Максимов Н.В., Голицына О.Л., Васина Е.Н. Управление данными

Подождите немного. Документ загружается.

зволяет организовать «потоковые» операции: однородность позволяет

рассматривать пересылаемые данные как непрерывный поток. Поток не

может быть прерван по контекстно определяемому условию, например,

при пересылке текста - по значению кода «перевод строки», и это не за-

ставляет программу анализировать значение каждого очередного эле-

мента. И, кроме того, последовательный доступ – это простота управле-

ния памятью и устройством ввода-вывода.

Таблица – это последовательности, обычно представляемые стро-

ками - совокупностями разнотипных элементов. Или, иначе, таблица -

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

нованных полей.

Однако с точки зрения размещения элементов таблица может быть

представлена как одномерный массив (или, в случае БД -

последовательность) с однородными композиционными элементами,

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

элементов. Именно это позволяет свести ввод/вывод таких типов

структур к последовательным элементарным операциям.

Кроме того, разнотипность элементов позволяет ввести отличную

от перечислительной схему идентификации записей, определив одно из

полей как ключ записи. Обычно ключ содержит значение, используемое

в процедурах упорядочения и поиска записей.

3.5.2. Нелинейные структуры

В качестве примеров нелинейных структур рассмотрим списки,

деревья и сети.

Порядок следования (и, соответственно, выборки) элементов таких

структур может не соответствовать порядку расположения элементов в

памяти. Списки представляют собой пример линейного упорядочения,

деревья – двумерного, сети – произвольного. Соответственно различа-

ются методы и средства, обеспечивающие последовательность выборки

элементов данных. Обычно для обеспечения возможности прямого дос-

тупа к произвольному элементу необходимо использовать вспомога-

тельные структуры типа инвертированных списков.

Список также, как и массив, представляет собой совокупность од-

нотипных элементов. Однако порядок выборки элементов может отли-

чаться от порядка следования в памяти, определенного при размещении.

Наиболее очевидный способ установления однонаправленного порядка

выборки элементов – это сопоставить каждому элементу списка ссылку,

указывающую на следующий элемент. Соответственно, для организации

двунаправленного списка, допускающего также выборку в обратном по-

рядке, каждый элемент должен иметь ссылку на предыдущий. Такая ор-

ганизация уже не допускает возможности прямого доступа, например,

по номеру элемента.

Кроме того, число элементов списка, как и в случае

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

начала обработки (и, соответственно, размещения) необходимо считать

длину списка бесконечной, что ведет к необходимости предусматривать

специальную процедуру выделения/освобождения памяти.

Таким образом, с точки зрения физической реализации элемент

списка должен быть составным, включающим собственно информатив-

ные данных, несущий смысловое значение, и дополнительные данные

(ссылки), определяющие порядок доступа к информативным элементам.

Понятие списка достаточно универсально. В общем случае ссылки

могут указывать ответвления к другим спискам – подспискам. В зависи-

мости от способа построения списка и предполагаемых путей доступа к

элементам различают следующие виды ссылок: перекрестные, боковые,

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

последовательный порядок прохода по элементам списка.

Деревья

Дерево (Рис. 3.7) представляет собой иерархию элементов, назы-

ваемых узлами. На самом верхнем уровне иерархии имеется только один

узел — корень. Каждый узел, кроме корня, связан с одним узлом на бо-

лее высоком уровне, называемым исходным узлом для данного узла. Ка-

ждый элемент имеет только один исходный. Каждый элемент может

быть связан с одним или несколькими элементами на более низком

уровне, которые называются порожденными. Элементы, расположенные

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

Корень

17 8 9 1 1

111

1 1

222

Листья

Рис. 3.7. Пример структуры типа дерево

Существует несколько способов представления структуры дерева.

Например, дерево может быть определено как иерархия узлов с попар-

ными связями, в которой:

1. Самый верхний уровень иерархии имеет один узел, называемый

корнем.

2. Все узлы, кроме корня, связываются с одним и только одним уз-

