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

6.2 Операция соединения JOIN уже рассматривалась выше в этой главе. Операция пересечения INTERSECТ может быть определена так:

А INTERSECТ В = А МINUS (А МINUS В)

или

А INTERSECТ В = В МINUS (В МINUS А)

Эти два равносильных выражения хотя и допустимы, но несколько неудовлетворительны, поскольку А INTERSECТ В - симметричное выражение относительно А и В, а остальные два выражения не симметричны. А вот для сравнения симметричный вариант:

(А МINUS (А МINUS В)) UNION (В МINUS (В МINUS А))

Замечание. Если дано, что отношения А и В совместимы по типу, то

А INTERSECТ В = А JOIN В

Теперь о делении. Пусть А, В, Х и У - обозначения, введенные нами при обсуждении операции DIVIDEВY выше в этой главе. Тогда

А DIVIDEВY В = А [ Х ] МINUS

((A [ X ] TIМESB) МINUS A) [ Х ]

Отметим, что поскольку операцию JOIN можно определить в терминах операции TIМES и операция TIМES является частным случаем операции JOIN, то операцию JOIN можно рассматривать как примитивную вместо операции TIМES.

Отметим также, что, если разрешено использовать дополнения отношений, мы бы могли рассматривать операции UNION и INTERSECТ как примитивные и определить операцию МINUS через них. Обозначим NOT (R) как дополнение к отношению R, т.е. множество всех возможных кортежей, которые совместимы по типу с отношением R, но не принадлежат ему. Тогда:

