Ответы к некоторым упражнениям

7.1. а) верно; б) верно; в) верно; г) верно; д) не верно.

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

Заметим, что тождества (верные!) могут использоваться в качестве основы для множества правил преобразования выражений исчисления аналогично алгебраическим правилам преобразования, упоминавшимся в главе 6 и подробно обсуждающимися в главе 17. Аналогичные замечания также применимы к упр. 7.2 и 7.3.

7.2. а) верно; б) верно; в) верно (этот пример рассматривался в основном тексте главы); г) верно (следовательно, один квантор может быть определен через другой); д) не верно; е) верно. Обратите внимание, что последовательность одинаковых кванторов - как в тождествах а и б - может быть записана в любом порядке без изменения смысла выражения, тогда как для разных кванторов - как показано в тождестве д - такой порядок имеет существенное значение. Чтобы проиллюстрировать последнее, предположим, что переменные х и у изменяются на множестве целых чисел и р является формулой WFF у > х. Очевидно, что формула

FORALL X EXISTS у ( у > X )

( для всех целых х существует целое у, большее х ) дает значение истина, тогда как формула

EXISTS у FORALL х (у > х )

( существует целое у, большее любого целого х ) дает значение ложь. Таким образом, перестановка неодинаковых кванторов изменяет значение выражения. Поэтому в языке запросов, основанном на реляционном исчислении, перестановка неодинаковых кванторов в предложении WHERE изменяет значение запроса [7.3].

7.3. а) верно; б) верно.

7.4. Если поставщик с номером S2 в данный момент не поставляет никаких деталей, исходный запрос будет возвращать все номера поставщиков из отношения S (включая, в частности, самого поставщика с номером S2, сведения о котором согласно нашему предположению содержатся в отношении S, но отсутствуют в SP). Если везде заменить переменную SX переменной SPX, то запрос будет возвращать все номера поставщиков, содержащихся в отношении SP. Различие между двумя формулировками следующее: первая означает Получить номера поставщиков всех типов деталей, поставляемых поставщиком с номером S2 (что и требуется), а вторая - Получить номера поставщиков по крайней мере одной детачи и по крайней мере всех типов деталей, которые поставляются поставщиком с номером S2 .

7.5. а) Получить наименование детали и название города для деталей, поставляемых для каждого проекта в Париже каждым поставщиком в Лондоне в количестве менее 500 щтук. б) Результат выполнения этого запроса - пустое множество.

7.6. Это упражнение очень трудное! Особенно если мы будем учитывать, что вес деталей неуникален. (Если бы их вес был уникален, можно было бы переформулировать запрос так: Получить все детали, такие, что количество более тяжелых деталей меньше трех .) Упражнение настолько трудное, что мы даже не пытаемся дать здесь полное решение на языке реляционного исчисления. Оно очень хорошо иллюстрирует тот факт, что реляционная полнота является лишь основным критерием выразительной силы языка, но необязательно достаточным. (Следующие два примера также иллюстрируют этот момент.) Подобные запросы обсуждаются в [6.4].

7.7. Пусть PSA, PSB, PSC, PSn- переменные кортежей, изменяющиеся на переменной-отношении PART STRUCTURE. Предположим также, что заданная деталь - это деталь с номером Р1. Тогда имеем следующее.

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

PSA.MINOR Pt WHERE PSA.MAJOR Pt = Р ( Pi )

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

PSB.MINOR Pt WHERE EXISTS PSA

( PSA.MAJOR Pt = P ( PI ) AND PSB.MAJOR Pi = PSA.MINOR Pt )

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

PSC.MINOR Pt WHERE EXISTS PSA EXISTS PSB

( PSA.MAJOR Pt = P ( PI ) AND PSB.MAJOR Pt = PSA.MINOR P# AND PSC.MAJOR Pt = PSB.MINOR P# )

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

PSn.MINOR Pt WHERE EXISTS PSA EXISTS PSB ... EXISTS PS(n-l) ( PSA.MAJOR P# = P ( PI ) AND PSB.MAJOR P# = PSA.MINOR Pt AND PSC.MAJOR Pt = PSB.MINOR Pt AND

........................... AND

РЗл.MAJOR Pt = PS(Л-1).MINOR Pt )

Для построения отношения PART LIST все результирующие отношения из пп. а, б,в,...,п необходимо объединить.

Проблема заключается в том, что невозможно записать п таких выражений, если значение п неизвестно. Следовательно, запрос разузлования детали является классической иллюстрацией задачи, которая не может быть сформулирована с помощью отдельных выражений на языке, обладающем лишь свойством реляционной полноты, т.е. на языке, который не является более мощным, чем реляционное исчисление (или алгебра). Частично эту проблему можно решить с помощью оператора TCLOSE, кратко рассмотренного в главе 6 (но только частично). Дальнейшие подробности выходят за рамки этой книги.

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

7.8. Этот запрос нельзя выразить ни в терминах исчисления, ни в терминах алгебры. Например, чтобы выразить его в терминах исчисления, по существу, потребовалось бы уметь выражать нечто подобное следующему.

Существует ли отношение г, такое, что в этом отношении г имеется кортеж t, такой, что t.S# = S# ( SI )?

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

Кстати, обратите внимание, что рассматриваемый запрос - это запрос типа Да - нет (причем, желаемый ответ - чаще всего значение истина). Поэтому читателю может показаться, что запрос нельзя выразить в терминах исчисления или с помощью алгебры, потому что выражения реляционного исчисления и алгебры принимают значения отношений, а не логические. Однако запросы типа Да - нет могут быть выражены в терминах исчисления и алгебры, если они правильно реализованы! Главная трудность заключается в том, чтобы понять, что результаты да и нет (эквивалентные значениям истина и ложь) .могут быть представлены как отношения. Рассматриваемые отношения - это TABLE DEE и TABLE DUM соответственно. Более подробное обсуждение этих отношений приводится в [5.5].

7.9. Для подтверждения реляционной полноты языка SQL необходимо сначала показать, что существуют SQL-выражения для каждой из пяти примитивных операций реляционной алгебры (выборки, проекции, произведения, объединения и вычитания), а затем доказать, что операнды таких SQL-выражений могут, в свою очередь, быть произвольными выражениями языка SQL.