124. Могут ли быть параметры триггера и как они ему передаются?

ALTER proc skolko @id int, @sum int output
as
if exists (select * from sotr where ID_Poraz = @id)
select @sum = COUNT(*) from sotr where ID_Poraz = @id
else select @sum = 0
print @sum

тут входной айди - задает номер отдела, а выходному "сум" присваетвается значение = количеству работников отдела

125. Что такое DRI и какое отношение эта аббревиатура имеет к триггерам? Как согласуется понятие DRI и механизм срабатывания триггеров, приведите примеры. При написании триггеров всегда надо помнить об этом, потому что при нарушении правил целостности по связям (DRI Declarative Referential Integrity) триггер просто может никогда не сработать. CREATE TRIGGER DEL_EXEMP ON dbo.EXEMPLAR

/* мы создаем триггер для таблицы EXEMPLAR */

FOR DELETE /* только для операции удаления */

AS

/* опишем локальные переменные */

DECLARE @Ntek int /* количество оставшихся экземпляров удаленной книги */

DECLARE @DEL_EX VARCHAR(12) /* шифр удаленного экземпляра*/

Begin /* по временной системной таблице, содержащей удаленные записи, определяем шифр книги, соответствующей последнему удаленномуэкземпляру */

SELECT @DEL_EX = ISBN From deleted

/* вызовем хранимую процедуру, которая определит количество экземпляров книги с заданным шифром */

EXEC @Ntek = COUNT_EX @DEL_EX

/* Если больше нет экземпляров данной книги, то мы удаляем запись о книге из таблицы BOOKS */

IF @Ntek = 0 DELETE from BOOKS WHERE BOOKS.ISBN = @DEL_EX

END

При наличии данных в подчинённых таблицах, триггер сработает некорректно.

CREATE TRIGGER DELL_BOOKS

ON [dbo].[BOOKS]

-- задали тип триггера

INSTEAD OF DELETE

AS

-- опишем переменную, в которую поместим шифр удаляемой книги

declare @ISBN varchar(14)

-- используя системную таблицу Deleted определеим значение шифра -- удаляемой книги и присвоим его нашей внутренней переменной @ISBN

Select @ISBN=ISBN from Deleted

-- удалим сначала из подчиненных таблиц все записи с заданным

-- значением шифра книги

Delete from BOOKS_CAT where BOOKS_CAT.ISBN=@ISBN

Delete from Relation_93 where RELATION_93.ISBN= @ISBN

-- Теперь удалим книгу

Delete from books where Books.isbn= @ISBN

Верный вариант, который согласует всё это с DRI.

Тема 11. Физические модели баз данных

126. Опишите механизм использования хэш-функций адресации к записям файлов. Сравните обе стратегии и определите, какая из них будет наиболее перспективной и в каких случаях. Суть методов хэширования состоит в том, что мы берем значения ключа (или некоторые его характеристики) и используем его для начала поиска, т. е. мы вычисляем некоторую хэш-функцию h(k) и полученное значение берем в качестве адреса начала поиска. Мы не требуем полного взаимнооднозначного соответствия, но для повышения скорости мы ограничиваем время этого поиска (количество дополнительных шагов) для окончательного получения адреса. Таким образом, мы допускаем, что нескольким разным ключам может соответствовать одно значение хэш-функции (т. е. один адрес). Подобные ситуации называются коллизиями. Значения ключей, которые имеют одно и то же значение хэш-функции, называются синонимами.

Поэтому при использовании хэширования как метода доступа необходимо принять два независимых решения:

• выбрать хэш-функцию;

• выбрать метод разрешения коллизий.

Существует множество различных стратегий разрешения коллизий, но мы для примера рассмотрим две достаточно распространенные.

11.2.1. Стратегия разрешения коллизий с областью переполнения

Первая стратегия условно может быть названа стратегией с областью переполнения.

При выборе этой стратегии область хранения разбивается на 2 части:

• основную область;

• область переполнения.

Для каждой новой записи вычисляется значение хэш-функции, которое определяет адрес ее расположения, и запись заносится в основную область в соответствии с полученным значением хэш-функции.

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