лом на более высоком уровне по отношению к ним самим.

Такое определение в части организации связей совпадает со спи-

ском, и, в частности, список представляет вырожденный случай дерева,

в котором каждая вершина имеет не более одного поддерева.

Еще раз отметим, что деревья здесь рассматриваются как средство

и для логического, и для физического представления данных. В логиче-

ском описании данных они используются для определения связей между

элементами структуры, а при определении физической организации

данных — для определения набора указателей, реализующих связи меж-

ду ними.

Использование ссылок для организации доступа к отдельным эле-

ментам структуры не позволяет сократить процедуру поиска, в основу

которой положен последовательный перебор. Процедура поиска будет

эффективнее, если будет предварительно установлен некоторый порядок

перехода к следующему элементу дерева. Такой порядок в ряде случаев

определяется в отношении метода обхода и регулярности итераций, оп-

ределяемой длиной пути и кратностью деления вершины.

Выделяют [2] три метода обхода: сверху вниз, слева направо, снизу

вверх.

Регулярность обхода дерева может быть связана с упорядоченными

деревьями, к которым относятся сбалансированные (Рис. 3.8) и двоичные

деревья (Рис. 3.9).

Рис. 3.8. Примеры сбалансированных и несбалансированных деревьев

Сбалансированное дерево в каждом узле имеет одинаковое число

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

сверху вниз, а на каждом уровне дерева — слева направо. Для дерева с

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

более простой. Однако большая часть логических организаций данных

Сбалансированные деревья

Несбалансированные деревья

не может быть задана в виде сбалансированной древовидной структуры,

и для их представления требуется переменное число ветвей в каждом

узле. В то же время индексы могут быть построены в виде сбалансиро-

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

Двоичные деревья - это особая категория сбалансированных древо-

видных структур, в которой допускается не более двух ветвей для одно-

го узла. На рис. 3.9 показано несбалансированное двоичное дерево.

Рис. 3.9. Пример несбалансированного двоичного дерева

Любые связи в дереве можно представить в виде двоичных древо-

видных структур. Рис. 3.10 иллюстрирует представление дерева в виде

двоичного дерева.

Рис. 3.10. Пример представления дерева в виде двоичного

4 5

6 7 8 9

11 12 13 14

16 17

21 22

3 4 5

8 9 10 11 12 13 14 15 16 17

18 19 20 21 22

Указатели на порожден-

ные элементы

При таком представлении каждый элемент может иметь указатели

как на порожденные, так и на подобные элементы.

Различные виды двоичных деревьев, для которых характерно на-

личие жесткой схемы управления их ростом, достаточно эффективно

используются для построения больших поисковых индексов, размещае-

мых обычно на устройствах внешней памяти. Кроме того, для таких де-

ревьев можно организовать специальное «страничное» хранение подде-

ревьев, что сократит число физических обращений к устройству.

Заметим, что деревья поисковых индексов являются однородными

структурами: каждый узел представлен элементами одного типа. Однако

большинство баз должно поддерживать организацию данных, имеющих

различную природу. В этом случае при работе с неоднородными струк-

турами разной глубины, гарантировать регулярность, обеспечивающую

эффективность процедур доступа, становится затруднительно.

3.5.3. Сетевые структуры

Иерархические структуры характерны для многих областей,

однако во многих случаях отдельная запись требует более одного

представления или связана с несколькими другими. В результате полу-

чаются обычно более сложные структуры по сравнению с древовидны-

ми. Например, генеалогическое дерево может быть представлено в виде

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

будет показан только один исходный элемент (родитель). Если бы были

показаны оба родителя, то это была бы более сложная структура.

В сетевой структуре любой элемент может быть связан с любым

другим элементом. Примеры сетевых структур приведены на рис. 3.11.

Рис. 3.11. Пример сетевых структур

Так же как и в случае древовидных структур, сетевую структуру

можно описать с помощью исходных и порожденных элементов. Удобно

