Хомоненко А.Д., Цыганков В.М., Мальцев М.Г. - Базы данных. Учебник для высших учебных заведений (6-е изд.) - 2009, страница 12

3.3. Одноуровневая схема индексацииБлок — N3. Реляционнаямодельданных55В каждом блоке записи располагаются в порядке возрастания значенияключа или свертки. Старшим ключом каждого блока является ключ егопоследней записи.Если в индексном файле хранятся хеш-коды ключевых полей индексированной таблицы, то алгоритм поиска нужной записи (с указанным ключом)в таблице включает в себя следующие три этапа.1. Образование свертки значения ключевого поля искомой записи.2. Поиск в индексном файле записи о блоке, значение первого поля которого больше полученной свертки (это гарантирует нахождение искомойсвертки в этом блоке).3. Последовательный просмотр записей блока до совпадения сверток искомой записи и записи блока файла. В случае коллизий сверток ищется запись, значение ключа которой совпадает со значением ключа искомой записи.Основным недостатком одноуровневой схемы является то, что ключи(свертки) записей хранятся вместе с записями.

Это приводит к увеличениювремени поиска записей из-за большой длины просмотра (значения данныхв записях приходится пропускать).Двухуровневаясхема в ряде случаев оказывается более рациональной,в ней ключи (свертки) записей отделены от содержимого записей (рис. 3.4).Блок ключей — 1Рис. 3.4. Двухуровневая схема индексации56Часть 1. Основы построениябазданныхВ этой схеме индекс основной таблицы распределен по совокупности файлов:одному файлу главного индекса и множеству файлов с блоками ключей.На практике для создания индекса для некоторой таблицы БД пользователь указывает поле таблицы, которое требует индексации. Ключевые полятаблицы во многих СУБД как правило индексируются автоматически.

Индексные файлы, создаваемые по ключевым полям таблицы, часто называются файлами первичных индексов.Индексы, создаваемые пользователем для не ключевых полей, иногда называют вторичными (пользовательскими)индексами. Введение такихиндексов не изменяет физического расположения записей таблицы, но влияет на последовательность просмотра записей. Индексные файлы, создаваемые для поддержания вторичных индексов таблицы, обычно называютсяфайлами вторичных индексов.Связь вторичного индекса с элементами данных базы может быть установлена различными способами. Один из них — использование вторичногоиндекса как входа для получения первичного ключа, по которому затемс использованием первичного индекса производится поиск необходимых записей (рис. 3.5).Рис. 3.5. Способ использования вторичных индексовНекоторыми СУБД, например Access, деление индексов на первичные ивторичные не производится.

В этом случае используются автоматически создаваемые индексы и индексы, определяемые пользователем по любому изне ключевых полей.Главная причина повышения скорости выполнения различных операцийв индексированных таблицах состоит в том, что основная часть работы про-3. Реляционнаямодельданных57изводится с небольшими индексными файлами, а не с самими таблицами.Наибольший эффект повышения производительности работы с индексированными таблицами достигается для значительных но объему таблиц. Индексирование требует небольшого дополнительного места на диске п незначительных затрат процессора па изменение индексов в процессе работы.Индексы в общем случае могут изменяться перед выполнением запросов кБД, после выполнения запросов к БД, по специальным командам пользователя или программным вызовам приложений.3 .

3 . Связывание таблицПри проектировании реальных БД информацию обычно размещают в нескольких таблицах. Таблицы при этом связаны семантикой информации.В реляционных С У Б Д для указания связей таблиц производят операциюих связывания.Укажем выигрыш, обеспечиваемый в результате с в я з ы в а н и я таблиц.Многие С У Б Д при связывании таблиц автоматически выполняют контрольцелостности вводимых в базу данных в соответствии с установленными связями.

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

Логическое связывание таблиц производится с помощью ключа связи.К/поч связи, по аналогии с обычным ключом таблицы, состоит из одногоили нескольких полей, которые в данном случае называют полями связи (Г1С).Суть связывания состоит в установлении соответствия полей связи основной и дополнительной таблиц.

Поля связи основной таблицы могут бытьобычными и ключевыми. В качестве полей связи подчиненной таблицы чащевсего используют ключевые поля.Часть 1. Основы58построениябазданныхВ зависимости от того, как определены поля связи основной и дополнительной таблиц (как соотносятся ключевые поля с полями связи), между двумя таблицами в общем случае могут устанавливаться следующие четыре основных вида связи (табл.

3.2):• один — один (1:1);• один — много (1:М);• много — один (М: 1);• много — много (М:М или M:N).Т а б л и ц а 3.2Характеристика видов связей таблицХарактеристика полейсвязи по видам1:11 :ММ:1М:МПоля связи основнойтаблицыявляютсяключомявляютсяключомнеявляютсяключомне являютсяключомПоля связидополнительнойтаблицыявляютсяключомнеявляютсяключомявляютсяключомнеявляютсяключомДадим характеристику названным видам связи между двумя таблицами иприведем примеры их использования.Связь вида 1:1Связь вида 1:1 образуется в случае, когда все поля связи основной и дополнительной таблиц являются ключевыми. Поскольку значения в ключевых полях обеих таблиц не повторяются, обеспечивается взаимно-однозначное соответствие записей из этих таблиц.

