Файл: Тема Введение в теорию баз данных Вопрос Основные понятия.pdf

·
нелинейные.
2)
с точки зрения однородности и «элементарности» типов данных, отражающих понятийную структуру ПрО.
по характеру информации, представляемой структурой:
·
однородные структуры, где все элементы находятся на одном понятийном уровне и имеют один тип данных,
·
неоднородные (композиционные), где элементы относятся к нескольким понятийным уровням или имеют разную природу.
Линейные структуры.
К линейным структурам относятся массивы и последовательности, таблицы.
Порядок следования (и, соответственно, выборки) элементов таких структур имеет линейный характер и соответствует порядку расположения элементов в памяти: один за другим без каких-либо промежутков.
Адрес элемента соответствует его положению и определяется индексом - порядковым номером элемента в последовательности размещения. К
элементу имеется прямой доступ, если известен его индекс.
Особенностью линейной структуры является то, что при последовательной организации (размещении) она допускает возможность прямого доступа
к произвольному элементу. Это возможно потому, что условие однородности (однотипности) предполагает, что все элементы занимают расположенные строго последовательно области одинакового размера, что и позволяет достаточно просто вычислять значение физического адреса элемента по значению его индекса.
Массив представляет собой совокупность однотипных элементов, причем число элементов массива известно до его размещения, что позволяет строить гибкие многомерные системы адресации.
Последовательность, так же, как и массив, представляет собой совокупность однотипных элементов. Однако число элементов до размещения неизвестно.
Хотя, каждая конкретная последовательность имеет конечную длину, до начала обработки (и, соответственно, размещения) необходимо считать длину последовательности бесконечной.
Принципиальность такого предположения выражается в том, что необходимо предусматривать специальную процедуру использования памяти (выделения/освобождения),
алгоритм обработки последовательности по частям (в ряде случаем, когда это требуется).
Этот тип данных превалирует в операциях ввода/вывода с устройствами внешней памяти.
Последовательный доступ позволяет организовать «потоковые» операции: однородность позволяет рассматривать пересылаемые данные как непрерывный поток.

---

Поток не может быть прерван по контекстно определяемому условию.
Например, при пересылке текста - по значению кода «перевод строки», и это не заставляет программу анализировать значение каждого очередного элемента. И, кроме того, последовательный доступ - это простота управления памятью и устройством ввода-вывода.
Но мы, не рассматриваем очереди и стеки. Они отличаются тем, что для них устанавливаются особые схемы добавления (размещения в памяти)
новых элементов и их выборки.
Очередь: порядок размещения/выборки определяется правилом «первым размещен – первым выбран».
Стек - «первым размещен – последним выбран». Выборка элемента влечет его удаление из последовательности.)
Таблица - это последовательности, обычно представляемые строками - совокупностями разнотипных элементов. Таблица -это множество записей,
каждая из которых представляет набор поименованных полей.
Однако с точки зрения размещения элементов таблица может быть представлена как одномерный массив (или, в случае БД - последовательность) с однородными композиционными элементами, каждый из которых представляет собой совокупность разнотипных элементов.
Это позволяет свести ввод/вывод таких типов структур к последовательным элементарным операциям.
Разнотипность элементов позволяет ввести отличную от перечислительной схему идентификации записей, определив одно из полей как ключ записи.
Обычно ключ содержит значение, используемое в процедурах упорядочения и поиска записей.
Нелинейные структуры.
В качестве примеров нелинейных структур рассмотрим списки, деревья и сети.
Порядок следования (и, соответственно, выборки) элементов таких структур может не соответствовать порядку расположения элементов в памяти.
Списки представляют собой пример линейного упорядочения,

---

Деревья - двумерного,
Сети - произвольного.
Соответственно различаются методы и средства, обеспечивающие последовательность выборки элементов данных. Обычно для обеспечения возможности прямого доступа к произвольному элементу необходимо использовать вспомогательные структуры типа инвертированных списков.
Список представляет собой совокупность однотипных элементов. Порядок выборки элементов может отличаться от порядка следования в памяти,
определенного при размещении. Наиболее очевидный способ установления однонаправленного порядка выборки элементов - это сопоставить каждому элементу списка ссылку, указывающую на следующий элемент. Соответственно, для организации двунаправленного списка, допускающего также выборку в обратном порядке, каждый элемент должен иметь ссылку на предыдущий.
Такая организация уже не допускает возможности прямого доступа, например, по номеру элемента.
Число элементов списка, как и в случае последовательностей, может быть неизвестно до размещения, и до начала обработки (и, соответственно,
размещения) необходимо считать длину списка бесконечной, что ведет к необходимости предусматривать специальную процедуру выделения/
освобождения памяти.
Таким образом, с точки зрения физической реализации элемент списка должен быть составным, включающим собственно информативные данных,
несущий смысловое значение, и дополнительные данные (ссылки), определяющие порядок доступа к информативным элементам.
Понятие списка достаточно универсально. В общем случае ссылки могут указывать ответвления к другим спискам - подспискам.
В зависимости от способа построения списка и предполагаемых путей доступа к элементам различают следующие виды ссылок:
·
перекрестные,
·
боковые,
·
иерархические,
·
множественные,
Они позволяют изменять «естественный» последовательный порядок прохода по элементам списка.
Деревья.
Дерево (рис. 15) представляет собой иерархию элементов, называемых узлами. На самом верхнем уровне иерархии имеется только один узел - корень.
Каждый узел, кроме корня, связан с одним узлом на более высоком уровне, называемым исходным узлом для данного узла. Каждый элемент имеет только один исходный. Каждый элемент может быть связан с одним или несколькими элементами на более низком уровне, которые называются

