Средства реализации запросов

 

Реализацию запросов в обоих формах рассмотрим на примере базы данных построенной на практических занятиях. Пусть нужно реализовать запрос: Какие организации не оплатили заказы?

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

 

В форме QBE запрос примет вид показанный на рисунке. В соответствии с требованием запроса из базы нужно выбрать значения указанных атрибутов, для которых вообще не введена оплата, т.е. значение соответствующего атрибута «Сумма оплаты» пусто (Null). В организации связей этого запроса есть одна особенность. Связь 1:М между отношениями «Заказы» и «Оплата» подразумевает выборку только существующих кортежей. Однако, если для какого либо заказа оплата не введена, то не будет кортежа в отношении «Оплата», соответствующего кортежу отношения «Заказы», т.е. условие «Сумма оплаты» = Null не будет работать. Для того, чтобы данное условие заработало нужно модифицировать связь, наложив на нее требование показывать все кортежи отношения «Заказы», а если им не соответствует не одного кортежа в отношении «Оплата», то ставить вместо него кортеж со значениями атрибутов Null. Таким образом условие запроса приобретает смысл.

В форме SQL данный запрос приобретает следующий вид.

SELECT Клиенты.Организация, Заказы.[Номер заказа], Оплата.[Сумма оплаты]

FROM Клиенты INNER JOIN (Заказы LEFT JOIN Оплата ON Заказы.[Номер заказа] = Оплата.[Номер заказа]) ON Клиенты.[Код клиента] = Заказы.[Код клиента]

WHERE (((Оплата.[Сумма оплаты]) Is Null));

В этом запросе использованы следующие операторы языка SQL:

SELECT – выбрать

FROM - из

INNER JOIN –соединить один ко многим

LEFT JOIN – соединить слева

WHERE – где

ON - по

В соответствии со смыслом операторов данный запрос на языке SQL можно прочитать как:

ВЫБРАТЬ Клиенты.Организация, Заказы.[Номер заказа], Оплата.[Сумма оплаты] ИЗ Клиенты СОЕДИНЕННЫЙ 1:М (Заказы СОЕДИНЕННЫЙ СЛЕВА Оплата ПО Заказы.[Номер заказа] = Оплата.[Номер заказа]) ПО Клиенты.[Код клиента] = Заказы.[Код клиента] ГДЕ (((Оплата.[Сумма оплаты]) Is Null));

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

Теоретические основы проектирования БД.

Основные понятия.

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

Атрибутом будем называть поименованное свойство объекта и обозначать А_i, где . Домен атрибута А_i обозначим dom(А_i). Тогда отношением R называется конечное множество атрибутов . Ключ отношения R является подмножеством К = со следующим свойством. Для любых двух различных кортежей t₁ и t₂ в R существует такое , что t₁(B) t₂(B). Другими словами, не существует двух кортежей, имеющих одно и то же значение на всех атрибутах из К. Таким образом, достаточно знать К - значение кортежа, чтобы идентифицировать кортеж однозначно.

Пример.

СТУДЕНТ[ НОМЕР_ЗАЧЕТКИ,ИМЯ,КУРС,ГРУППА]

Ключи, явно указанные в модели называются выделенными. Могут быть ключи отличные от выделенных и называемые неявными ключами. Например ИМЯ в предыдущем прмере.

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

ГРАФИК[ПИЛОТ,РЕЙС,ДАТА,ВРЕМЯ]

ПИЛОТ функционально зависит от {РЕЙС,ДАТА}

F-зависимости принято обозначать {РЕЙС,ДАТА}-> ПИЛОТ и говорят, что РЕЙС и ДАТА функционально определяют ПИЛОТ.

В терминах теории множеств и реляционной алгебры F-зависимость определяется так. Пусть R отношение и X, Y подмножества атрибутов в R. Отношение R удовлетворяет функциональной зависимости X -> Y, если p_Y(s_X-x®) имеет не более чем один кортеж для каждого Х - значения х. В F-зависимости X->Y подмножество X называется левой частью, а Y - правой частью.

Такая интерпретация функциональной зависимости является основой алгоритма SATISFIES, приводимого ниже.

SATISFIES

Вход: Отншение R и F-зависимость X->Y.

