Основные структуры данных. 2

КУРСОВАЯ РАБОТА

по дисциплине «Информатика»

на тему «Основные структуры данных»

                                                                Исполнитель:

Смоленск - 2011

Оглавление

Оглавление………………………………………………………………………..2

Введение…..……………………………………………………….……………...3

1. Основные структуры данных ……….………………………………………4

     1.1. Классификация баз данных…………………………………….………...8

     1.2 Структурные элементы базы данных…………………………………..10

2. Виды моделей данных………………………………………………….…….12

     2.1. Иерархическая модель данных………………………………….…...13

     2.2. Сетевая модель данных…………………………………………………15

     2.3. Реляционная модель данных…………………………………………...17

Практическая часть ………………………...…………………………….……..20

Заключение……………………………………………………………………….25

Список использованной литературы……………………………………….......26

Введение

Современные информационные системы, основанные на концепции интеграции данных, характеризуются огромными объемами хранимых данных, сложной организацией, необходи­мостью удовлетворять разнообразные требования многочисленных пользователей.

В современных базах данных хранятся отнюдь не только данные, но и информация.

Это утверждение легко пояснить, если, например, рассмотреть базу данных круп­ного банка. В ней есть все необходимые сведения о клиентах, об их адресах, кре­дитной истории, состоянии расчетных счетов, финансовых операциях и т. д. Доступ к этой базе имеется у достаточно большого количества сотрудников банка, но среди них вряд ли найдется такое лицо, которое имеет доступ ко всей базе полностью и при этом способно единолично вносить в нее произвольные изменения. Кроме дан­ных, база содержит методы и средства, позволяющие каждому из сотрудников оперировать только с теми данными, которые входят в его компетенцию. В результате взаимодействия данных, содержащихся в базе, с методами, доступными конкрет­ным сотрудникам, образуется информация, которую они потребляют и на основа­нии которой в пределах собственной компетенции производят ввод и редактиро­вание данных.

Теоретическая часть работы направлена на формирование представления о базах данных (БД) и их основных видах.

В практической части данной работы будет показана взаимосвязь таблиц, выполнение расчетов на основе табличных данных, графическое построение полученных данных.

1. Основные структуры данных

Цель любой информационной системы — обработка данных об объектах реального мира. В широком смысле слова база данных (БД) — это поименованная совокупность структурированных и взаимосвязанных сведений о конкретных объектах реального мира в какой-либо предметной области. Под предметной областью принято понимать часть реального мира, подлежащего изучению для организации управления и, в конечном счете, автоматизации, например, предприятие, вуз и т.д.

Для поиска данных в базе данных применяется общий управляемый способ. Данные запоминаются так, чтобы они были независимы от программ, использующих эти дан­ные; открыты для добавления новых или модификации существу­ющих данных.

Основные требования к организации баз данных.

1.  База данных - это основа для будущего наращивания при­кладных программ. Базы данных должны обеспечивать возмож­ность разработки приложений легче, быстрее, дешевле.

2. Многократное использование данных. Пользователи, кото­рые по-разному понимают одни и те же данные, могут использо­вать их различным образом.

3. Сохранение затрат умственного труда. Существующие про­граммы и логические структуры данных не переделываются при внесении изменений в базу данных.

4.  Простота. Пользователи могут легко узнать и понять, ка­кие данные имеются в их распоряжении.

5. Легкость использования. Пользователи имеют простой до­ступ к данным; сложный доступ к данным осуществляет СУБД.

6.  Гибкость использования. Обращение к данным или их по­иск осуществляется с помощью различных методов доступа.

7.  Быстрая обработка незапланированных запросов на дан­ные. Случайные запросы на данные могут обрабатываться с по­мощью высокоуровневого языка запросов или языка генерации отчетов, а не прикладными программами.

8. Простота внесения изменений. База данных может увеличи­ваться и изменяться без нарушения имеющихся способов исполь­зования данных.