Сами таблицы, по сути, здесьстановятся равноправными.Пример 1.Пусть имеются основная 0 1 и дополнительная Д1 таблицы. Ключевыеполя обозначим символом «*», используемые для связи поля обозначим символом «+».Таблица 0 1* +Поле11Поле12а10б40в33. Реляционнаямодельданных59Таблица Д1* +Поле21Поле22астолвкнигаВ приведенных таблицах установлена связь между записью (а, 10) таблицы 0 1 и записью (а, стол) таблицы Д1. Основанием этого является совпадение значений в полях связи. Аналогичная связь существует и между записями (в, 3) и (в, книга) этих же таблиц.

В таблицах записи отсортированы позначениям в ключевых полях.Сопоставление записей двух таблиц по существу означает образованиеновых «виртуальных записей» (псевдозаписей). Так, первую пару записейлогически можно считать новой псевдозаписью вида (а, 10, стол), а вторуюпару — псевдозаписью вида (в, 3, книга).На практике связи вида 1:1 используются сравнительно редко, так как хранимую в двух таблицах информацию легко объединить в одну таблицу, которая занимает гораздо меньше места в памяти ЭВМ.

Возможны случаи, когдаудобнее иметь не одну, а две и более таблицы. Причинами этого может бытьнеобходимость ускорить обработку, повысить удобство работы несколькихпользователей с общей информацией, обеспечить более высокую степень защиты информации и т. д. Приведем пример, иллюстрирующий последнююиз приведенных причин.Пример 2.Пусть имеются сведения о выполняемых в некоторой организации научно-исследовательских работах. Эти данные включают в себя следующую информацию по каждой из работ: тему (девиз и полное наименование работ),шифр (код), даты начала и завершения работы, количество этапов, головногоисполнителя и другую дополнительную информацию.

Все работы имеют гриф«Для служебного пользования» или «секретно».В такой ситуации всю информацию целесообразно хранить в двух таблицах: в одной из них — всю секретную информацию (например, шифр, полное наименование работы и головной исполнитель), а в другой — всю оставшуюся несекретную информацию. Обе таблицы можно связать по шифруработы. Первую из таблиц целесообразно защитить от несанкционированного доступа.Связь вида 1 :МСвязь 1:М имеет место в случае, когда одной записи основной таблицысоответствует несколько записей вспомогательной таблицы.Часть 1. Основы60построениябазданныхПример 3.Пусть имеются две связанные таблицы 0 2 и Д2. В таблице 0 2 содержитсяинформация о видах мультимедиа-устройств ПЭВМ, а в таблице Д2 — сведения о фирмах-производителях этих устройств, а также о наличии на складехотя бы одного устройства.Таблица 0 2*+аВидустройстваCD-ROMбCD-RecorderвSound BlasterКодТаблица Д2**+КодФирма-производительНаличиеаAcerдааMitsumiнетаNECдааPanasonicдааSony.дабPhilipsнетбSonyнетбYamahaдавCreative LabsдаТаблица Д2 имеет два ключевых поля, так как одна и та же фирма можетпроизводить устройства различных видов.

В примере фирма Sony производит устройства считывания и перезаписи с компакт-дисков.Сопоставление записей обеих таблиц по полю «Код» порождает псевдозаписи вида: (a, CD-ROM, Acer, да), (a, CD-ROM, Mitsumi, нет), (a, CD-ROM,NEC, да), (a, CD-ROM, Panasonic, да), (a, CD-ROM, Sony, да), (б, CD-Recorder,Philips, нет), (б, CD-Recorder, Sony, да) и т. д.Если свести псевдозаписи в новую таблицу, то получим полную информацию обо всех видах мультимедиа-устройств ПЭВМ, фирмах, ихпроизводящих, а также сведения о наличии конкретных видов устройствна складе.3. Реляционнаямодельданных61Связь вида М:1Связь М:1 имеет место в случае, когда одной или нескольким записям основной таблицы ставится в соответствие одна запись дополнительной таблицы.Пример 4.Рассмотрим связь таблиц ОЗ и ДЗ.