Выход: истина, если R удовлетворяет X->Y, ложь - в противном случае.

SATISFIES(R,X->Y)

Отсортировать отношение R по Х-столбцам так, чтобы собрать кортежи с равными Х-значениями вмести.

Если каждая совокупность кортежей с равными Х-значениями имеет также равные Y-значения, то на выходе получаем истину, а в противном случае - ложь.

Этот алгоритм проверяет, удовлетворяет ли отношение R F-зависимости X -> Y.

Пример.

В результате выполнения алгоритма SATISFIES выясним удовлетворяет ли F-зависимость РЕЙС -> ВРЕМЯ_ВЫЛЕТА следующему отношению

ГРАФИК

ПИЛОТ	РЕЙС	ДАТА	ВРЕМЯ_ВЫЛЕТА
А...		9 авг	10:15
П...		11 авг	10:15
А...		10 авг	13:25
Р...		12 авг	13:25
П...		8 авг	5:50
С...		9 авг	5:50
П...		12 авг	18:35
С...		15 авг	13:25

 

Однако F-зависимость ВРЕМЯ_ВЫЛЕТА -> РЕЙС согласно этому алгоритму не выполняется для этого отношения

ГРАФИК

ПИЛОТ	РЕЙС	ДАТА	ВРЕМЯ_ВЫЛЕТА
П...		8 авг	5:50
С...		9 авг	5:50
А...		9 авг	10:15
П...		11 авг	10:15
А...		10 авг	13:25
Р...		12 авг	13:25
С...		15 авг	13:25
П...		12 авг	18:35

 

Для разработки модели базы данных необходимо знать полное множество F-зависимостей. Чтобы найти их, необходимы семантические знания об исходном отношении R. Поэтому можно считать семейство F-завсимостей заданным. Обозначим его F. Однако при таком подходе нельзя быть уверенным, что найдены все F-зависимости отношения R. Для того, чтобы найти все F-зависимости, если известны некоторые из них, можно воспользоваться аксиомами вывода. Возможность получения новых F-зависимостей с помощью аксиом вывода базируется на следующем правиле. Мнжество F-зависимостей F влечет за собой F-зависимость X -> Y (обозначение: F = X -> Y), если каждое отношение удовлетворяющее всем зависимостям в F, удовлетворяет также зависимости X -> Y. Аксиома вывода - это правило, устанавливающее, что если отношение удовлетворяет определенным F-зависимостям, то оно должно удовлетворять и некоторым другим F-зависимостям. Существует шесть аксиом вывода:

Рефлексивность: X -> X.

Пополнение: X -> Y влечет за собой XZ -> y.

Аддитивность: X -> Y и X -> Z влечет за собой X -> YZ.

Проективность: X -> YZ влечет за собой X -> Z.

Транзитивность: X -> Y и Y -> Z влечет за собой X -> Z.

Псевдотранзитивность: X -> Y и YZ -> W влечет за собой XZ -> W.

Пример.

Пусть дано отношение R, а X, Y и Z подмножества R. Предположим, что отношению удовлетворяет XY -> Z и X -> Y. Согласно аксиоме псевдотранзитивности получим XX -> Z или X -> Z.

Если даны аксиомы рефлексивности, пополнения и псевдотранзитивности, то из них можно вывести все остальные. Иногда их называют аксиомами Армстронга.

Пусть F-множество F-зависимостей для отношения R. Замыкание F, обозначаемое F­­­­⁺ , - это наименьшее содержащее F множество, такое что при применении к нему аксиом Армстронга нельзя получить ни одной F - зависимости, не принадлежащей F.

Пример.

Пусть F = {AB -> C, C -> B } - множество F-зависимостей на R(ABC). F⁺ = {A -> A, AB -> A, AC -> A, ABC -> A, B -> B, AB -> B, BC -> B, ABC -> B, C -> C, AC -> C, BC -> C, ABC -> C, AB -> AB, ABC -> AB, AC -> AC, ABC -> AC, BC -> BC, ABC -> BC, ABC -> ABC, AB -> C, AB -> AC, AB -> BC, AB -> ABC, C -> B, C -> BC, AC -> B, AC -> AB}

Таким образом, если известно множество F-зависимостей удовлетворяющих отношению R, можно найти все F- зависимости, удовлетворяющие этому отношению. Говорят, что F = X -> Y,если X -> Y F⁺.