---

порожденными.
Элементы, расположенные в конце ветви, т. е. не имеющие порожденных, называются листьями.
Рис. 15. Пример структуры дерева
Существует несколько способов представления структуры дерева.
Например, дерево может быть определено как иерархия узлов с попарными связями, в которой:
1.
Самый верхний уровень иерархии имеет один узел, называемый корнем.
2.
Все узлы, кроме корня, связываются с одним и только одним узлом на более высоком уровне по отношению к ним самим.
Такое определение в части организации связей совпадает со списком, и, в частности, список представляет вырожденный случай дерева, в котором каждая вершина имеет не более одного поддерева. Заметим, что деревья мы рассматриваем как средство и для логического, и для физического представления данных.
В логическом описании данных они используются для определения связей между элементами структуры. При определении физической
организации данных - для определения набора указателей, реализующих связи между ними.
Использование ссылок для организации доступа к отдельным элементам структуры не позволяет сократить процедуру поиска, в основу которой положен последовательный перебор. Процедура поиска будет эффективнее, если будет предварительно установлен некоторый порядок перехода к следующему элементу дерева. Такой порядок в ряде случаев определяется в отношении метода обхода и регулярности итераций, определяемой длиной пути и кратностью деления вершины.
Выделяют три метода обхода: сверху вниз, слева направо, снизу вверх. Регулярность обхода дерева может быть связана с упорядоченными деревьями,
к которым относятся сбалансированные (рис. 16) и двоичные деревья (рис. 17).
Рис. 16. Примеры сбалансированных и несбалансированных деревьев
Сбалансированное дерево в каждом узле имеет одинаковое число ветвей, причем процесс включения новых ветвей в узлы дерева идет сверху вниз, а на каждом уровне дерева — слева направо. Для дерева с фиксированным числом ветвей физическая организация данных будет более простой. Однако большая часть логических организаций данных не может быть задана в виде сбалансированной древовидной структуры, и для их представления требуется переменное число ветвей в каждом узле. В то же время индексы могут быть построены в виде сбалансированных древовидных структур.

---

Двоичные деревья - это особая категория сбалансированных древовидных структур, в которой допускается не более двух ветвей для одного узла. На рис. 17 показано несбалансированное двоичное дерево.
Рис. 17. Пример несбалансированного двоичного дерева
Любые связи в дереве можно представить в виде двоичных древовидных структур. Рис. 18 иллюстрирует представление дерева в виде двоичного дерева.
Рис. 18. Пример представления дерева в виде двоичного
При таком представлении каждый элемент может иметь указатели как на порожденные, так и на подобные элементы.
Различные виды двоичных деревьев, для которых характерно наличие жесткой схемы управления их ростом, достаточно эффективно используются для построения больших поисковых индексов, размещаемых обычно на устройствах внешней памяти. Кроме того, для таких деревьев можно организовать специальное «страничное» хранение поддеревьев, что сократит число физических обращений к устройству. Заметим, что деревья поисковых индексов являются однородными структурами: каждый узел представлен элементами одного типа. Однако большинство баз должно поддерживать организацию данных, имеющих различную природу. В этом случае при работе с неоднородными структурами разной глубины, гарантировать регулярность,
обеспечивающую эффективность процедур доступа, становится затруднительно.
Сетевые структуры.
Иерархические структуры характерны для многих областей, однако во многих случаях отдельная запись требует более одного представления или связана с несколькими другими. В результате получаются обычно более сложные структуры по сравнению с древовидными. Например, генеалогическое дерево может быть представлено в виде древовидной структуры, только если для каждого элемента (личности) будет показан только один исходный элемент (родитель). Если бы были показаны оба родителя, то это была бы более сложная структура.
В сетевой структуре любой элемент может быть связан с любым другим элементом.
Рис. 19. Пример сетевых структур
Так же как и в случае древовидных структур, сетевую структуру можно описать с помощью исходных и порожденных элементов. Удобно представлять ее так, чтобы порожденные элементы располагались ниже исходных. При рассмотрении некоторых сетевых структур естественно говорить об уровнях, так же как и в случае древовидных структур.

---