в заключение хотелось бы отметить, что, к сожалению, многие современные программные продукты содержат некоторые замедлители оптимизации, о которых пользователь должен по крайней мере знать (даже если с этим ничего нельзя поделать). Замедлитель оптимизации - это функция СУБД, не позволяющая оптимизатору выполнять свою работу так, как она могла бы быть выполнена (например, при отсутствии данной функции). К замедлителям оптимизации можно, например, отнести возможность вставки в таблицу записей-дубликатов [5.6], трехзначную логику (глава 18) и реализацию трехзначной логики в языке SQL [18.6], [18.10].

Упражнения

17.1. Одни пары выражений в контексте базы данных поставщиков, деталей и проектов эквивалентны, а другие - нет. Какие пары выражений действительно эквивалентны?

al) S JOIN ( ( Р JOIN J ) WHERE CITY = London a2) ( P WHERE CITY = London ) JOIN ( J JOIN S )

61) ( S MINUS ( ( S JOIN SPJ ) WHERE P# = P# ( P2 ) )

{ S#, SNAME, STATUS, CITY } ) { S#, CITY }

62) S { S#, CITY } MINUS

( S { Si, CITY } JOIN

( SPJ WHERE P# = P# ( P2 ) ) ) { Si, CITY }

b1) ( S { CITY } MINUS P { CITY } ) MINUS J { CITY }

b2) ( S { CITY } MINUS J { CITY } )

MINUS ( P { CITY } MINUS J { CITY } )

rl) ( J { CITY } INTERSECT P { CITY } ) UNION ( S { CITY } )

г2) J { CITY } INTERSECT ( S { CITY } UNION P { CITY } )

д1) ( ( SPJ WHERE S# = Si (Sl ) )

UNION ( SPJ WHERE P# = P# ( РГ ) ) )

INTERSECT

( ( SPJ WHERE J# = J# ( Jl ) )

UNION ( SPJ WHERE S# = S# ( Sl ) ) )

д2) ( SPJ WHERE S# = S# ( Sl ) ) UNION

( ( SPJ WHERE P# = P# ( Pl ) ) INTERSECT ( SPJ WHERE J# = Ji ( Jl ) ) )

el) ( S WHERE CITY = London ) UNION ( S WHERE STATUS > 10 )

e2) S WHERE CITY = London AND STATUS > 10

ж1) ( S { S# } INTERSECT ( SPJ WHERE J# = Jl ( Jl ) ) { S# } ) UNION ( S WHERE CITY = London ) { Sl }

ж2) S { SI } INTERSECT ( ( SPJ WHERE Jl = Jl ( Jl ) ) { SI } ) UNION ( S WHERE CITY = London ) { Sl } )

3l) ( SPJ WHERE Jl = Jl ( Jl ) ) { SI }

MINUS ( SPJ WHERE Pl = Pi ( Pl ) ) { Si }

з2) ( ( SPJ WHERE Л = Л ( Л ) )

MINUS ( SPJ WHERE Pi = P ( РГ ) ) ) { SI }

и1) S JOIN ( P { CITY } MINUS J { CITY } )

и2) ( S JOIN P { CITY } ) MINUS ( S JOIN J { CITY } )

17.2. Докажите, что операции соединения, объединения и пересечения являются коммутативными, а операция вычитания - нет.

17.3. Докажите, что операции соединения, объединения и пересечения являются ассоциативными, а операция вычитания - нет.

17.4. Докажите, что:

а) объединение распределяется по пересечению;

б) пересечение распределяется по объединению.

17.5. Докажите, что для всех А и В:

а) А UNION ( А INTERSECT В ) = А;

б) А INTERSECT ( А UNION В ) = А.

Замечание. Эти два закона называются законами поглощения. Как и законы идемпотентности, коммутативности и т.д., они могут оказаться полезными при проведении оптимизации.

17.6. Докажите следующее.

а) Выборка безусловно распределяема по объединению, пересечению и вычитанию и условно распределяема по соединению.

б) Проекция безусловно распределяема по объединению и пересечению, условно распределяема по соединению и не распределяема по вычитанию. Запишите соответствующие критерии для условной распределяемости.

17.7. Распространите правила преобразования, изложенные в разделе 17.4, так, чтобы учитывались операторы EXTEND и SUMMARIZE.

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

17.9. Запишите соответствующий набор правил преобразования для условий, в которых используются операторы AND, OR и NOT. Примером таких правил может служить закон коммутативности для оператора AND, т.е. утверждение, что выражение А AND В тождественно выражению В AND А.

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

17.11.Ниже перечислены ограничения целостности для базы данных поставшиков, деталей и проектов.

Допустимыми городами являются Лондон (London), Париж (Paris), Рим (Rome), Афины (Athens), Осло (Oslo), Стокгольм (Stockholm), Мадрид (Madrid) и Амстердам (Amsterdam).

Никакие два проекта не могут быть размешены в одном и том же городе.

в любой момент в Афинах может находиться не более одного поставщика.

Ни одна поставка по количеству не может превышать удвоенное среднее значение количества по всем поставкам.

Поставщик с наибольшим статусом не может находиться в одном городе с поставщиком с наименьшим статусом.

Каждый проект должен находиться в городе, в котором есть хотя бы один поставщик этого проекта.

Должна существовать по крайней мере одна красная деталь.

Среднее значение статуса поставщика должно быть больше 18.

Каждый поставщик из Лондона должен поставлять деталь с номером Р2.

Хотя бы одна красная деталь должна весить меньше 50 фунтов.

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

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

Ниже перечислены простые запросы к этой базе данных:

а) выбрать сведения о поставщиках, которые не поставляют деталь с номером Р2;

б) выбрать сведения о поставщиках, которые не поставляют детали для какого-либо проекта в том же городе, где они находятся;

в) выбрать сведения о таких поставщиках, для которых не существует других поставщиков, поставляющих меньше видов деталей;

г) выбрать сведения о поставщиках из Осло, которые поставляют по крайней мере два разных вида деталей из Парижа для по крайней мере двух разных проектов в Стокгольме;

д) выбрать сведения о парах поставщиков из одного города, поставляющих пары деталей из одного и того же города;

е) выбрать сведения о парах поставщиков из одного города, поставляющих детали парам проектов, находящихся в одном городе;

ж) выбрать сведения о деталях, поставляемых хотя бы для одного проекта, но только теми поставщиками, которые размещены не в том городе, где находится сам проект;

з) выбрать сведения о поставщиках наибольшего количества различных типов деталей.

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

17.13. Попробуйте провести следующий эксперимент. Возьмите простой запрос, например Выбрать имена поставщиков детали с номером Р2 , и запишите его всеми известными вам способами с помощью любого доступного языка запросов (возможно, это будет язык SQL). Создайте и заполните данными подходящую тестовую базу данных, выполните все версии запроса и определите время выполнения каждой версии. Если полученные значения будут сильно различаться, значит, экспериментально доказано.