Лекция 3

Получение замыкания F⁺ не обязательно для установления F = X -> Y.

Для этого достаточно воспользоваться алгоритмом MEMBER.

Алгоритм MEMBER.

Вход: Множество F-зависимостей F и F-зависимость X -> Y.

Выход: истина, если F = X -> Y, ложь в противном случае.

MEMBER(F, X -> Y)

begin

if Y CLOSURE(X,F) then return (истина)

else return(ложь)

end

 

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

Алгоритм CLOSURE.

Вход: Множество атрибутов Х и множество F-зависимостей F.

Выход: Замыкание Х над F.

CLOSURE(X,F)

begin

OLDDEP = 0; NEWDEP = X

while NEWDEP OLDDEP do begin

OLDDEP = NEWDEP

for каждая F- зависимость W -> Z в F do

if NEWDEP W then

NEWDEP = NEWDEP Z

end

return(NEWDEP)

end

 

Пример работы алгоритма MEMBER

Пусть F = {НОМЕР_РЕЙСА, ДАТА_ВЫЛЕТА -> КОЛИЧЕСТВО_МЕСТ,

НОМЕР_РЕЙСА -> ПУНКТ_ОТПРАВЛЕНИЯ, НОМЕР_РЕЙСА, ДАТА_ВЫЛЕТА -> ПИЛОТ} и необходимо установить F |= НОМЕР_РЕЙСА -> ПИЛОТ

Используем для этого алгоритм MEMBER

Обращение к нему будет выглядеть так: MEMBER (F,НОМЕР_РЕЙСА -> ПИЛОТ).

Результатом работы алгоритма будет истина, если будет истинным выражение Y CLOSURE(X,F), или с учетом данных примера ПИЛОТ CLOSURE(НОМЕР_РЕЙСА,F). Выполним поэтапно работу алгоритма CLOSURE как показано в таблице. В результате будет возвращено значение НОМЕР_РЕЙСА. ПУНКТ_ОТПРАВЛЕНИЯ. Атрибут ПИЛОТ не является подмножеством результата работы CLOSURE, поэтому F не влечет за собой НОМЕР_РЕЙСА -> ПИЛОТ, т.е. эту функциональную зависимость нельзя вывести из F.

 

 

Шаг	NEWDEP	OLDDEP	Зависимость из F	Пояснения
	НОМЕР_РЕЙСА			Начальные значения переменных, если они не равны, то OLDDEP= NEWDEP
	НОМЕР_РЕЙСА	НОМЕР_РЕЙСА	НОМЕР_РЕЙСА, ДАТА_ВЫЛЕТА -> КОЛИЧЕСТВО_МЕСТ	НОМЕР_РЕЙСА, ДАТА_ВЫЛЕТА не является подмножеством содержимого NEWDEP поэтому следующая зависимость из F
	НОМЕР_РЕЙСА	НОМЕР_РЕЙСА	НОМЕР_РЕЙСА -> ПУНКТ_ОТПРАВЛЕНИЯ	НОМЕР_РЕЙСА подмножество NEWDEP поэтому добавим к NEWDEP ПУНКТ_ОТПРАВЛЕНИЯ
	НОМЕР_РЕЙСА. ПУНКТ_ОТПРАВЛЕНИЯ	НОМЕР_РЕЙСА	НОМЕР_РЕЙСА, ДАТА_ВЫЛЕТА -> ПИЛОТ	НОМЕР_РЕЙСА, ДАТА_ВЫЛЕТА не является подмножеством NEWDEP и это последняя зависимость из F. NEWDEP не равно OLDDEP поэтому присваиваем OLDDEP значение NEWDEP и повторяем цикл
	НОМЕР_РЕЙСА. ПУНКТ_ОТПРАВЛЕНИЯ	НОМЕР_РЕЙСА. ПУНКТ_ОТПРАВЛЕНИЯ		Повторяя перебор зависимостей из F убедимся, что NEWDEP не изменится, поэтому после окончания цикла окажется, что NEWDEP= OLDDEP и алгоритм CLOSURE возвращает значение НОМЕР_РЕЙСА. ПУНКТ_ОТПРАВЛЕНИЯ