При этом цепочка синонимов не разрывается, но мы не просматриваем ее до конца, чтобы расположить новую запись в конце цепочки синонимов, а располагаем всегда новую запись на второе место в цепочке синонимов, что существенно сокращает время размещения новой записи. При таком алгоритме время размещения любой новой записи составляет не более двух обращений к диску с учетом того, что номер первой свободной записи в области переполнения хранится в виде системной переменной.

Рассмотрим теперь механизмы поиска произвольной записи и удаления записи для этой стратегии хэширования.

При поиске записи сначала вычисляется значение ее хэш-функции и считывается первая запись в цепочке синонимов, которая расположена в основной области. Если искомая запись не соответствует первой в цепочке синонимов, то далее поиск происходит перемещением по цепочке синонимов, пока не будет обнаружена требуемая запись. Скорость поиска зависит от длины цепочки синонимов, поэтому качество хэш-функции определяется максимальной длиной цепочки синонимов. Хорошим результатом может считаться наличие не более 10 синонимов в цепочке.

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

Если же удаляемая запись находится в середине цепочки синонимов, то необходимо провести корректировку указателей: в записи, предшествующей удаляемой, в цепочке ставится указатель из удаляемой записи. Если это последняя запись в цепочке, то механизм изменения указателей такой же, т. е. в предшествующую запись заносится признак отсутствия следующей записи в цепочке, который ранее хранился в последней записи.

11.2.2. Организация стратегии свободного замещения

При этой стратегии файловое пространство не разделяется на области, но для каждой записи добавляется 2 указателя: указатель на предыдущую запись в цепочке синонимов и указатель на следующую запись в цепочке синонимов. Отсутствие соответствующей ссылки обозначается специальным символом, например нулем или пробелом. Для каждой новой записи вычисляется значение хэш-функции, и если данный адрес свободен, то запись попадает на заданное место и становится первой в цепочке синонимов. Если адрес, соответствующий полученному значению хэш-функции, занят, то по наличию ссылок определяется, является ли запись, расположенная по указанному адресу, первой в цепочке синонимов. Если да, то новая запись располагается на первом свободном месте и для нее устанавливаются соответствующие ссылки: она становится второй в цепочке синонимов, на нее ссылается первая запись, а она ссылается на следующую, если таковая есть. Если запись, которая занимает требуемое место, не является первой записью в цепочке синонимов, значит, она занимает данное место «незаконно» и при появлении «законного владельца» должна быть «выселена», т. е. перемещена на новое место. Механизм перемещения аналогичен занесению новой записи, которая уже имеет синоним, занесенный в файл. После перемещения «незаконной» записи вновь вносимая запись занимает свое законное место и становится первой записью в новой цепочке синонимов.

Механизмы удаления записей во многом аналогичны механизмам удаления в стратегии с областью переполнения. Однако еще раз кратко опишем их. Если удаляемая запись является первой записью в цепочке синонимов, то после удаления на ее место перемещается следующая (вторая) запись из цепочки синонимов и проводится соответствующая корректировка указателя третьей записи в цепочке синонимов, если таковая существует. Если же удаляется запись, которая находится в середине цепочки синонимов, то производится только корректировка указателей: в предшествующей записи указатель на удаляемую запись заменяется указателем на следующую за удаляемой запись, а в записи, следующей за удаляемой, указатель на предыдущую запись заменяется на указатель на запись, предшествующую удаляемой.

127. Что такое индексные файлы, какие типы индексных файлов бывают? Как строятся индексные файлы с плотным индексом? Как рассчитывается размер данного файла и время доступа к произвольной записи? Несмотря на высокую эффективность хэш-адресации, в файловых структурах далеко не всегда удается найти соответствующую функцию, поэтому при организации доступа по первичному ключу широко используются индексные файлы. В некоторых коммерческих системах индексными файлами называются также файлы, организованные в виде инвертированных списков, которые используются для доступа по вторичному ключу. Мы будем придерживаться классической интерпретации индексных файлов и надеемся, что если вы столкнетесь с иной интерпретацией, то сумеете разобраться в сути, несмотря на некоторую путаницу в терминологии.