9. Небольшие затраты. Низкая стоимость хранения и исполь­зования данных и минимизация затрат на внесение изменений.

10. Уменьшение избыточности данных. Требования новых при­ложений удовлетворяются за счет существующих данных, а не путем создания новых файлов.

11. Производительность. Запросы на данные удовлетворяются с такой скоростью, которая требуется для использования данных.

12. Достоверность данных и соответствие одному уровню об­новления. Необходимо использовать контроль за достоверностью данных. Система предотвращает наличие различных версий од­них и тех же элементов данных, доступных пользователям, на раз­ных стадиях обновления.

13. Секретность. Несанкционированный доступ к данным не­возможен. Ограничение доступа к одним и тем же данным для различного их использования может осуществляться разными способами.

14. Защита от искажения и уничтожения. Данные должны быть защищены от сбоев, катастрофических и криминальных ситуаций, некомпетентного или злонамеренного обращения к ним лиц, ко­торые могут ошибочно обновить их.

15.  Готовность. Пользователь быстро получает данные вся­кий раз, когда это ему необходимо.

Создавая базу данных, пользователь стремится упорядочить информацию по различ­ным признакам и быстро извлекать выборку с произвольным сочетанием признаков. Сделать это возможно, только если данные структурированы.

Структурирование — это введение соглашений о способах представления данных.

Неструктурированными называют данные, записанные, например, в текстовом файле.

Пример неструктурированных данных:

Личное дело № 16493, Сергеев Петр Михайлович, дата рождения 1 января 1976 г.; Л/д № 16593, Петрова Анна Владимировна, дата рожд. 15 марта 1975 г.; № личн. дела 16693, др. 14.04.76, Анохин Андрей Борисович.

Чтобы автоматизировать поиск и систематизировать эти данные, необходимо вырабо­тать определенные соглашения о способах представления данных, т.е. дату рождения нужно записывать одинаково для каждого студента, она должна иметь одинаковую длину и определенное место среди остальной информации. Эти же замечания спра­ведливы и для остальных данных (номер личного дела, фамилия, имя, отчество).

После проведения несложной структуризации с информацией, указан­ной в примере, она будет выглядеть так:

Таблица 1  Пример структурированных данных

Пользователями базы данных могут быть различные прикладные программы, программные комплексы, а также специалисты предметной области, выступающие в роли потребителей или источников данных, называемые конечными пользователями.

В современной технологии баз данных предполагается, что создание базы данных, ее поддержка и обеспечение доступа пользователей к ней осуществляются централизованно с помощью специального программного инструментария — системы управления базами данных.

Система управления базами данных (СУБД) — это комплекс программных и языковых средств, необходимых для создания баз данных, поддержа­ния их в актуальном состоянии и организации поиска в них необходимой информации.

Централизованный характер управления данными в базе данных предполагает необхо­димость существования некоторого лица (группы лиц), на которое возлагаются функции ад­министрирования данными, хранимыми в базе.

1.1.           Классификация баз данных

По технологии обработки данных базы данных подразделяются на централизованные и распределенные.

Централизованная база данных хранится в памяти одной вычислительной системы. Если эта вычислительная система является компонентом сети ЭВМ, возможен распределенный доступ к такой базе. Такой способ использования баз данных часто приме­няют в локальных сетях ПК.

Распределенная база данных состоит из нескольких, возможно пересекаю­щихся или даже дублирующих друг друга частей, хранимых в различных ЭВМ вычисли­тельной сети. Работа с такой базой осуществляется с помощью системы управления распределенной базой данных (СУРБД).

По способу доступа к данным базы данных разделяются на базы данных с локальным доступом и базы данных с удаленным (сетевым) доступом.

Системы централизованных баз данных с сетевым доступом предполагают различные архитектуры  подобных систем:

-     файл-сервер;

-     клиент-сервер.

