Теория и практика построения баз данных (1088289), страница 161
Текст из файла (страница 161)
Данный факт можно представить в виде индекса, изображенного на рис. А.24. Этот индекс связывает адрес родителя с адресами каждого из ега потомков. Рнс. А.24. Представление саван ПОСТАВЩИК-СЧЕТ с помощью индексов Если дерево имеет несколько связей 1:)Ч, потребуется несколько индексов, па одному на каждую связь. Для структуры на рис. А.13 потребуется пять индексов. Представление простых сетей Как и деревья, простые сети могут быть представлены с помощью связных спи- сков и индексов. деревьев. Рассмотрим, например, простую сеть, изображенную на рис.
А.25. Она имеет две связи 1;Х: одна между записями ГРУЗОВИК и ДОСТАВКА, а другая — между записями ДОСТАВКА и КЛИЕНТ. Каждую из зтих связей можно хранить в виде индекса. На рис. А.28 показаны два индекса, с помощью которых можно представить пример на рис. А.26. Будем предполагать, что записи находятся на тех же позициях, что и на рис.
А.27, Содержимое записи Поля ссылок Рис. А.25. Структура простой сети Ссылки Ссылки на клиентов на грузовики Рис. А.27. Представление простой сети с помощью связных списков Запись Запись о машине о доставке Запись Запись о клиенте о доставке Рис. А.26. Представление простой сети с помощью индексов Представление сложных сетей Сложньге сети могут быть представлены лгножеством способов. Их можно разбивать на деревья или простые сети, а уже зги простые структуры представлять с помощью одной из рассмотренных только что методик.
Кроме того, их можно представлять непосредственно с помощью индексов. Связные списки не используются СУБД для непосредственного представления сложных сетей. На практике сложные сети почти всегда разбиваются на более простые структуры, позтому далее мы будем рассматривать только такие представления. Распространенный подход к представлению сложной сети состоит в сведении ее к простой сети и последующем представлении получившейся простой 744 Приложение А. Структуры данных Представление простых сетей с помощью связных спискОВ Рассмотрим простую сеть, изображенную на рис. А.25. Прежде всего, зта структура действительно является простой сетью, поскольку все связи в ней имезот вид 1:Х, а записи типа ДОСТАВКА имеют родителей различных типов.
Каждая запись типа ДОСТАВКА имеет в качестве родителей запись типа КЛИЕНТ и запись типа ГРУЗОВИК. Связь между записями КЛИЕНТ и ДОСТАВКА имеет вид 1 гн, поскольку одному клиенту может доставляться несколько заказов, Связь между записями ГРУЗОВИК и ДОСТАВКА также имеет вид 1:п(, поскольку различные заказы могут доставляться одним и тем же грузовиком (если считать, что размеры доставляемых товаров достаточно малы, чтобы поместиться на одном грузовике). Эзстеззпляр такой сети показан на рис.
А.26. Рис. А.26. Пример простой сети со структурой, соответствующей рис. А.25 Чтобы представить простую сеть с помощью связных списков, для каждой связи 1:Тч нужно создать набор указателей. В данном случае это означает, что нужно создать один набор указателей, связываюшпй записи КЛИЕНТ и ДОСТАВКА, и один набор указателей, связываюшяй записи ДОСТАВКА и ГРУЗОВИК.
Так, например, запись КЛ И ЕНТ будет содержать один указатель (на первую связаннуго с ней запись ДОСТАВКА), запись ГРУЗОВИК будет содержать один указатель (на первую связанную с ней запись ДОСТАВКА), а запись ДОСТАВКА будет иметь два указателя; один — на следующую запись ДОСТАВКА, принадлежащую той же записи КЛИЕНТ, и на следуюшую запись ДОСТАВКА, приналлежашую той же записи ГРУЗОВИК. Эта схема изображена на рпс. А.27. Простая сеть имеет по меныией мере две связи 1:и(, каждая из которгях может быть представлена с помошью индекса, как было показано в ходе обсуждения Относительный номер записи 1 2 3 4 5 6 7 6 9 10 Представление бинарных связей 745 Обратите внимание, что связь записей СТУДЕНТ и ЗАНЯТИЕ с записью пересечения имеет внд 1:Тч.
Таким образом, мы создали простую сеть, которую можно представить с помощью связных списков илн индексов, как было показано ранее. Файл с примером такой простой сети, для представления которой используются связные списки, изображен па рис. А.31. Относительный номер записи Содержимое записи Поле ссылки Ссылки Ссылки на студентов на предметы Рио. А.З1. Пример сети со структурой, соответствующей рис.
А.зо Резюме по представлению связей Па рис. А.32 изображены все способы представления связей между записями. Деревья могут быть представлены с помощью последовательных ст1нсков (хотя мы не обсуждали этот подход), связных списков или индексов. Последовательные списки не используются в СУБД. Простую сеть можно разбить на деревья и затем представить с помощью соответствующих структур данных, а можно представить непосредственно с помощью связных списков или индексов. Сложную сеть можно преобразовать в дерево или в простую сеть (с помощью записей пересечения) либо представить непосредственно с помощью индексов.
746 Приложение А, Структуры данных сети с помощью связных списков нли индексов. Обратите, однако, внимание, что связи в сложной сети соединяют между собой две записи, а в простой сети — три записи. Поэтому, чтобы преобразовать сложную сеть в простую, требуется создать третий тип записи. Запись, создаваемая при преобразовании сложной сети в простую, называется записью пересечения (шгегзесг1оп гесогт1). Рассмотрим сложную сеть, отражающую посещение занятий студентами. Запись пересечения будет содержать уникальный ключ записи СТУДЕНТ и уникальный ключ соответствующей ей записи ЗАНЯТИЕ.
Запись пересечения не будет содержать никаких друптх данных приложения, хотя в ней могут быть поля ссылок. Общая структура этой связи показана на рис. А.29. Экземпляр связи СТУДЕНТ-ЗАНЯТИЕ представлен на рис. А,ЗО (здесь предполагается, что имена записей, обозначенные С1, 31 и т, д,, являются уникальными). Рио. А.29. Преобразование сложной сети в простую Рис. А.ЗО. Экземпляр связи СТУДЕНТ-ЗАНЯТИЕ с записями пересечения 7 8 9 10 11 12 13 14 15 16 17 16 19 20 Представление бинарных связей 747 Индексы же могут использоваться для представления как уникальных, так и не- уникальных ключей, Представление вторичных ключей с помощью СВЯЗНЫХ СПИСКОВ Вид связи между записями Рассмотрим файл КЛИЕНТ, структура которого показана на рис.
А.ЗЗ. Первичным ключом является НомерСчета; есть также вторичный ключ, МаксимальныйКредит. Возможные значения поля МаксимальныйКредит — 500, 700 и 1000. Таким образом, у нас будет три набора записей: с максимальным кредитом 500, 700 и 1000. НомерСчета Имя Адрес МакскмальиыйКредит ОстатокНаСчете ПереичныйКлюч ВторичныйКлюч Рис.
А.ЗЗ. Структура файла КЛИЕНТ Структуры данных Чтобы представить этот вторичный ключ с помощью связных списков, добавим в структуру файла КЛИЕНТ поле ссылки. В этом поле ссылки мы создадим связный список для каждого набора записей. На рис. А.З4 показана база данных с одиннадцатью клиентами, где для краткости показаны только поля НомерСчета и МаксимальныйКредит. К каждой записи добавлено поле ссылки. Предположим, что одна запись в базе данных соответствует физической записи в файле прямого доступа, использующем относительную адресацию записей.
Принцип доступа к файлу Максимальный- Прочие Кредит данные Относительный Номер- номер записи Ссылка Счета 1 2 3 4 НАЧАЛО-500 = 1 НАЧАЛО-700 = 3 НАЧАЛО-1000 = 4 Рис. А.З4. Представление вторичного ключа МаксимальныйКредит с помощью связного списка Чтобы знать, где начинается каждый связный список, нужны три указа~ела. Каждый такой указатель называется головой списка (леан) и хранится отдельно от данных. Головой связного списка покупателей с максимальным кредитом 3500 является запись с относительным номером 1. Запись 1 указьлвает на запись 2, 748 Приложение А. Структуры данных Обычно — — ---- — - Редко Рис. А.З2.
Представление связей между записями с помощью различных структур данных и принципов доступа Представление вторичных ключей Во многих случаях терлеином ключ обозначается одно плн несколько полей, уникальным образом идентифицирующих запись. Такой ключ обычно называется первичным ключом.
Но иногда приложениям нужно обращаться к записям и обрабатывать их по впгоричлому ключу, который обладает иными свойствами, чем первичный. Вторичный ключ может быть уникальным (например, имя преподавателя) или неуникальным (например, почтовый индекс клиента). В этом разделе термином множество (зес) мы будем обозначать все записи, имеющие одинаковое значение неуникального вторичного ключа; например, множество записей, в которых поле Индекс имеет значение 98040. Для представления вторичных ключей можно использовать и связные списки, и индексы, но связные списки пригодны только в случае неуникальных ключей, 5 6 6 9 10 11 Представление вторичных ключей 749 750 Приложение А.
Структуры данных Представление вторичных ключей 751 которая, в свою очередь, указывает на запись 7. Запись 7 имеет нулевое значение в поле ссылки, указывающее на то, что это конец списка, Следовательно, множество записей клиентов с максимальным кредитом 3500 состоит из записей с относительными номерами 1, 2 п 7, Аналогичным образом множество записей клиентов с максимальным кредитом $700 состоит из записен с относительными номерами 3, 5 и 10, а множество записей клиентов с максимальным кредитом $1000 состоит из записей с относительными номерами 4, 6, 8, 9 и 11. Возьмем для примера запрос сколько счетов с максимальным кредитом 31000 имеют баланс, превышающий 3900?.
Чтобы ответить на подобньш запрос, можно использовать связный список записей с максимальным кредитом $1000. При этом считывать из файла и обрабатгявать нужно только те записи, которые принадлежат множеству с максимальным кредитом 31000. Хотя преимущество этого подхода не ощущается явно в этом небольшом примере, представьте, что есть 100 000 записей КЛИЕНТ, и только 100 из них принадлежат искомому множеству. Если бы связного списка не было, пришлось бы провести поиск пп всем 100 000 записям; при наличии же связного списка требуется обработать только 100 записей, а именно записи из множества с максимальным кредитом $1000.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
