Введение в системы БД (542480), страница 69
Текст из файла (страница 69)
КосКЫПе, Мбл Сопзршег Бс!епсе Ргезз, 1988. Книга Ульмана, в отличие от данной книги, содержит более формальное изложе- ние реляционного исчисления и связанных с ним вопросов. В частности, в ней обсуждается понятие безопасное~и выражений исчисления. Это имеет значение при адаптации немного измененной версии исчисления, в которой переменные кортежей не определяются отдельными операторами ККНЯЕ, а связываются с об- ластью значений посредством явных условий в предложении ИНЕКЕ.
В такой вер- сии исчисления запрос "Получить имена всех поставщиков из Лонлона", напри- мер, може~ выглядеть так. ЯХ ИНЕКЕ ЯХ е Я йН0 ЯХ.СТТУ = 'Ьопбол' Одна из проблем, возникающих при использовании этой версии исчисления, за- ключается в том, что в ней недопустимы запросы, подобные следующему. Такие выражения называются небезопасными, так как они не возвращают конечный результат (множество всего, что не входит в отношение Я, бесконечно). Поэтому необходимо ввести некоторые правила, обеспечивающие безопасность в этом смысле. В книге Ульмана описаны такие правила (для исчисления как кортежей, так и доменов).
Следует отметить, что в оригинальном исчислении Кодда такие правила были. 7.14. 2!пег" М. М. ()вегу Ву Ехатр1е // Ргос. ХСС 44.— Апа!зе!ш, Са1!Г., 1975.— Мопгча!е, 143х АР1РЯ Ргезз, 1977. Описанный в этой работе реляционный язык (4цегу-Ву-Ехашр1е (! !ВЕ) включает элементы исчисления кортежей и в еще большей степени — элементы исчисления доменов. Привлекательный и интуитивно понятный синтаксис языка основывается иа идее формирования элементов в "шаблонные таблицы" на экране дисплея вместо записи линейных операторов. Например, формулировка языка ОВЕ для запроса "Получить имена поставщиков по крайней мере одной детали, поставляемой поставщиком с номером 'Б2'" (довольно сложный запрос) может выглядеть следующим образом.
Пояснение. Пользователь обращается к системе с запросом отобразить на экране три шаблонные таблицы (одну — для отношения Я и две — для отношения ЯР), после чего формирует в них элементы, как показано выше. Элементы, начинающиеся символом подчеркивания, представляют "образцы" (т.е. переменные доменов); остальные элементы представляют собой литералы. В этом случае пользователь обращается к системе с запросом "предоставить" ("Р") значения имен поставщиков ( ЫХ), таких, что если это поставщик ЯХ, то ЯХ поставляет некоторую деталь РХ, а деталь РХ, в свою очередь, также поставляется поставщиком с номером 'Я2'.
Заметьте, что под кванторами существования подразумевается (как, кстати, и под кванторами существования в языке О()ЕЕ) совсем другой смысл, поэтому данный синтаксис прост для понимания. Вот другой пример: "Определить все пары номеров поставщиков, которые находятся в одном городе". К сожалению, язык ОВЕ не является реляционно полным, а конкретнее — не поддерживает (в полной мере) негативный квантор существования (НОТ ЕХ1ЯТЯ).
Вследствие этого определенные запросы (например, "Получить имена поставщиков всех типов деталей") не могут быть выражены в языке ОВЕ. (На самом деле язык ОВЕ вначале "поддерживал" квантор НОТ БХ1ЯТЯ, по крайней мере неявно, но построение всегда было сопряжено с некоторыми трудностями.
Основная проблема заключалась в том, что не было способа указать порядок, в котором различные неявные кванторы могли бы быть применены, а этот порядок, к сожалению, очень важен; см. (7.3) или ответ к упр. 7.2. Поэтому определенные запросы получались неоднозначными [7.3!.) Злуф (автор этой работы) первым изобрел и разработал язык ОВЕ. Данная статья была первой из многих статей, написанных Злуфом по этой тематике. 283 Глава 7. Реляционное исчисление Ответы к некоторым упражнениям РОНАЬЬ х ЕХ1ЯТЯ у ( у > х ) ЕХ1ЯТБ у РОНАЬЬ х (у > х ) 7.3. 7,.4.
284 Часть 11. Реляционная модель 7.1. 7.2. а) верно; б) верно; е) верно; г) верно; д) не верно. Замечание. Причина, по которой утверждение д не верно, состоит в том, что применение квантора ГОНАЬЬ к пустому множеству всегда дает значение истина. И наоборот, применение квантора ЕХ1БТЯ к пустому множеству всегда дает значение ложь. Поэтому, например, если утверждение 7Все фиолетовые детали весят более 100 фунтов" истинно, то это необязательно означает, что действительно существуют фиолетовые детали. Заметим, что тождества (верные!) могут использоваться в качестве основы для множества правил преобразования выражений исчисления аналогично алгебраическим правилам преобразования, упоминавшимся в главе 6 и подробно обсуждающимися в главе 17.
Аналогичные замечания также применимы к упр. 7.2 и 7.3. а) верно; б) верно; е) верно (этот пример рассматривался в основном тексте главы); г) верно (следовательно, один квантор может быть определен через другой); д) не верно; е) верно. Обратите внимание, что последовательность одинаковых кванторов — как в тождествах а и б — может быть записана в любом порядке без изменения смысла выражения, тогда как для разных кванторов — как показано в тождестве д — такой порядок имеет существенное значение. Чтобы проиллюстрировать последнее, предположим, что переменные х и у изменяются на множестве целых чисел и р является формулой %ГГ у > х.
Очевидно, что формула ("для всех целых х существует целое у, большее х") дает значение истина, тогда как формула ("существует целое у, большее любого целого х") дает значение ложь. Таким образом, перестановка неодинаковых кванторов изменяет значение выражения. Поэтому в языке запросов, основанном на реляционном исчислении, перестановка неодинаковых кванторов в предложении НБЕНЕ изменяет значение запроса [7.3). а) верно; б) верно. Если поставщик с номером 'Б2' в данный момент не поставляет никаких деталей, исходный запрос будет возвращать все номера поставщиков из отношения Я (включая, в частности, самого поставщика с номером 'Б2', сведения о котором согласно нашему предположению содержатся в отношении Б, но отсутствуют в ЯР).
Если везле заменить переменную ЯХ переменной ЯРХ, то запрос будет возвращать все номера поставщиков, содержащихся в отношении БР. Различие между лвумя формулировками следующее: первая означает "Получить номера поставщиков всех типов деталей, поставляемых поставщиком с номером 'Б2'" (что и требуется), а вторая — "Получить номера поставщиков ло крайней мере одной детали и по крайней мере всех типов деталей, которые поставляются поставщиком с номером ' Б2 мЬ 7.5. а) Получить наименование детали и название горола для леталей, поставляемых для каждого проекта в Париже каждым поставщиком в Лонлоне в количестве менее 500 штук. 6) Результат выполнения этого запроса — пустое множество. 7.6.
Это упражнение очень трудное! Особенно если мы будем учитывать, что вес деталей неуникален. (Если бы их вес был уникален, можно было бы переформулировать запрос так: "Получить все детали, такие, что количество более тяжелых деталей меньше трех".) Упражнение настолько трудное, что мы даже не пытаемся дать здесь полное решение на языке реляционного исчисления. Оно очень хорошо иллюстрирует тот факт, что реляционная полнота является лишь основным критерием выразительной силы языка, но необязательно достаточным. (Следующие два примера также иллюстрируют этот момент.) Подобные запросы обсуждаются в !6.4].
7.7. Пусть РЯА, РЯВ, РБС, ..., РЯп — переменные кортежей, изменяющиеся на переменной-отношенин РАНТ ЯТКОСТОКЕ. Предположим также, что заданная деталь — это деталь с номером 'Р1', Тогда имеем следующее. а) Выражение реляционного исчисления для запроса "Получить номера деталей для всех типов деталей, которые являются компонентами детали с номером 'Р1' на первом уровне входимости" будет таким.
РБА.М1ЮК Р() ННЕКЕ РЯА.МАООК Р() = Р ( 'Р1' ) б) Выражение реляционного исчисления для запроса "Получить номера деталей для всех деталей, которые являются компонентами детали с номером 'Р!' на втором уровне входимости" будет таким. РБВ.М1НОК Р() ИНЕКЕ ЕХ1БТБ РЯА ( РЯА.МАЯОК Р() = Р ( 'Р1' ) АЮ РЯВ.МЫОК Р() = РЯА.М1НОК Р() ) в) Выражение реляционного исчисления лля запроса "Получить номера деталей для всех деталей, которые являются компонентами детали с номером 'Р1' на третьем уровне входимости" будет таким. РБС.М1НОК Р() ННЕКЕ ЕХ1ЯТБ РЯА ЕХ1ЯТЯ РЯВ ( РБА.МЫОК Р() = Р ( 'Р1' ) АНО РЯВ.МЫОК Р() = РЯА.М1НОК Р() АНО РЯС.МА!ОН Р() = РЯВ.М1НОР. Р() ) И т.д.
Выражение реляционного исчисления для запроса "Получить номера деталей для всех деталей, которые являются компонентами детали с номером 'Р1' на и-м уровне входимости" будет таким. РБп.М1НОК Р() ИНЕКЕ ЕХ1БТБ РЯА ЕХ1ЯТЯ РЯВ ... ЕХ1ЯТЯ РЯ(л-1) ( РЯА.МАЯОК Р() = Р ( 'Р1' ) АНО РЯВ.МАЯОК Р() = РБА.М1НОК Р() АЮ РЯС.МАЯОК Р() = РЯВ.М1НОК Р() АЮ АНО РЯп.МАЯОК Р() = РЯ(п-1).М1НОК Р() ) Глава 7. Реляционное исчисление 285 Для построения отношения РйЕТ ЬТЯТ все результирующие отношения из пп. а, б, а, ..., и необхолимо объединить.
Проблема заключается в том, что невозможно записать и таких выражений, если значение и неизвестно. Следовательно, запрос разузлования детали является классической иллюстрацией залачи, которая не может быть сформулирована с помощью отдельных выражений на языке, обладающем лишь свойством реляционной полноты, т.е. на языке, который не является более мощным, чем реляционное исчисление (или алгебра).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