Файл-сервер. Архитектура систем БД с сетевым доступом предполагает выделение одной из машин сети в качестве центральной (сервер файлов). На такой машине хранится совместно используемая централизованная БД. Все другие машины сети выполняют функ­ции рабочих станций, с помощью которых поддерживается доступ пользовательской системы к централизованной базе данных. Файлы базы данных в соответствии с пользова­тельскими запросами передаются на рабочие станции, где в основном и производится обра­ботка. При большой интенсивности доступа к одним и тем же данным производительность информационной системы падает. Пользователи могут создавать также на рабочих станциях локальные БД, которые используются ими монопольно. Концепция файл-сервер условно отображена на рисунке 1:

Рис.1  Схема обработки информации в БД по принципу файл-сервер

Клиент-сервер. В этой концепции подразумевается, что помимо хранения централи­зованной базы данных центральная машина (сервер базы данных) должна обеспечивать вы­полнение основного объема обработки данных. Запрос на данные, выдаваемый клиентом (рабочей станцией), порождает поиск и извлечение данных на сервере. Извлеченные данные (но не файлы) транспортируются по сети от сервера к клиенту. Спецификой архитектуры клиент-сервер является использование языка запросов SQL. Концепция клиент-сервер ус­ловно изображена на рисунке 2:

Рис.2  Схема обработки информации в БД по принципу клиент-сервер

1.2.Структурные элементы базы данных

Понятие базы данных тесно связано с такими понятиями структурных элементов, как поле, запись, файл (таблица).

                                                   Поле                         Запись

Рис.3  Основные структурные элементы БД

Поле — элементарная единица логической организации данных, которая соответст­вует неделимой единице информации — реквизиту. Для описания поля используются сле­дующие характеристики:

имя, например, Фамилия, Имя, Отчество, Дата рождения;

тип, например, символьный, числовой, календарный;

длина, например, 15 байт, причем будет определяться максимально возможным ко­личеством символов;

точность для числовых данных, например два десятичных знака для отображения дробной части числа.

Запись — совокупность логически связанных полей. Экземпляр записи — отдельная реализация записи, содержащая конкретные значения ее полей.

Файл (таблица) — совокупность экземпляров записей одной структуры.

Описание логической структуры записи файла содержит последовательность располо­жения полей записи и их основные характеристики, как это показано в таблице 2:

Таблица 2.  Описание логической структуры записи файла

В структуре записи файла указываются поля, значения которых являются  ключами  первичными   (ПК), которые идентифицируют экземпляр записи, и вторичными (ВК), которые выполняют роль поисковых или группировочных признаков (по значению вторичного ключа можно найти несколько записей).

В таблице 3 приведен пример описания логической структуры записи файла (таблицы) СТУДЕНТ, содержимое которого приводится в таб.1. Структура записи файла СТУДЕНТ линейная, она содержит записи фиксированной длины. По­вторяющиеся группы значений полей в записи отсутствуют. Обращение к значению поля производится по его номеру.

Таблица 3.  Описание логической структуры записи файла СТУДЕНТ

2. Виды моделей данных

Ядром любой базы данных является модель данных. Модель данных представляет собой множество структур данных, ограничений целостности и операций манипулирования данными. С помощью модели данных могут быть представлены объекты предметной области и взаимосвязи между ними.

Модель данных — совокупность структур данных и операции их обработки.

СУБД основывается на использовании  иерархической, сетевой или реляционной моде­ли, на комбинации этих моделей или на некотором их подмножестве.

Рассмотрим три основных типа моделей данных: иерархическую, сетевую и реляционную.

2.1. Иерархическая модель данных

Иерархическая структура представляет совокупность элементов, связанных между собой по Определенным правилам. Объекты, связанные иерархическими отношениями, образуют ориентированный граф (перевернутое дерево), вид которого представлен на рисунке 4:

Рис.4 Графическое изображение иерархической структуры БД

