Взаимосвязь этапов создания базы данных (БД) и используемых моделей предметной области. Классификационная схема моделей базы данных (БД).
Каждый этап строится на предыдущем и если что - возвращается к нему Концептуальная модель представляет объекты и их взаимосвязи без указания способов их физического хранения. Концептуальная модель включает описания объектов и их взаимосвязей, представляющих интерес в рассматриваемой предметной области и выявляемых в результате анализа данных. Концептуальная модель транслируется затем в модель данных, совместимую с выбранной СУБД. Версия концептуальной модели, которая может быть обеспечена конкретной СУБД, называется логической моделью. Логическая модель отражает логические связи между элементами данных вне зависимости от их содержания и среды хранения.
Логическая модель данных может быть реляционной, иерархической или сетевой. Пользователям выделяются подмножества этой логической модели, называемые внешними моделями, отражающие их представления о предметной области. Физическая модель, определяющая размещение данных, методы доступа и технику индексирования, называется внутренней моделью системы. Внешние модели никак не связаны с типом физической памяти, в которой будут храниться данные, и с методами доступа к этим данным. Это положение отражает первый уровень независимости данных. Если концептуальная модель способна учитывать расширение требований к системе в будущем, то вносимые в нее изменения не должны оказывать влияния на существующие внешние модели. Это - второй уровень независимости данных. Построение логической модели обусловлено требованиями используемой СУБД. Поэтому при замене СУБД она также может измениться. Основное различие между указанными выше тремя типами моделей данных (концептуальной, логической и физической) состоит в способах представления взаимосвязей между объектами. При проектировании БД нам потребуется различать взаимосвязи между объектами, между атрибутами одного объекта и между атрибутами различных объектов.
Иерархическая модель данных строится по принципу иерархии типов объектов, то есть один тип объекта является главным, а остальные, находящиеся на низших уровнях иерархии, - подчиненными. Между главным и подчиненными объектами устанавливается взаимосвязь «один ко многим». Иными словами, для данного главного типа объекта существует несколько подчиненных типов объекта. В то же время для каждого экземпляра главного объекта может быть несколько экземпляров подчиненных типов объектов. Узлы и ветви образуют иерархическую древовидную структуру. Узел является совокупностью атрибутов, описывающих объект. Наивысший в иерархии узел называется корневым (это главный тип объекта). Корневой узел находится на первом уровне. Зависимые узлы (подчиненные типы объектов) находятся на втором, третьем и т. д. уровнях. Недостатки: из нижних уровней иерархии нельзя направить информационный поиск по вышележащим узлам. Сетевая модель.В сетевой модели данных понятия главного и подчиненных объектов несколько расширены. Любой объект может быть и главным и подчиненным (в сетевой модели главный объект обозначается термином «владелец набора», а подчиненный - термином «член набора»). Один и тот же объект может одновременно выступать и в роли владельца, и в роли члена набора. Это означает, что каждый объект может участвовать в любом числе взаимосвязей. Реляционная модель.В реляционной модели данных (ввел в 1970 г. Э. Ф. Кодд.) объекты и взаимосвязи между ними представляются с помощью таблиц. Взаимосвязи также рассматриваются в качестве объектов. Каждая таблица представляет один объект и состоит из строк и столбцов. В реляционной базе данных каждая таблица должна иметь первичный ключ (ключевой элемент) - поле или комбинацию полей, которые единственным образом идентифицируют каждую строку в таблице. Благодаря своей простоте и естественности представления реляционная модель получила наибольшее распространение в СУБД для персональных компьютеров. Признаки, позволяющие считать таблицу отношением.В таблице нет строк с совпадающими ключами (строки уникальны). В каждой строке содержатся значения одного и того же набора атрибутов. Отношения неразложимы (не могут быть элементами другого отношения). Достоинства реляционных моделей данных Упрощение схемы данных для пользователя. Как уже известно, древовидная и сетевая модели объединяют в одной схеме понятия логического и физического уровней, т. е. построение схемы пользователем требует хорошего знания технических приемов, реализованных в системе, если необходимо получить эффективную в использовании БД. Преимуществом реляционной модели перед другими моделями является простая и удобная для пользователя схема данных, представляемая в виде таблиц. • Улучшение логической и физической независимости. Логическая независимость допускает возможность применения одной концептуальной модели различными пользователями. Физическая независимость дает возможность в целях эффективности использования БД модифицировать физическую организацию данных и пути доступа. Например, необходимо добавить или удалить некоторую связь между записями без изменения программы. В иерархической и сетевой моделях физическая независимость является слабой, так как схема зависит от физического описания, и, следовательно, любое физическое изменение пути доступа в той или иной степени влияет на ПП. Физическая независимость реляционной модели состоит в том, что модель данных не включает никаких физических описаний. В действительности физическое представление отношений и путей доступа описывается независимо от описания логической схемы отношений.
• Обеспечение пользователя языками высокого уровня. Манипулирование данными в иерархической и сетевой моделях производится с помощью процедурных языков. Язык является непроцедурным, когда с его помощью задают информацию, которую желают получить, не указывая способа доступа к этой информации. Для реляционных моделей бессмысленно использовать процедурный язык, поскольку обеспечена физическая независимость данных. С помощью команд процедурного языка программист строит стратегию доступа к данным. Но любое изменение пути доступа приводит к необходимости модификации программы.
• Оптимизация доступа к БД. Увеличение физической независимости и использование непроцедурных языков требуют от системы выбора наилучшей стратегии доступа. Поскольку в программе не определяется стратегия доступа, то система выбирает наиболее эффективную из возможных.
• Улучшение целостности и защиты данных. Современные СУБД, ориентированные на иерархические и сетевые модели, имеют ограниченные средства для поддержания целостности и защиты данных. Требования целостности определяются логическими терминами на уровне концептуальной схемы. Реляционная модель позволяет улучшить выражение требований целостности путем использования языка высокого уровня. Для обеспечения безопасности и секретности необходимо указать информацию, которую нужно защитить, и пользователей, применяющих данную информацию. Эффективность описания достигается применением непроцедурных языков, поскольку они способны идентифицировать информацию вне зависимости от любого пути доступа. • Возможности различных применений. Использование простой реляционной схемы и языка запросов, рассчитанного на непрограммистов, позволяет расширить области применения. • Обеспечение методологического подхода. Главной целью модели БД является возможность описания реального мира. В реляционной модели определение первой, второй, третьей нормальных форм, как увидим далее, основывается на математической теории отношений, позволяет пользователю структурировать информацию, точно идентифицируя связи, существующие между элементами информации, и ограничения, которым эти элементы должны удовлетворять. Кроме того, концепция нормальной формы отношения есть средство измерения уровня качества модели. В частности, далее увидим, что концептуальная схема содержит только отношения в третьей нормальной форме. Данная схема предоставляет пользователю возможность изменять любые значения одних отношений, не затрагивая других. Недостатком реляционной модели данных является избыточность по полям (из-за создания связей).
Программисту или пользователю необходимо иметь возможность обращаться к отдельным, нужным ему записям или отдельным элементам данных. В зависимости от уровня программного обеспечения прикладной программист может использовать следующие способы:
• Задать машинный адрес данных и в соответствии с физическим форматом записи прочитать значение. Это случай, когда программист должен быть «навигатором». • Сообщить системе имя записи или элемента данных, которые он хочет получить, и возможно, организацию набора данных. В этом случае система сама произведет выборку (по предыдущей схеме), но для этого она должна будет использовать вспомогательную информацию о структуре данных и организации набора. Такая информация по существу будет избыточной по отношению к объекту, однако общение с базой данных не будет требовать от пользователя знаний программиста и позволит переложить заботы о размещении данных на систему. В качестве ключа, обеспечивающего доступ к записи, можно использовать идентификатор – отдельный элемент данных. Ключ, который идентифицирует запись единственным образом, называется первичным (главным). В том случае, когда ключ идентифицирует некоторую группу записей, имеющих определенное общее свойство, ключ называется вторичным (альтернативным). Набор данных может иметь несколько вторичных ключей, необходимость введения которых определяется практической необходимостью – оптимизацией процессов нахождения записей по соответствующему ключу. Иногда в качестве идентификатора записи используют составной сцепленный ключ – несколько элементов данных, которые в совокупности, например, обеспечат уникальность идентификации каждой записи набора данных. Один из способов использования вторичного ключа в качестве входа – организация инвертированного списка, каждый вход которого содержит значение ключа вместе со списком идентификаторов соответствующих записей. Существует несколько различных способов адресации и поиска записей.
1. Последовательное сканирование файла. Наиболее простым способом локализации записи является сканирование файла с проверкой ключа каждой записи. Этот способ, однако, требует слишком много времени и может применяться, когда каждая запись все равно должна быть прочитана.
2. Блочный поиск.Если записи упорядочены по ключу, то при сканировании файла не требуется чтение каждой записи. ЭВМ могла бы, например, просматривать каждую сотую запись в последовательности возрастания ключей. При нахождении записи с ключом большим, чем искомое значение, просматриваются последние 99 записей, которые были пропущены. Этот способ называется блочным поиском. Записи группируются в блоки и каждый блок проверяется по одному разу до тех пор, пока не будет найден нужный блок. Иногда данный способ называется поиском с пропусками.
3. Двоичный поиск. При двоичном поиске в файле записей, упорядоченных по ключу, анализируется запись, находящаяся в середине поисковой области файла (изначально всего файла), а ее ключ сравнивается с поисковым ключом. Затем поисковая область делится пополам и процесс повторяется для соответствующей половины области, пока не будет обнаружено искомое значение или длина области не станет равной 1. Число сравнений в этом случае будет меньше, чем для случая блочного поиска. Двоичный поиск эффективен для поиска в файлах, организованных в виде двоичного дерева с указателями, когда поиск проходит в направлении, задаваемом указателями. Кроме того, добавление в файл новых записей не приводит к сдвигу других записей, что требует много времени и является достаточно сложной процедурой. Таким образом, двоичный поиск более пригоден для поиска в индексе файла, чем в самом файле. 4. Индексно-последовательные файлы. Если файл упорядочен по ключам, то для адресации может использоваться таблица, называемая индексом, связывающая ключ хранимой записи с ее относительным или абсолютным адресом во внешней памяти. Индекс можно определить как таблицу, с которой связана процедура, воспринимающая на входе информацию о некоторых значениях атрибутов и выдающая на выходе информацию, способствующую быстрой локализации записи или записей, которые имеют заданные значения атрибутов. Если записи файла упорядочены по ключу, индекс обычно содержит не ссылки на каждую запись, а ссылки на блоки записей, внутри которых можно выполнять поиск или сканирование. Хранение ссылок на блоки записей, а не на отдельные записи в значительной степени уменьшает размер индекса. Причем даже в этом случае индекс часто оказывается слишком большим для поиска, и поэтому используется индекс индекса. 5. Индексно-произвольные файлы. Произвольный (не упорядоченный по ключу) файл можно индексировать точно так же, как и последовательный файл. Однако при этом индекс должен содержать по одному элементу для каждой записи файла, а не для блока записей. Более того, в нем должны содержаться полные абсолютные (или относительные) адреса, в то время как в индексе последовательного файла адреса могут содержаться в усеченном виде, так как старшие знаки последовательных адресов будут совпадать. Произвольные файлы в основном используются для обеспечения возможности адресации записей файла с несколькими ключами. Если файл упорядочен по одному ключу, то он не упорядочен по другому ключу. Для каждого типа ключей может существовать свой индекс: для упорядоченных ключей индекс будет иметь по одному элементу на блок записей, для других ключей индексы буду более длинными, так как должны будут содержать по одному элементу для каждой записи. Ключ, который чаще всего используется при адресации файла, обычно служит для его упорядочения. В индексно-произвольных файлах часто используются символические, а не абсолютные адреса, так как при добавлении новых или удалении старых записей изменяется местоположение записей. Если в записях имеется несколько ключей, то индекс вторичного ключа может содержать в качестве выхода первичный ключ записи. При определении же местоположения записи по ее первичному ключу можно использовать какой-нибудь другой способ адресации. По этому методу поиск осуществляется медленнее, чем поиск, при котором физический адрес записи определяется по индексу. В файлах, в которых положение записей часто изменяется, символическая адресация может оказаться предпочтительнее.
6. Адресация с помощью ключей, преобразуемых в адрес. Известно много методов преобразования ключа непосредственно в значение адреса в файле. В тех случаях, когда возможно преобразование значения ключа непосредственно в значение адреса в файле, такой способ адресации обеспечивает самый быстрый доступ; при этом нет необходимости организовывать поиск внутри файла или выполнять операции с индексами. В некоторых приложениях адрес может быть вычислен на основе значений некоторых элементов данных записи. К недостаткам данного способа относится малое заполнение файла: в файле остаются свободные участки, поскольку ключи преобразуются не в непрерывное множество адресов. Другим недостатком схем прямой адресации является их малая гибкость. Машинные адреса записей могут измениться при обновлении файла. Для устранения этого недостатка прямую адресацию обычно выполняют в два этапа. Сначала ключ преобразуется в порядковый номер, который затем преобразуется в машинный адрес. 7. Хэширование. Простым и полезным способом вычисления адреса является хэширование (перемешивание). В данном методе ключ преобразуется в квазислучайное число, которое используется для определения местоположения записи. Более экономичным является указание на область, в которой размещается группа записей. Эта область называется участком записей (slot, bucket). При первоначальной загрузке файла адрес, по которому должна быть размещена запись, определяется следующим образом: 1. Ключ записи преобразуется в квазислучайное число, находящееся в диапазоне от 1 до числа участков, используемых для размещения записей.
2. Число преобразуется в адрес участка и, если на участке есть свободное место, то логическая запись размещается на нем.
3. Если участок заполнен, запись должна быть размещена на участке переполнения – следующий по порядку участок либо участок в отдельной области переполнения. При чтении записей из файла их поиск выполняется аналогично, причем может оказаться, что для поиска записи потребуется чтение нескольких участков переполнения. Из-за вероятностей природы алгоритма в этом способе не удалось достичь 100% плотности заполнения памяти, однако для большинства файлов может быть достигнута плотность 80 или 90%; при этом память для индексов не требуется. Большинство записей можно найти за одно обращение, но для некоторых потребуется второе обращение (при переполнении). Для очень небольшой части записей потребуется третье или четвертое обращение к файлу. Кроме того, в этом случае менее эффективно используется память, чем в индексных методах; записи не упорядочены для последовательной обработки. 8. Комбинации способов адресации. При адресации записей некоторых файлов используются комбинации перечисленных выше способов. Например, с помощью индекса может определяться ограниченная поисковая область файла, затем эта область просматривается последовательно, либо в ней выполняется двоичный поиск. С помощью алгоритма прямой адресации может определяться нужный раздел индекса и, таким образом, исчезает необходимость поиска во всем индексе.
Понятие ключа и индекса. Прямая и инвертированная формы индекса. Примеры.
Ключ – значение (элемент данных), используемое для идентификации или определения адреса записи. (логическое определение).
Ключ сцепленный (составной) – несколько элементов данных, которые в совокупности обеспечивают уникальность идентификации каждой записи набора данных. Индекс – физическая реализация ключа, обеспечивающая доступ к записям, соответствующим отдельным значениям ключа.
Логически индекс есть бинарное отношение I(v,a), где v – значение атрибута, а a – список адресов элементов хранения (записей, кортежей, документов), соответствующих данному значению атрибута. Для повышения эффективности поиска отдельных значений и слияния/пересечения списков значения v и адреса элементов в списке a хранятся в упорядоченном виде, что обеспечивает применение процедур быстрого поиска. Индекс I(v,a) часто называют инвертированным индексом. Каждый элемент а инвертированного индекса наз. инвертированным списком.
Прямая реализация индекса представляет собой расширение бинарного отношения до совокупности записей, состоящих из 2-ух полей – значения атрибута и адреса размещения одного элемента хранения. Отдельное значение атрибута повторяется в индексе столько раз, сколько оно встречается в файле данных, а длина индекса (в записях) совпадает с длиной файла данных.
В инвертированной форме:
В случае, когда списки а достаточно длинные, инвертированный индекс хранится в двух разных файлах, связанных указателями. Такая организация требует меньше памяти для хранения значений ключей и поиск в ней более эффективен. Способы реализации указателя пересылок:
- Указанием ссылки на первый и последний адреса размещения элементов для отдельного ключевого значения; - Заданием ссылки на адрес размещения первого элемента и длиной списка адресов.
Пример:
Сходство и отличие процессов обработки данных средствами файловой системы и системы управления (СУ) базы данных (БД).
Приведем основные отличительные особенности обработки данных, характерные для файловых систем и СУБД. Файлы обладают следующими свойствами: • файл, как правило, представляет собой совокупность записей одного типа, доступ к которым определяется типом организации файла и осуществляется только средствами операционной системы;
• файл описывают и используют в прикладной программе, работающей с данными. База данных имеет следующие особенности:
• база данных представляет собой совокупность данных разного типа, причем часто по одним данным получают другие;
• база данных существует независимо от конкретной прикладной программы – база оздается с целью интеграции данных, объединяющей данные многих приложений (но определенного назначения). База данных предназначена для совместного, многофункционального использования многими пользователями один раз введенных данных. Надо отметить, что с точки зрения управления данными СУБД оперирует данными на содержательном уровне, хотя физические структуры, используемые для этих целей, могут совпадать с аналогичными структурами, создаваемыми ОС. Коренное же отличие СУБД от файловых систем ОС состоит в том, что СУБД устанавливает связь между содержанием и адресом, а ОС – между именем и адресом данных. В то же время эта граница постоянно подвергается «атакам» с обеих сторон. Например, ОС-360 с «индексным доступом к данным», IN-PICK, включающая язык поиска записи файлов по содержанию, UNIX, включающая команды коррекции, сортировки или объединения содержимого текстовых файлов, наподобие того, как это осуществляется с таблицами данных в СУБД. Тем не менее, следует признать это скорее исключением, чем правилом и в компетенцию ОС надо относить только связь «имя-адрес», оставляя другие зависимости на ответственность прикладных программ и оболочек СУБД и АИПС автоматизированные информационно-поисковые системы).
Характерные свойства и отличия линейных и нелинейных структур. Нелинейные структуры. Примеры.
К линейным структурам относятся массивы и последовательности, таблицы. Порядок следования (и, соответственно, выборки) элементов таких структур имеет линейный характер и соответствует порядку расположения элементов в памяти: один за другим без каких-либо промежутков. Адрес элемента соответствует его положению и определяется индексом – порядковым номером элемента в последовательности размещения. К элементу имеется прямой доступ, если известен его индекс. Особенностью линейной структуры является то, что при последовательной организации (размещении) она допускает возможность прямого доступа к произвольному элементу, поскольку условие однородности (однотипности) предполагает, что все элементы занимают расположенные строго последовательно области одинакового размера, что и позволяет достаточно просто вычислять значение физического адреса элемента по значению его индекса. Массив представляет собой совокупность однотипных элементов, причем число элементов массива известно до его размещения, что позволяет строить гибкие многомерные системы адресации.
Последовательность, так же, как и массив, представляет собой совокупность однотипных элементов. Однако число элементов до размещения неизвестно. И, хотя каждая конкретная последовательность имеет конечную длину, до начала обработки (и, соответственно, размещения) необходимо считать длину последовательности бесконечной. Принципиальность такого предположения выражается в том, что необходимо предусматривать специальную процедуру использования памяти (выделения/освобождения) и, возможно, алгоритм обработки последовательности по частям. Важность рассмотрения такого типа данных обусловлена тем, что именно он превалирует операциях ввода/вывода с устройствами внешней памяти. Именно последовательный доступ позволяет организовать «потоковые» операции: однородность позволяет рассматривать пересылаемые данные как непрерывный поток. Поток не может быть прерван по контекстно определяемому условию, например, при пересылке текста – по значению кода «первой строки», и это не заставляет программу анализировать значение каждого очередного элемента. И, кроме того, последовательный доступ – это простота управления памятью и устройством ввода-вывода.
Таблица – это последовательности, обычно представляемые строками – совокупностями разнотипных элементов. Или, иначе, таблица – это множество записей, каждая из которых представляет набор поименованных полей. Однако с точки зрения размещения элементов таблица может быть представлена как одномерный массив (или, в случае БД – последовательность)) с однородными композиционными элементами, каждый из которых представляет собой совокупность разнотипных элементов. Именно это позволяет свести ввод/вывод таких типов структур к последовательным элементарным операциям. Кроме того, разнотипность элементов позволяет ввести отличную от перечислительной схему идентификации записей, определив одно из полей как ключ записи. Обычно ключ содержит значение, используемое в процедурах упорядочения и поиска записей. Линейные — структуры данных, в которых переход от одного элемента данных к другому не зависит от каких-либо логических условий, т.е. в линейных структурах используются лишь безусловные связи элементов; нелинейные — структуры данных, в которых переход от одного элемента данных к другому может зависеть от выполнения некоторого логического условия, т.е. в нелинейных структурах могут использоваться условные связи элементов. В качестве примеров нелинейных структур рассмотрим списки, деревья и сети. Порядок следования (и, соответственно, выборки) элементов таких структур может не соответствовать порядку расположения элементов в памяти. Списки представляют собой пример линейного упорядочения, деревья – двумерного, сети – произвольного. Соответственно различаются методы и средства, обеспечивающие последовательность выборки элементов данных. Обычно для обеспечения возможности прямого доступа к произвольному элементу необходимо использовать вспомогательные структуры типа инвертированных списков. Списки. Как и массив, список представляет собой совокупность однотипных элементов. Однако порядок выборки элементов может отличаться от порядка следования в памяти, определенного при размещении. Наиболее очевидный способ установления однонаправленного порядка выборки элементов – это сопоставить каждому элементу списка ссылку, указывающую на следующий элемент. Соответственно, для организации двунаправленного списка, допускающего также выборку в обратном порядке, каждый элемент должен иметь ссылку на предыдущий. Такая организация уже не допускает возможности прямого доступа, например, по номеру элемента. Кроме того, число элементов списка, как и в случае последовательностей, может быть неизвестно до размещения, и до начала обработки (и, соответственно, размещения) необходимо считать длину списка бесконечной, что ведет к необходимости предусматривать специальную процедуру выделения/освобождения памяти. Таким образом, с точки зрения физической реализации элемент списка должен быть составным, включающим собственно информативные данные, несущие смысловое значение, и дополнительные данные (ссылки), определяющие порядок доступа к информативным элементам. Понятие списка достаточно универсально. В общем случае ссылки могут указывать ответвления к другим спискам – подспискам. В зависимости от способа построения списка и предполагаемых путей доступа к элементам различают следующие виды ссылок: перекрестные, боковые, иерархические, множественные, что позволяет изменять «естественный» последовательный порядок прохода по элементам списка. Деревья. Дерево представляет собой иерархию элементов, называемых узлами. На самом верхнем уровне иерархии имеется только один узел – корень. Каждый узел, кроме корня, связан с одним узлом на более высоком уровне, называемым исходным узлом для данного узла. Каждый элемент имеет только один исходный. Каждый элемент может быть связан с одним или несколькими элементами на более низком уровне, которые называются порожденными. Элементы, расположенные в конце ветви, т.е. не имеющие порожденных, называются листьями. Существует несколько способов представления структуры дерева. Например, дерево может быть определено как иерархия узлом с попарными связями, в которой: 1. Самый верхний уровень иерархии имеет один узел, называемый корнем. 2. Все узлы, кроме корня, связываются с одним и только одним узлом на более высоком уровне по отношению к ним самим. Такое определение в части организации связей совпадает со списком, и, в частности, список представляет вырожденный случай дерева, в котором каждая вершина имеет не более одного поддерева. В логическом описании данных деревья используются для определения связей между элементами структуры, а при определении физической организации данных – для определения набора указателей, реализующих связи между ними. Использование ссылок для организации доступа к отдельным элементам структуры не позволяет сократить процедуру поиска, в основу которой положен последовательный перебор. Процедура поиска будет эффективнее, если будет предварительно установлен некоторый порядок перехода к следующему элементу дерева. Такой порядок в ряде случаев определяется в отношении метода обхода и регулярности итераций, определяемой длиной пути и кратностью деления вершины. Выделяют три метода обхода: сверху вниз, слева направо, снизу вверх. Регулярность обхода дерева может быть связана с упорядоченными деревьями, к которым относятся сбалансированные и двоичные деревья. Сбалансированное дерево в каждом узле имеет одинаковое число ветвей, причем процесс включения новых ветвей в узлы дерева идет сверху вниз, а на каждом уровне дерева – слева направо. Для дерева с фиксированным числом ветвей физическая организация данных будет более простой. Однако большая часть логических организаций данных не может быть задана в виде сбалансированной древовидной структуры, и для их представления требуется переменное число ветвей в каждом узле. В то же время индексы могут быть построены в виде сбалансированных древовидных структур. Двоичные деревья – это особая категория сбалансированных древовидных структур, в которой допускается не более двух ветвей для одного узла. Любые связи в дереве можно представить в виде двоичных древовидных структур. При таком представлении каждый элемент может иметь указатель как на порожденные, так и на подобные элементы. Различные виды двоичных деревьев, для которых характерно наличие жесткой схемы управления их ростом, достаточно эффективно используется для построения больших поисковых индексов, размещаемых обычно на устройствах внешней памяти. Кроме того, для таких деревьев можно организовать специальное «страничное» хранение поддеревьев, что сократит число физических обращений к устройству. Деревья поисковых индексов являются однородными структурами: каждый узел представлен элементами одного типа. Однако большинство баз должно поддерживать организацию данных, имеющих различную природу. В этом случае при работе с неоднородными структурами разной глубины, гарантировать регулярность, обеспечивающую эффективность процедур доступа, становится затруднительно. В сетевой структуре любой элемент может быть связан с любым другим элементом. Так же, как и в древовидных структурах, сетевую структуру можно описать с помощью исходных и порожденных элементов. Удобно представлять ее так, чтобы порожденные элементы располагались ниже исходных. При рассмотрении некоторых сетевых структур естественно говорить об уровнях, так же как и в случае древовидных структур. Во многих сетевых структурах, задающих связи между элементами, представление отношений между исходными и порожденными элементами аналогично представлению отношений в случае дерева: отношение исходный-порожденный является сложным (указывается сдвоенными стрелками), а отношение порожденный-исходный – простым (указывается одинарными стрелками). В некоторых случаях один элемент данных может быть связан с целой совокупностью других элементов данных. Например, одно изделие может поставляться несколькими поставщиками, каждый из которых установил свою цену на это изделие. Элемент данных ЦЕНА не может быть ассоциирован только с элементом ИЗДЕЛИЕ или только с элементом ПОСТАВЩИК, а должен быть связан одновременно с двумя. Информация такого рода, т.е. данные, ассоциированные с совокупностью элементов, называют иногда данными пересечения. Некоторые структуры содержат циклы. Циклом считается ситуация, в которой предшественник узла является в то же время его последователем. Отношения «исходный-порожденный» образуют при этом замкнутый контур. Например, завод выпускает различную продукцию. Некоторые изделия производятся на других заводах-субподрядчиках. С одним контрактом может быть связано производство нескольких изделий. Представление этих отношений и образует цикл. Иногда элементы связаны с другими элементами того же типа. Такая ситуация называется петлей. В массиве служащих специфицированы связи, существующие между некоторыми служащими. В базу данных списка материалов введено дополнительное усложнение: некоторые узлы сами состоят из узлов. Разделение сетевых структур на простые и сложные необходимо потому, что сложные структуры требуют более сложных методов физического представления. Это не всегда является недостатком, поскольку сложную сетевую структуру можно (а в большинстве случаев и следует) преобразовать к простому виду.
