Файл: 1. Введение в теорию баз данных Вопрос Основные понятия.docx
Добавлен: 05.12.2023
Просмотров: 548
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Сбалансированное дерево в каждом узле имеет одинаковое число ветвей, причем процесс включения новых ветвей в узлы дерева идет сверху вниз, а на каждом уровне дерева — слева направо. Для дерева с фиксированным числом ветвей физическая организация данных будет более простой. Однако большая часть логических организаций данных не может быть задана в виде сбалансированной древовидной структуры, и для их представления требуется переменное число ветвей в каждом узле. В то же время индексы могут быть построены в виде сбалансированных древовидных структур.
Двоичные деревья - это особая категория сбалансированных древовидных структур, в которой допускается не более двух ветвей для одного узла. На рис. 17 показано несбалансированное двоичное дерево.
Рис. 17. Пример несбалансированного двоичного дерева
Любые связи в дереве можно представить в виде двоичных древовидных структур. Рис. 18 иллюстрирует представление дерева в виде двоичного дерева.
Рис. 18. Пример представления дерева в виде двоичного
При таком представлении каждый элемент может иметь указатели как на порожденные, так и на подобные элементы.
Различные виды двоичных деревьев, для которых характерно наличие жесткой схемы управления их ростом, достаточно эффективно используются для построения больших поисковых индексов, размещаемых обычно на устройствах внешней памяти. Кроме того, для таких деревьев можно организовать специальное «страничное» хранение поддеревьев, что сократит число физических обращений к устройству. Заметим, что деревья поисковых индексов являются однородными структурами: каждый узел представлен элементами одного типа. Однако большинство баз должно поддерживать организацию данных, имеющих различную природу. В этом случае при работе с неоднородными структурами разной глубины, гарантировать регулярность, обеспечивающую эффективность процедур доступа, становится затруднительно.
Сетевые структуры.
Иерархические структуры характерны для многих областей, однако во многих случаях отдельная запись требует более одного представления или связана с несколькими другими. В результате получаются обычно более сложные структуры по сравнению с древовидными. Например, генеалогическое дерево может быть представлено в виде древовидной структуры, только если для каждого элемента (личности) будет показан только один исходный элемент (родитель). Если бы были показаны оба родителя, то это была бы более сложная структура.
В сетевой структуре любой элемент может быть связан с любым другим элементом.
Рис. 19. Пример сетевых структур
Так же как и в случае древовидных структур, сетевую структуру можно описать с помощью исходных и порожденных элементов. Удобно представлять ее так, чтобы порожденные элементы располагались ниже исходных. При рассмотрении некоторых сетевых структур естественно говорить об уровнях, так же как и в случае древовидных структур.
Во многих сетевых структурах, задающих связи между элементами, представление отношений между исходными и порожденными элементами аналогично представлению отношений в случае дерева:
· отношение исходный-порожденный является сложным (указывается сдвоенными стрелками),
· отношение порожденный-исходный - простым (указывается одинарными стрелками).
На рис. 20 показана неоднородная сетевая структура с пятью типами элементов. Ни одна из их соединяющих линий не имеет сдвоенных стрелок в обоих направлениях. Каждое отношение может рассматриваться как отношение «исходный-порожденный».Запись ЗАКАЗ-НА-ЗАКУПКУ является порожденной по отношению к записи ИЗДЕЛИЕ и исходной по отношению к записи ПАРТИЯ-ТОВАРА.
Рис. 20. Пример простой сетевой структуры
Желательно отличать структуры, в которых представление отношений «порожденный-исходный» является простым или не используется, от структур, в которых представление отношений между какими-то двумя типами данных является сложным в обоих направлениях.
Для структур второго типа на одной из линий схемы будут сдвоенные стрелки, указывающие в разные стороны. Этот тип схемы назовем
сложной сетевой структурой,
Схему, в которой ни на одной из линий нет сдвоенных стрелок в обоих направлениях,- простой сетевой структурой. На рис. 20 показана простая сетевая структура. Она станет сложной, если ввести отношение ЗАКАЗ-НА-ЗАКУПКУ - ИЗДЕЛИЕ, когда один заказ может быть сделан сразу на несколько изделий. Для образования сложной сетевой структуры достаточно двух типов элементов. Например, ПОСТАВЩИК может иметь несколько порожденных записей, потому что может поставляться более одного вида изделий. С другой стороны, элемент ИЗДЕЛИЕ может иметь более одного исходного элемента, поскольку это изделие может поставляться различными поставщиками.
В некоторых случаях один элемент данных может быть связан с целой совокупностью других элементов данных. Например, одно изделие может поставляться несколькими поставщиками, каждый из которых установил свою цену на это изделие. Элемент данных ЦЕНА не может быть ассоциирован только с элементом ИЗДЕЛИЕ или только с элементом ПОСТАВЩИК, а должен быть связан одновременно с двумя. Информация такого рода, т. е. данные, ассоциированные с совокупностью элементов, называют иногда данными пересечения.
Некоторые структуры содержат циклы. Циклом считается ситуация, в которой предшественник узла является в то же время его последователем. Отношения «исходный-порожденный» образуют при этом замкнутый контур.
Например, завод выпускает различную продукцию. Некоторые изделия производятся на других заводах-субподрядчиках. С одним контрактом может быть связано производство нескольких изделий. Представление этих отношений и образует цикл.
Иногда элементы связаны с другими элементами того же типа. Такая ситуация называется петлей. На рис. 21 приведены две достаточно распространенные ситуации, где могут использоваться петли. В массиве служащих специфицированы связи, существующие между некоторыми служащими. В базу данных списка материалов введено дополнительное усложнение: некоторые узлы сами состоят из узлов.
Рис. 21. Пример сетевой структуры с петлей
Разделение сетевых структур на простые и сложные необходимо потому, что сложные структуры требуют более сложных методов физического представления. Это не всегда является недостатком, поскольку сложную сетевую структуру можно (а в большинстве случаев и следует) преобразовать к простому виду.
Вопрос 6. Реляционная модель данных.[10]
Реляционная[11] модель является удобной и наиболее привычной формой представления данных в виде таблицы. В отличие от иерархической и сетевой модели, такой способ представления 1) понятен пользователю-непрограммисту; 2) позволяет легко изменять схему - присоединять новые элементы данных и записи без изменения соответствующих подсхем; 3) обеспечивает необходимую гибкость при обработке непредвиденных запросов. К тому же любая сетевая или иерархическая схема может быть представлена двумерными отношениями.
Одним из основных преимуществ реляционной модели является ее однородность. Все данные рассматриваются как хранимые в таблицах, в которых каждая строка имеет один и тот же формат. Каждая строка в таблице представляет некоторый объект реального мира или соотношение между объектами. Пользователь модели сам должен для себя решить вопрос, обладают ли соответствующие сущности реального мира однородностью. Этим самым решается проблема пригодности модели для предполагаемого применения.
Основными понятиями, с помощью которых определяется реляционная модель, являются следующие: домен, отношение, кортеж, кардинальность, атрибуты, степень, первичный ключ. Соотношение этих понятий иллюстрируется рис. 22. Эти понятия представляют специальную терминологию, введенную авторами теоретических основ, однако они имеют и более привычные аналоги (но не во всем эквиваленты!), соответствие которых приведено в следующей таблице 4.
Таблица 4.
| Домен | Совокупность допустимых значений |
| Кортеж | Строка таблицы |
| Кардинальность | Количество строк в таблице |
| Атрибут | Поле, столбец таблицы |
| Степень отношения | Количество полей (столбцов) |
| Первичный ключ | Уникальный идентификатор |
Домен – это совокупность значений, из которой берутся значения соответствующих атрибутов определенного отношения. С точки зрения программирования домен - это тип данных, определяемый системой (стандартный) или пользователем.
Первичный ключ - это столбец или некоторое подмножество столбцов, которые уникально, т.е. единственным образом определяют строки. Первичный ключ, который включает более одного столбца, называется множественным, или комбинированным, или составным. Правило целостности объектов утверждает, что первичный ключ не может быть полностью или частично пустым, т.е. иметь значение null.
Остальные ключи, которые можно также использовать в качестве первичных, называются потенциальными или альтернативными ключами.
Внешний ключ - это столбец или подмножество одной таблицы, который может служить в качестве первичного ключа для другой таблицы. Внешний ключ таблицы является ссылкой на первичный ключ другой таблицы. Правило ссылочной целостности гласит, что внешний ключ может быть либо пустым, либо соответствовать значению первичного ключа, на который он ссылается. Внешние ключи являются неотъемлемой частью реляционной модели, поскольку реализуют связи между таблицами базы данных.
Внешний ключ, как и первичный ключ, тоже может представлять собой комбинацию столбцов. На практике внешний ключ всегда будет составным (состоящим из нескольких столбцов), если он ссылается на составной первичный ключ в другой таблице. Очевидно, что количество столбцов и их типы данных в первичном и внешнем ключах совпадают.
Если таблица связана с несколькими другими таблицами, она может иметь несколько внешних ключей.
Модель предъявляет к таблицам следующие требования:
1) данные в ячейках таблицы должны быть структурно неделимыми;
2) данные в одном столбце должны быть одного типа;
3) каждый столбец должен быть уникальным (недопустимо дублирование столбцов);
4) столбцы размещаются в произвольном порядке;
5) строки размещаются в таблице также в произвольном порядке;
6) столбцы имеют уникальные наименования.
Рис. 22. Основные понятия реляционной модели
В целом концепция реляционной модели определяется следующими двенадцатью правилами Кодда:
1. Правило информации. Вся информация в базе данных должна быть предоставлена исключительно на логическом уровне и только одним способом - в виде значений, содержащихся в таблицах.