А МINUS В = NOT ((NOT (А)) UNION (А INTERSECТ В)

6.3 А INTERSECТ: В (см. выше ответ к упр. 6.2).

6.4 Мы даем только интуитивное "доказательство".

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

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

n Объединение - единственный оператор, увеличивающий количество кортежей, кроме произведения, но произведение, кроме этого, также увеличивает количество атрибутов. Пусть отношения А и В должны быть объединены. Обратите внимание, что отношения А и В должны быть совместимы по типу и в их объединении должны быть те же самые атрибуты, что и в них самих. Если мы образуем проuзведенuе отношений А и В, а затем используем проекцию, чтобы уменьшить множество атрибутов в произведении до множества атрибутов в отношении А (или В), мы просто снова вернемся к исходному отношению А (или В). Следовательно, произведение не может быть использовано для моделирования операции объединения, а значит, операция объединения примитивна.

n Вычитание не может быть смоделировано через произведение (поскольку операция произведения увеличивает количество кортежей), через объединение (аналогично) или через проекцию (поскольку проекция сокращает количество атрибутов). Также оно не может быть смоделировано с помощью выборки, поскольку вычитание реагирует на значения во втором отношении, которого не может быть при выборке (в силу природы условия выборки). Следовательно, операция вычитания также примитивна.

n Выборка является единственной операцией, которая позволяет сравнивать значения атрибутов с определенными литералами (т.е. значениями, которые не являются частью какого-либо отношения). Следовательно, операция выборки также примитивна.

6.5 Не совсем. Оператор DIVIDEBY, возможно, больше похож на целочисленное деление в обычной арифметике (т.е. он игнорирует остаток). Пусть заданы два отношения А и В, тогда формирование декартова произведения отношений А и В и затем деления результата отношением В даст нам снова отношение А:

(А TIМES В) DIVIDEВY В = А

Однако деление отношения А отношением В и затем формирование декартова произведения результата с отношением В даст отношение, которое может быть идентично отношению А, но более вероятно, что оно будет некоторым собственным подмножеством отношения А:

(А DIVIDEВY В) TIМES В = А

Давайте условимся последнее обстоятельство в данный момент считать "псевдообратным свойством". Тогда можно сказать, что результат деления отношения А отношением В является таким максимальным подмножеством проекции А[Х](где Х - это множество общих атрибутов в отношениях А и В), что сохраняется псевдообратное свойство.

Отметим, что аналогичное свойство не сохраняется для операции DIVIDEBY PER, описанной в [6.4].

6.6 Ловушка заключается в том, что операция JOIN использует атрибуты CIТY так же, как и атрибуты S# и Р# (в силу нашего определения оператора JOIN). Результат будет подобен следующему:

S#	SNANE	STATUS	CITY	P#	QTY	PNAME	COLOR	WEIGHT
S1 S1 S1 S2 S3 S4	Smith Smith Smith Jones Black Clark		London London London Paris Paris London	P1 P4 P6 P2 P2 P4		Nut Screw Cog Bolt Bolt Screw	Red Red Red Green Green Red

6.7. 2ⁿ. Это количество включает идентичную проекцию (т.е. проекцию по всем n атрибутам, которая дает результат, идентичный исходному отношению А) и "нулевую" проекцию (т.е. проекцию по никаким атрибутам совсем, которая дает в результате TABLE_DUM, если исходное отношение А пустое, и TABLE_DEE в противном случае).

6.8. Да, есть такое отношение, а именно TABLE_DEE. Отношение TABLE_DEE (далее для краткости D ЕЕ) - аналог номер один по отношению к умножению в обычной арифметике, поскольку

R TIМES DEE = DEE TIМES R = R

для всех отношений R. Иначе говоря, DEE - это нейтральный элемент для операции ТIМES (и конечно, для операции JOIN).

6.9 Не существует отношения, ведущего себя относительно операции TIМES в точности аналогично нулю относительно умножения. Однако поведение отношения TABLE_DUM (или сокращенно DUM) несколько сходно с поведением нуля, так как для всех отношений R

R TIМES DUM = DUM TIМES R = пустое отношение с тем же

самым заголовком, что и у R

6.10 Отношениями, которые совместимы с DEE и DUM при объединении, пересечении и вычитании, являются сами отношения DEE и DUM. В результате мы имеем:

UNION	DEE	DUM		INTERSECT	DEE	DUM		MINUS	DEE	DUM
DEE	DEE	DEE		DEE	DEE	DUM		DEE	DUM	DEE
DUM	DEE	DUM		DUM	DUM	DUM		DUM	DUM	DUM

В случае вычитания первый операнд показан слева в таблице, а второй вверху таблицы (для других операторов, конечно, операнды могут меняться между собой). Обратите внимание, как это напоминает таблицы истинности для логических операций ИЛИ, И, И НЕ соответственно; конечно, такое совпадение не случайно.

Рассмотрев затем выборку и проекцию, мы получим:

n Любая выборка из отношения DEE дает отношение DEE, если значение условия выборки равно истине, и DUM, если оно равно лжи.

n Любая выборка из отношения DUM дает отношение DUM.

n Проекция любого отношения по пустому множеству атрибутов дает отношение DUM, если исходное отношение пустое, и отношение DЕЕ в противном случае. В частности, проекция отношения DЕЕ или отношения DUM, обязательно по пустому множеству атрибутов, возвращает исходное отношение.

В следующих замечаниях по делению подразумевается обобщенная форма оператора деления Тодда, которая рассматривается в [6.4].

n Любое отношение R, делимое отношением DЕЕ, в результате дает отношение R. Любое отношение R, делимое отношением DUM, в результате дает пустое отношение с тем же заголовком, что и у отношения R.

n Отношение DЕЕ, делимое любым отношением R, в результате дает отношение R.

n Отношение DUM, делимое любым отношением R, в результате дает пустое отношение с тем же заголовком, что и у отношения R.

n Любое непустое отношение, делимое на себя, в результате дает отношение DЕЕ. Пустое отношение, делимое на себя, в результате дает отношение DUM.

Операции расширения и суммирования:

n Расширение отношения DЕЕ или отношения DUM для добавления новых атрибутов дает отношение с одним атрибутом и тем же количеством кортежей, что и в исходном отношении.

n Суммирование отношения DEE или отношения DUM (обязательно по пустому множеству атрибутов) дает отношение с одним атрибутом и тем же количеством кортежей, что и в исходном отношении.

6.11 Здесь мы имеем дело, конечно, с "независимыми от времени" потенциальными ключами. Имея в виду это предостережение, мы предлагаем в качестве "первого эскиза" множества ответов следующее:

а) любая выборка из отношения А наследует все потенциальные ключи отношения А;

б) если проекция включает любой из потенциальных ключей K отношения А, то К - потенциальный ключ проекции. В противном случае потенциальным ключом является комбинация всех атрибутов проекции;

в) каждая комбинация К потенциального ключа КА отношения А и потенциального ключа КВ отношения В является потенциальным ключом произведения А TlМES B;

г) потенциальным ключом объединения А UNION В является комбинация всех атрибутов;

д) оставлено в качестве упражнения для читателя (пересечение - не примитивная операция);

е) каждый потенциальный ключ отношения А является потенциальным ключом для результата вычитания А МINUS B;

ж) мы оставляем общий случай в качестве упражнения для читателя (естественное соединение - не примитивная операция). Однако заметим, что в частном случае, где соединяющий атрибут в отношении А является потенциальным ключом А, каждый потенциальный ключ отношения В является потенциальным ключом соединения;

з) оставлено в качестве упражнения для читателя (деление - не примитивная операция);

и) каждый потенциальный ключ отношения А является и потенциальным ключом для произвольного расширения А;

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