К основным понятиям иерархической структуры относятся: уровень, элемент (узел), связь. Узел — это совокупность атрибутов данных, описывающих некоторый объект. На схеме иерархического дерева узлы представляются вершинами графа. Каждый узел на более низком уровне связан только с одним узлом, находящимся на более высоком уровне. Иерархическое дерево имеет только одну вершину (корень дерева), не подчиненную никакой другой вершине и находящуюся на самом верхнем (первом) уровне. Зависимые (подчиненные) узлы находятся на втором, третьем и т.д. уровнях. Количество деревьев в базе данных определяется числом корневых записей.

К каждой записи базы данных существует только один (иерархический) путь от корневой записи. Например, как видно из рисунка, для записи С4 путь проходит через записи А и В3.

На представленном ниже рисунке 5 мы наблюдаем использование иерархической модели базы данных.

Рис.5  Пример иерархической структуры БД

Для рассматриваемого примера иерархическая структура правомерна, так как каждый студент учится в определенной (только одной) группе, которая относится к опреде­ленному (только одному) институту.

Достоинствами иерархической модели являются наличие промышленных СУБД, поддерживающих данную модель, просто­та понимания используемого принципа иерархии, обеспечение определенного уровня независимости данных.

К основным недостаткам такого вида модели можно отнести следующие: сложность отображения связей «многие ко многим»; иерархия в значительной степени усложняет операции включения информации о новых объектах в базу данных и удаления устарев­шей; доступ к любому узлу возможен только через корневой.

2.2             Сетевая модель данных

В сетевой структуре при тех же основных понятиях (уровень, узел, связь) каждый элемент может быть связан с любым другим элементом.

              На рисунке 6 изображена сетевая структура базы данных в виде графа.

Рис.6  Графическое изображение сетевой структуры

Примером сложной сетевой структуры может служить структура базы данных, содержащей сведения о студентах, участвующих в научно-исследовательских работах (НИРС). Возможно участие одного студента в нескольких НИРС, а также участие нескольких студентов в разработке одной НИРС. Графическое изображение описанной в примере сетевой структуры, состоящей только из двух типов записей, показано на рисунке 7. Единственное отношение представляет собой сложную связь между записями в обоих направлениях.

Рис.7  Пример сетевой структуры БД

Основной недостаток сетевой модели состоит в ее сложности. Прикладной программист должен детально знать логическую структуру базы данных, поскольку ему необходимо осуществлять навигацию среди различных экземпляров наборов и записей, т.е. программист должен представлять «свое» текущее состояние в экземплярах наборов при «продвижении» по базе данных. Дру­гим недостатком является возможная потеря независимости дан­ных при реорганизации базы данных. Кроме того, в сетевой мо­дели данных представление, используемое прикладной програм­мой, сложнее, чем в иерархической модели, поэтому и процедура составления прикладных программ может оказаться сложнее.

2.3.      Реляционная модель данных

Табличная форма — наиболее простая и распрост­раненная форма организации баз данных, получившая название реляционной.

Понятие реляционный (англ. relation — отношение) связано с разработками известного американского специалиста в области систем баз данных Е. Кодда.

Эти модели характеризуются простотой структуры данных, удобным для пользователя табличным представлением и возможностью использования формального аппарата алгебры отношений и реляционного исчисления для обработки данных.

Реляционная модель ориентирована на организацию данных в виде двумерных таблиц

Каждая реляционная таблица представляет собой двумерный массив и обла­ет следующими свойствами:

— каждый элемент таблицы — один элемент данных;

— все столбцы в таблице однородные, т.е. все элементы в столбце имеют одинаковый

— тип (числовой, символьный и т.д.) и длину;

— каждый столбец имеет уникальное имя;

— одинаковые строки в таблице отсутствуют;

— порядок следования строк и столбцов может быть произвольным.

Реляционной таблицей можно представить информацию о студентах, обучающихся в вузе.

Таблица 4.  Пример реляционной таблицы