Интерпретации Datalog и SQL

Между вторым способом интерпретации правил Datalog, описанным в разделе 4.2.4, и то.лько что рассмотренной интерпретацией простых запросов SQL есть определенное сходство. В Datalog рассматриваются все возможные приписывания кортежей из подходящего огношения подцелям в теле правила. В SQL тоже рассматриваются все возможные приписывания кортежей переменным кортежей. В обоих случаях эти приписывания кортежей ограничива-ютоя арифметическими подцелями (частями предложений WHERE в SQL) и кортежи результата получаются путем вычисления головного элемента правила (пункта SELECT в SQL).

Преобразование в релядионнутю алгебру

Третий способ интерпретации - это преобразование запроса SQL в выражение реляционной а.пге6ры. Сначала берется декартово произведение переменных корте-. жей из пункта FROM. Если две переменные кортежей ссылаются на одно и то же , отношение, оно появляется в произведении дважды и его атрибуты переименовы-ваются так, чтобы все их имена были уникальны. Во избежание двусмысленностей ангшогичным образом переименовываются атрибуты из разных отношений, имею, л lune одно и то же имя.

кортеж, состояший из значений термов, которые следуют за словом SELECT. Заметим, что значение каждого терма определяется текувшм припнсыванием кортежей переменным кортежей. Алгоритм ответов на запросы представлен на рмс. 5.2.

LET переменные кортежей в пункте from пробегают по

отношенипы R1, R2.....Rn;

FOR каждого кортежа t1 в отношении R1 DO

FOR каждого кортежа 12 в отношении R2 DO

FOR каждого кортежа tn в отношении Rn DO

IF пункт where выполняется при подстановке

переменных из t1, t2.....tn вместо всех

ссылок на атрибуты THEN

оценить атрибуты пункта select согласно

t1,12,.... tn и построить кортеж

из результатов этой оценки.

Рис. 5.2 Алгоритм ответа но простой запрос SQI

Параллельное приписывание

Существует эквивалентное определение семантики запроса, при котором вложенные циклы, пробегающие по переменным кортежей, не строятся явным образом. Вместо этого применяются произвольные или параллельные возможные приписывания кортежей из отношений переменным кортежей. Для каждого приписывания определяется истинность пункта WHERE. Каждое приписывание, при котором этот пункт истинен, составляет кортеж ответа, который строится из атри-6>тов пункта SELECT, вычисляемых согласно данному приписыванию.

Интуитивно неочевидные следствия из семантики SQL

Пусть Л, S и Т- унарные (однокомпонеитные) отношения, в каждое из которых входит единственный атрибут А, и нужно найти такие элементы Л, которые входят также в S или Т, т.е. вычислить Ло(5и 7). Предположим, что для этого нужен запрос:

SELECT R.A FROM R.S.T

WHERE R.A = S.A OR R.A = T.A

Рассмотрим случай, когда Т пусто. Тогда условие R.A = Т.А никогда не выполняется, и на основе интуитивного понимания связки OR мы считаем, что запрос даст результат И все же, применяя любое из приведенных

выше эквивалентных определений запроса, мы обнаруживаем, что результат пуст независимо от того, сколько общих элементов имеют R и S. Применение семантики вложенных циклов (рис. 5.2) показывает, что цикл для переменной кортежа Т повторяется О раз, так как в этом отношении нет кортежей, по которым данная переменная могла бы пробегать. Поэтому IF-предложение никогда не выполняется и ничего нового не возникает. Если же рассматривать приписывания кортежей переменным, тоже оказывается, что невозможно приписать кортеж отношению Т, поэтому никаких приписываний не существует. И наконец, применяя декартово произведение, мы начинаем с выражения RxSx Т. которое яачяется пустым, поскольку У пусто.

Пример 5.13. Преобразуем в выражение реляционной алгебры запрос из примера 5.12. В предложении FROM две переменные кортежей ссылаются на отношение MovieStar, поэтому начнем с выражения

MovieStar х MovieStar

В результирующем отношении восемь атрибутов. Первые четыре - name, address, gender и birthdate берутся из первой копии отношения MovieStar, а последние соответствуют тем же атрибутам из второй копии MovieStar Можно было бы со-ааать имена этих атрибутов с помощью точки и псевдонима переменной кортежа, например Starl .gender, но для краткости введем новые символы и назовем атрибуты Ai.Aj.....А. Итак, А соответствует Starl.name. А2 соответствует Star2name и т.д.

4 Технически реляционная алгебра не допускает арифметических вычислений в предложении SELECT, а в SQL они допустимы (см. пример 5.4). Однако можно применить очевидное расширение оператора проекции реляционной алгебры, и более ограниченное определение проекции - просто дань традиции.

К полученному произиедению применяется оператор выбора путем простого преобразования предложения WHERE в условия выбора. При этом каждая ссылка на атрибрт в предложении WHERE заменяется соответствующим ей атрибутом из произведения. И наконец, из предложения SELECT стротся список атрибутов для финальной операции проекции. Атрибуты для этой операции определяются так же, как и д1я операции выбора: каждая ссылка на атрибут предложения SELECT заменяется соответствующим ей атрибутом из произведения.

Стили записи запросов SQL

в обшс.у случае запросы SQL записываются так, что каждое важное к.пю-чевое слово начинает новую строку. Такой стиль записи дает читающему BH3v:uibHoe прсзставленяе о структуре запроса. Однако, когда запрос или гюд-запрос короток, ои записывается в одной строке 1как в примере 5.15). Такой сппь зап1(1 лелает запрос компактным и удобным юя чтения

При таком методе присвоения вмен атрибутам из пункта WHERE получается условие отбора =A(,uAi< Ay Список проекции -Ау, А. Таким образом, выражение

л.a d ч,... (Р ( , , j(MovieStar). р., ,j(MovieStar))) представляет весь запрос в реляиионной алгебре. □

5.2.5 Объединение, пересечение и разность запросов

Иногда отношения комбинируются с по*ющью теоретнко-множесгвенных операций объединения, пересечения и разности. В SQL соответствующие операторы применяются к результатам запросов при условии, что запросы порождают отношения с одним и тем же множеством атрибутов. Ключевые слова UN ON, INTERSECT и EXCEPT обозначают соответственно cj, г. и -. Слова типа UNION ставятся между двумя запросами, заключенными в скобки.

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

MovieStar(name, address, gender, birthdate) .

MovieExec(name. add ess. cert#, netWorth)

можно сформулировать запрос, показанный на рис. 5.3.

1) (SELECT name, address

2) FROM MovieStar

3) WHERE gender = F)

4) INTERSECT

5) (SELECT name, address

6) FROM MovieExec

7) WHERE netWorth > 10000000)

Рис. 5.3 Пересечение женщин-кинозвезд с богатыми одминкктратороми

Строки (1) - (3) порождают множество женщин-кинозвезд в отношении, схема которого солержлт атрибуты name и address.

Строки (5) - (7) порождают множество администраторов с чистым доходом не менее 10 млн. дол. Эзот запрос тоже дает отнииение, схема которого содержит только атрибуты name и address. Поскольку обе полученные схемы совпадают, пересечения можно вычислить с помошью оператора, указанного в строке (4). □