Индексные файлы можно представить как файлы, состоящие из двух частей. Это не обязательно физическое совмещение этих двух частей в одном файле, в большинстве случаев индексная область образует отдельный индексный файл, а основная область образует файл, для которого создается индекс. Но нам удобнее рассматривать эти две части совместно, так как именно взаимодействие этих частей и определяет использование механизма индексации для ускорения доступа к записям.

Мы предполагаем, что сначала идет индексная область, которая занимает некоторое целое число блоков, а затем идет основная область, в которой последовательно расположены все записи файла.

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

Файлы с плотным индексом называются также индексно-прямыми файлами, а файлы с неплотным индексом называются также индексно-последовательными файлами.

Рассмотрим файлы с плотным индексом. В этих файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а структура индексной записи в них имеет следующий вид (рис. 11.3):

Рис. 11.3. Структура плотного индекса

 Здесь значение ключа — это значение первичного ключа, а номер записи — это порядковый номер записи в основной области, которая имеет данное значение первичного ключа. Так как индексные файлы строятся для первичных ключей, однозначно определяющих запись, то в них не может быть двух записей, имеющих одинаковые значения первичного ключа. В индексных файлах с плотным индексом для каждой записи в основной области существует одна запись из индексной области. Все записи в индексной области упорядочены по значению ключа, поэтому можно применить более эффективные способы поиска в упорядоченном пространстве.

Длина доступа к произвольной записи оценивается не в абсолютных значениях, а в количестве обращений к устройству внешней памяти, которым обычно является диск. Именно обращение к диску является наиболее длительной операцией по сравнению со всеми обработками в оперативной памяти.

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

T_n = log ₂N,

где N — число элементов.

Однако в нашем случае является существенным только число обращений к диску. Поиск происходит в индексной области, где применяется двоичный алгоритм поиска индексной записи, а потом путем прямой адресации мы обращаемся к основной области уже по конкретному номеру записи. Для того чтобы оценить максимальное время доступа, нам надо определить количество обращений к диску для поиска произвольной записи. На диске записи файлов хранятся в блоках. Размер блока определяется физическими особенностями дискового контроллера и операционной системой. В одном блоке могут размещаться несколько записей. Значит нам надо определить количество индексных блоков, которое потребуется для размещения всех требуемых индексных записей, а потому максимальное число обращений к диску будет равно двоичному логарифму от заданного числа блоков плюс единица. После поиска номера записи в индексной области необходимо обратиться к основной области файла. Поэтому формула для вычисления максимального времени доступа в количестве обращений к диску выглядит следующим образом:

T_n = log ₂N _{бл. инд.} + 1.

Рассмотрим конкретный пример и сравним время доступа при последовательном просмотре и при организации плотного индекса.

128. Как строятся индексные файлы с неплотным индексом? Как рассчитывается размер данного файла и время доступа к произвольной записи? Попробуем усовершенствовать способ хранения файла: будем хранить его в упорядоченном виде и применим алгоритм двоичного поиска для доступа к произвольной записи. Тогда время доступа к произвольной записи будет существенно меньше. Для нашего примера это будет:

T = log₂KBO = log ₂12 500 = 14 обращений к диску.

И это существенно меньше, чем 12 500 обращений при произвольном хранении записей файла. Однако и поддержание основного файла в упорядоченном виде — операция сложная.

Неплотный индекс строится именно для упорядоченных файлов. Для этих файлов используется принцип внутреннего упорядочения для уменьшения количества хранимых индексов. Структура записи индекса для таких файлов имеет следующий вид (рис. 11.4).

Рис. 11.4. Структура неплотного индекса

В индексной области мы теперь ищем нужный блок по заданному значению первичного ключа. Так как все записи упорядочены, то значение первой записи блока позволяет нам быстро определить, в каком блоке находится искомая запись. Все остальные действия происходят в основной области.

Время сортировки больших файлов весьма значительно, но поскольку файлы поддерживаются сортированными с момента их создания, накладные расходы в процессе добавления новой информации будут гораздо меньше. Оценим время доступа к произвольной записи для файлов с неплотным индексом. Алгоритм решения задачи аналогичен описанному ранее.