представлять ее так, чтобы порожденные элементы располагались ниже

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

говорить об уровнях, так же как и в случае древовидных структур.

Во многих сетевых структурах, задающих связи между элемента-

ми, представление отношений между исходными и порожденными эле-

ментами аналогично представлению отношений в случае дерева: отно-

шение исходный-порожденный является сложным (указывается сдвоен-

ными стрелками), а отношение порожденный-исходный — простым

(указывается одинарными стрелками).

На рис. 3.12 показана неоднородная сетевая структура с пятью ти-

пами элементов. Ни одна из их соединяющих линий не имеет сдвоенных

стрелок в обоих направлениях. Каждое отношение может рассматри-

ваться как отношение «исходный-порожденный». Запись ЗАКАЗ-НА-

ЗАКУПКУ является порожденной по отношению к записи ИЗДЕЛИЕ и

исходной по отношению к записи ПАРТИЯ-ТОВАРА.

Рис. 3.12. Пример простой сетевой структуры

Желательно отличать структуры, в которых представление отно-

шений «порожденный-исходный» является простым или не использует-

ся, от структур, в которых представление отношений между какими-то

двумя типами данных является сложным в обоих направлениях. Для

структур второго типа на одной из линий схемы будут сдвоенные стрел-

ки, указывающие в разные стороны. Этот тип схемы назовем сложной

сетевой структурой, а схему, в которой ни на одной из линий нет сдво-

енных стрелок в обоих направлениях,— простой сетевой структурой. На

рис. 3.9 показана простая сетевая структура. Она станет сложной, если

ввести отношение ЗАКАЗ-НА-ЗАКУПКУ — ИЗДЕЛИЕ, когда один за-

каз может быть сделан сразу на несколько изделий. Для образования

сложной сетевой структуры достаточно двух типов элементов. Напри-

мер, ПОСТАВЩИК может иметь несколько порожденных записей, по-

тому что может поставляться более одного вида изделий. С другой сто-

Поставщик

Изделие

Расценка

Заказ на

закупку

Партия

товара

роны, элемент ИЗДЕЛИЕ может иметь более одного исходного элемен-

та, поскольку это изделие может поставляться различными поставщика-

ми.

В некоторых случаях один элемент данных может быть связан с

целой совокупностью других элементов данных. Например, одно изде-

лие может поставляться несколькими поставщиками, каждый из кото-

рых установил свою цену на это изделие. Элемент данных ЦЕНА не мо-

жет быть ассоциирован только с элементом ИЗДЕЛИЕ или только с эле-

ментом ПОСТАВЩИК, а должен быть связан одновременно с двумя.

Информация такого рода, т. е. данные, ассоциированные с со-

вокупностью элементов, называют иногда данными пересечения.

Некоторые структуры содержат циклы. Циклом считается ситуа-

ция, в которой предшественник узла является в то же время его последо-

вателем. Отношения «исходный-порожденный» образуют при этом

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

Некоторые изделия производятся на других заводах-субподрядчиках. С

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

лий. Представление этих отношений и образует цикл.

Иногда элементы связаны с другими элементами того же типа. Та-

кая ситуация называется петлей. На рис. 3.13 приведены две достаточно

распространенные ситуации, где могут использоваться петли. В массиве

служащих специфицированы связи, существующие между некоторыми

служащими. В базу данных списка материалов введено дополнительное

усложнение: некоторые узлы сами состоят из узлов.

Рис. 3.13. Пример сетевой структуры с петлей

Разделение сетевых структур на простые и сложные необходимо

потому, что сложные структуры требуют более сложных методов физи-

ческого представления. Это не всегда является недостатком, поскольку

ру

ководит

ру

ководитель

сл

жащий

изделие

зел

деталь

сложную сетевую структуру можно (а в большинстве случаев и следует)

преобразовать к простому виду.

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

3.6.1. Основные понятия реляционной модели данных

Реляционная

модель является удобной и наиболее привычной