Однако большинство упомянутых операторов в определенных ситуациях можно некоторым образом усовершенствовать. Например:

n Сочетание атрибутов {S#, Р#, J#} не является потенциальным ключом для выборки SPJ WНERE S# = 'S1'; им является сочетание {Р#, J#}.

n Если отношение А, имеющее заголовок {Х, У, Z} и единственный потенциальный ключ Х, удовлетворяет "функциональной зависимости" У Z (эти обозначения описываются в главе 9), то У является потенциальным ключом проекции отношения А по атрибутам У и Z.

n Если отношение А и отношение В оба являются выборкой из отношения С то каждый потенциальный ключ отношения С является потенциальным ключом объединения А UNION B

И т.д. Более подробно вопрос о наследовании потенциальных ключей обсуждается далее в книге.

6.12 Нет!

6.13 J

6.14 J WНERE CIТY = 'London'

6.15 (SPJ WНERE J# = 'J1') [ S# ]

6.16 SPJ WНERE QTY ≥ 300 AND QTY ≤ 750

6.17 Р [ COLOR, CIТY ]

6.18 (S JOIN Р JOIN J) [ S#, Р#, J# ]

6.19 (((S RENAМE CIТY AS SCIТY) TIМES

(Р RENAМE CIТY AS PCIТY) TIМES

(J RENAМE CIТY AS JCIТY))

WНERE SCIТY ≠ PCIТY

OR PCIТY ≠ JCIТY

OR JCIТY ≠ SCIТY) [ S#, Р#, J# ]

6.20 (((S RENAМE CIТY AS SCIТY) TIМES

(Р RENAМE CIТY AS PCIТY) TIМES

(J RENAМE CIТY AS JCITY))

WНERE SCIТY ≠ PCIТY

AND PCIТY ≠ JCIТY

AND JCIТY ≠ SCIТY) [ S#, Р#, J# ]

6.21 (SPJ JOIN (S WНERE CIТY = 'London')) [ Р# ]

6.22 ((SPJ JOIN (S WHERE CIТY = 'London')) [Р#, J#]

JOIN (J WНERE CIТY = 'London')) [ Р# ]

6.23 ((S RENAМE CIТY AS SCIТY) JOIN SPJ JOIN

(J RENAМE CIТY AS JCIТY)) [SCIТY, JCIТY ]

6.24. (J JOIN SPJ JOIN S) [Р# ]

6.25 (((J RENAМE CIТY AS JCIТY) JOIN SPJ JOIN

(S RENAМE CIТY AS SCIТY)

WНERE JCIТY ≠ SCIТY) [ J# ]

6.26. (((SPJ [ S#, Р# ] RENAМE S# AS ХS#, Р# AS ХР#))

TIМE

((SPJ [ S#, Р# ] RENAМE S# AS УS#, Р# AS УР#)))

WНERE ХS# = УS#

AND ХР# < УР#) [ХР#, УР# ]

6.27 (SUMMARIZE ((SPJ WНERE S# = 'S1') [ J#]) ВУ ()

ADD COUNT AS N) [N ]

Как уже отмечалось, это выражение, к сожалению, не будет возвращать нуль (точнее, отношение из одного атрибута и одного кортежа, содержащего числовое значение нуль), если поставщик S1 не обеспечивает проектов; вместо этого выражение возвратит пустое отношение. Поэтому мы предлагаем следующее более точное решение:

(EXТEND (S WНERE S# = 'S1')

ADD COUNТ ((МATCHING SPJ) (P# ]) AS N) [ N ]

6.28 (SUMMARIZE (SPJ WНERE S# = 'S1' AND Р# = 'Р1')) ВУ ()

ADD SUМ (QTY) AS Q) [Q]

Следующее решение более точное (почему?). Обратите внимание на синтаксис apгументa SUM.

(EXТEND (S WНERE S# = 'S1')

ADD SUМ ((МATCНING SPJ) WНERE Р# = 'Р1', QTY)

AS Q) [Q]

6.29 SUMMARIZE SPJ ВУ (Р#, J#) ADD SUМ (QTY) AS Q

6.30 ((SUMMARIZE SPJ ВУ (P#, J#)

ADD AVG (QTY) AS Q)

WНERE Q > 320) [ P# ]

6.31 (J JOIN (SPJ WНERE S# = 'S1')) [ JNAМE ]

6.32 (Р JOIN (SPJ WНERE S# = 'S1')) [COLOR]

6.33 (SPJ JOIN (J WНERE CIТY = 'London')) [ P# ]

6.34 (SPJ JOIN (SPJ WНERE S# = 'S1') [ Р# ]) [ J# ]

6.35 (((SPJ JOIN (Р WНERE COLOR = 'Red') (P# ])

[ S# ] JOIN SPJ) [ P# ] JOIN SPJ) [S# ]

6.36 ((S [ S#, STAТUS ] RENAМE S# AS XS#, SТAТUS AS XSТAТUS)

TIМES

(S (S#, STAТUS ] RENAМE S# AS УS#, STAТUS AS YSTAТUS)

WНERE ХS# = 'S1' AND XSТAТUS > YSTAТUS) [УS# ]

6.37 J [ J#I ] МINUS

((J [ J#, CIТY ] RENAМE CIТY AS XCIТY)

TIМES J [ CIТY ]) WНERE XCIТY > CIТY) [ J# ]

6.38 (((SUMMARIZE (SPJ WНERE Р# = 'Р1') ВУ (J#)

ADD AVG (QTY) AS QX

TIМES

(SUMMARIZE (SPJ WНERE J# = 'J1') ВУ ()

ADD МАХ (QTY) AS QY) [QY])

WНERE OX> QY) [ J# ]

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

(EXТEND (SPJ WНERE Р# = 'Р1')

ADD AVG ((SPJ RENAМE J# AS ZJ#)

WНERE ZJ# = J# AND РО = 'Р1', QTY) AS QX)

[ J#, QX ]

TIМES

(EXTEND (SPJ WНERE J# = 'J1')

ADD МАХ ((SPJ, WНERE J# = 'J1', QTY) AS QY) [ QY ])

WНERE QX > QY [ J# ]

6.39 (((((SPJ WНERE Р# = 'Р1.') [ S#, J#, QTY ])

RENAМE J# AS XJ#, QTY AS ХQ)

TIMES

(SUMMARIZE (SPJ WНERE Р# = 'Р1') ВУ (J#)

ADD AVG (QTY) AS Q))

WНERE XJ# = J# AND ХQ > Q) [ S# ]

6.40 J [ J# J МINUS

((S WНERE CIТY = ‘London’) [ S# ]

JOIN SPJ JOIN (Р WНERE COLOR = 'Red')) [ J# ]

6.41 J [ J# ] МINUS (SPJ WНERE S# '" 'S1') [ J# ]

6.42 (Р WНERE (МAТCНING SPJ) [ J# ] ≥

(J WНERE CIТY = 'London') [ J# ]) [ Р# ]

6.43 (SPJ [ S#, Р#, J# ] DIVIDEВY J [ J# ]) [ S# ]

Замечание. В этом решении предполагается, что отношение SPJ не пустое.

6.44 (J WНERE (МAТCНING SPJ) [ Р# ] ≥

6.45 S [ CIТY ] UNlON Р [ CIТY ] UNION J [ CIТY ]

6.46 (SPJ JOIN (S WНERE CIТY = 'London’)) [ Р#]

UNlON

SPJ JOIN (J WНERE CIТY = 'London')) [ Р# ]

6.47 (S TIМES Р) [ S#, Р# ] МINUS SР. [ S#, Р# ]

6.48 Мы приводим два решения этой проблемы. Первое, предложенное Хугом Дарвеном (Hugh Darwen), для простоты приводится в пошаговой форме с комментариями.

Т1:= (SР RENAМE S# AS SA) [ SA, P# ];

/* Т1 {SA, Р#}; пocтaвщик SA поставляет деталь Р# *

Т2:= (SР RENAМE S# AS SB) [ SB, Р# ];

/* T2 {SB,Р#}; пocтaвщик SB поставляет деталь Р# */

T3:= Т1 [ SA ]

/* T3 {SA}: поставщик SA поставляет некоторую деталь */

Т4:= Т1 [ SВ ]

/* Т4 {SВ}: поставщик SB поставляет некоторую деталь */

Т5:= T1 TIМES Т4

/* Т5 {SA,SB,P#}; поставщик SA поставляет некоторую деталь

и поставщик SB поставляет деталь Р# * /

T6: = T2 TIMES T3

/* Т6 {SА,SВ,Р#}; поставщик SB поставляет некоторую деталь

и поставщик SА поставляет деталь Р# * /

T7: = T1 JOIN T2

/* Т7 {SA,SB,P#}: поставщики SB и SА поставляют деталь Р# */

T8: = T3 TIMES T4

/* Т8 {SA,SВ}: поставщик SB поставляет некоторую деталь

и поставщик SА поставляет некоторую деталь.*/

Т9:= SР [ Р# ];

/* Т9 {Р#}: деталь P # поставляется некоторым поставщиком */

T10:= Т8 TlМES Т9

/* T10 {SA, SB, P#}:

поставщик SA поставляет некоторую деталь,

поставщик SB поставляет некоторую деталь

и деталь P# поставляется некоторым поставщиком */

T11: = T10 MINUS T7

/* T11 {SA, SB, P#}: деталь Р# поставляется,

но не поставщиками SA и SB одновременно */

T12:= T6 INTERSECT T11

/* T12 {SA, SB, P#}: деталь P# поставляется поставщиком SA,

но не поставляется поставщиком SB */

T13:= T5 INTERSECT T11

/* T13 {SA, SB, P#}: деталь P# поставляется поставщиком SB,

но не поставляется поставщиком SA */

T14:=T12 [ SA, SB ];

/*T14 { SA, SB }:

поставщик SA поставляет некоторую деталь, не поставляемую поставщиком SB */

T15:=T13 [ SA, SB ];

/*T15 { SA, SB }:

поставщик SB поставляет некоторую деталь, не поставляемую поставщиком SА */

T16:= T14 UNION T15;

/*T15 { SA, SB }: некоторая деталь поставляется поставщиком SA или поставщиком SB, но не обоими одновременно */

T17:= T7 [ SA, SB];

/*T17 { SA, SB }:

некоторую деталь поставляют одновременно поставщики SA и SB */

T18: = T17 MINUS T16;

/* T18 { SA, SB }:

некоторую деталь поставляют одновременно поставщики SA и SB,

и нет деталей, поставляемых SA и не поставляемых SB,

и нет деталей, поставляемых SB и не поставляемых SA

- значит, поставщики SA и SB поставляют одни и те же детали */

T19: = T18 WHERE SA < SB;

/* приводим отношение в порядок */

Во втором решении (которое значительно проще!) используются реляционные сравнения. Обозначим через RA отношение S, в котором атрибут S# переименован в атрибут SA, а затем взята проекция по этому атрибуту, аналогично определено отношение RВ. Тогда требуемый результат можно получить с помощью следующего выражения:

[1]Изначально эта операция называлась restrict (дословно – ограничение), но теперь ее чаще называют select (выборка). Однако это последнее название не совсем удачное, поскольку его легко перепутать с оператором SELECT в SQL, а это далеко не то же самое. На самом деле оператор SELECT в SQL гораздо мощнее алгебраической операции restrict – он в основном включает функциональные возможности всех первоначальных восьми алгебраических операций и еще кое-что.

[2] В предыдущих изданиях этой книги, придерживаясь терминологии [6.2], для этого понятия использовался термин union-compatible (дословно-совместимый для объединения), который часто встречается в литературе. Причины, побудившие нас предпочесть термин type-compatible (совместимо по типу), разъясняются далее в этой книги, где также исследуется определение этого термина (и связанное с этим ослабление довольно строгих терминов для операций объединения, пересечения и вычитания).

[3] Необходимо подчеркнуть, что замена Х и У литералами в действительности просто другая синтаксически сокращенная запись. Например, выборку S WHERE CITY=’London’ можно считать сокращением выражения следующего вида: (EXTEND S ADD ’London’ AS LONDON) WHERE CITY =- LONDON. (См. обсуждение оператора EXTEND далее в этой главе.)

[4] Но не совсем. В системе, которая поддерживает логические типы данных, «простые сравнения» могут также содержать имя атрибута или литерал этого типа данных.

[5] В системе должен быть определен домен атрибута Z. Обсуждение этого вопроса (и многих связанных с ним) будет продолжено далее в этой книге.

[6] В действительности в предыдущем издании этой книги (как и в языке SQL – см. главу 8) использовалось ключевое слово GROUPBY вместо BY, но слово GROUPBY имеет несколько процедурный подтекст, и в любом случае слово BY короче.

[7] Как и в случае с оператором EXTEND, в системе должен быть определен домен для нового атрибута Z. И опять обсуждение этого вопроса (и многих связанных с ним) будет продолжено далее в этой книге.

[8] Как неоднократно упоминалось в этой главе, данная операция также служит основой для операций выборки (т. е. запросов).

[9] Однако обратите внимание, что новые условия не являются условиями выборки в терминах определения, данного выше в этой главе. На самом деле наши объяснения умышленно упрощены. В действительности необходимо сделать следующее. Вначале нужно сделать допустимым атрибуты, значения которых являются отношениями (и это нужно сделать без нарушения требований нормализации!). Далее необходимо усовершенствовать оператор EXTEND так, чтобы он мог генерировать такие атрибуты. После этого можно использовать эти атрибуты для сравнения при выборке обычным образом. Более подробно этот вопрос будет обсуждаться в последующих главах книги.