формой представления данных в виде таблицы. В отличие от иерархиче-

ской и сетевой модели, такой способ представления 1) понятен пользо-

вателю-непрограммисту; 2) позволяет легко изменять схему – присоеди-

нять новые элементы данных и записи без изменения соответствующих

подсхем; 3) обеспечивает необходимую гибкость при обработке не-

предвиденных запросов. К тому же любая сетевая или иерархическая

схема может быть представлена двумерными отношениями.

Одним из основных преимуществ реляционной модели является ее

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

которых каждая строка имеет один и тот же формат. Каждая строка в

таблице представляет некоторый объект реального мира или соотноше-

ние между объектами. Пользователь модели сам должен для себя ре-

шить вопрос, обладают ли соответствующие сущности реального мира

однородностью. Этим самым решается проблема пригодности модели

для предполагаемого применения.

Основными понятиями, с помощью которых определяется реляци-

онная модель, являются следующие: домен, отношение, кортеж, кар-

динальность, атрибуты, степень, первичный ключ. Соотношение этих

понятий иллюстрируется рис. 3.14. Эти понятия представляют специ-

альную терминологию, введенную авторами теоретических основ, одна-

ко они имеют и более привычные аналоги (но не во всем эквиваленты!),

соответствие которых приведено в следующей таблице 3.1.

Таблица 3.1

Домен Совокупность допустимых

значений

Кортеж Таблица

Кардинальность Количество строк в таблице

Атрибут Поле, столбец таблицы

Степень отношения Количество полей (столбцов)

Первичный ключ Уникальный идентификатор

Домен – это совокупность значений, из которой берутся значения

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

В математических дисциплинах понятию «таблица» соответствует понятие «отношение» (relation).

Отсюда и произошло название модели – реляционная. Т.е., применительно к базам данных понятия

«реляционная БД» и «табличная БД» по существу являются синонимами.

программирования домен – это тип данных, определяемый системой

(стандартный) или пользователем.

Первичный ключ – это столбец или некоторое подмножество

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

строки. Первичный ключ, который включает более одного столбца, на-

зывается множественным, или комбинированным, или составным. Пра-

вило целостности объектов утверждает, что первичный ключ не может

быть полностью или частично пустым, т.е. иметь значение null.

Остальные ключи, которые можно также использовать в качестве

первичных, называются потенциальными или альтернативными клю-

чами.

Внешний ключ – это столбец или подмножество одной таблицы,

который может служить в качестве первичного ключа для другой табли-

цы. Внешний ключ таблицы является ссылкой на первичный ключ дру-

гой таблицы. Правило ссылочной целостности гласит, что внешний

ключ может быть либо пустым, либо соответствовать значению первич-

ного ключа, на который он ссылается. Внешние ключи являются неотъ-

емлемой частью реляционной модели, поскольку реализуют связи меж-

ду таблицами базы данных.

Внешний ключ, как и первичный ключ, тоже может представлять

собой комбинацию столбцов. На практике внешний ключ всегда будет

составным (состоящим из нескольких столбцов), если он ссылается на

составной первичный ключ в другой таблице. Очевидно, что количество

столбцов и их типы данных в первичном и внешнем ключах совпадают.

Если таблица связана с несколькими другими таблицами, она мо-

жет иметь несколько внешних ключей.

Модель предъявляет к таблицам следующие требования:

1. данные в ячейках таблицы должны быть структурно недели-

мыми

;

2. данные в одном столбце должны быть одного типа;

3. каждый столбец должен быть уникальным (недопустимо дуб-

лирование столбцов);

4. столбцы размещаются в произвольном порядке;

5. строки размещаются в таблице также в произвольном порядке;

6. столбцы имеют уникальные наименования.

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

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

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

принцип неделимости информации, поскольку в ячейке окажутся разделяемые данные, имеющие раз-

ную информационную сущность, такие, как наименование модели, номер кузова, двигателя, сведения

о предприятии-изготовителе и т.д.