Рнс 4.25. Гроф, поароенный по неаротифицироаонной рекурсии

Для сравнения построим 1тэаф для предикатов из примера 4.40 (рис. 4.25). Поскольку прави-Ю I имеет голову Р с отрицательной подцелью О. сушествует отрицательно направленное ребро от Я к О, а поскольку правило 2 имеет голову Q с офиштельно!! подцелью Р. сушеств! отрицательное ребро и в обратном направлении. Значит, намучается негативный цикл и правила не стратифицированы. □

4.4.5 Упражнения к разделу 4.4

Упрожнение 4.4.1. Добавляя или удаляя направленные ребра в днагра.чме,

изображенной на рис. 4.19, можно изменить значения отношения Reaches из примера 4.37, отношения Connects из примера 4.38 или отношений AAreaches и UAreaches нз примера 4.39. Найдете новые значения э .х отношений, если:

а) добавлено новое ребро АА, 1900-2100, направленное от CHI к SF;

b) добавлено новое ребро UA, 900-MOD, направленное от NY к DEN;

c) добавлены два ребра, указанные в пунктах (а) и (Ь);

d) удалено ребро, направленное от DEN к DAL.

Ыпрожнсние 4.4.2. Сформулируйте правила Datalog (используя при необходимости стратифицированное отрицание) для описания указанных ниже изменений понятия последователя нз примера 4.33. При этом можно использовать EDB-отношение SequelOf и lDB-отношение FollowOn, определенные в примере 4.36.

*а) Р(х, у) означает, что фильм у следует за фильмом д-, но не является продолжением фильма X (как определено EDB-отношением SequelOO.

b) Q(x, у) означает, что фильм у следует за х, но не является ни продолжением, нн продолжением продолжения .v.

! с) R(x) означает, что за фильмом х следуют по крайней мере два фильма. Учтите, что они оба .могут быть независимыми друг от друга продолжениями .V. т.е. необязательно, чтобы один был продолжением, а второй продолжением продолжения.

Id) S(x.у) означает, что у следует за .v и при этом имеет не более одного посладолателя.

Упражнение 4.4.3. ODL-классы и их связи можно описать с помощью отношения Rel(dass. rclass. mult), где mult обозначает множественность связей: multi -.многозначная, single - однозначная связь. Первые два атрибута - связанные классы; связь направлена от class к rclass (связанный класс). Например, на рис. 4.26 ПОК1Ш1Ю отношение Rel, прсдстав.чяюшее три ODL-класса нз примера текущего фильма, показанного на рис. 2.6.

Эти .щиныс тоже можно представить в виде 1рафа, узлами которого являются классы, а peOjia направлены от класса к связанному с ним классу и помечены как multi 1ШИ single. На рис. 4.27 изображен граф для данных из рис. 4.26.

Рис 4.26. Предаовление О01-свнзвй с помощью релйционных донньа

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

Предикат P{class. eclass) означает, что в графе классов есть путь* от class к eclass. 1Чожно считать второй из этих классов погруженным в первый, так как в некотором смысле он является частью объекта первого класса.

*! Ь) Даны предикаты: S(class, eclass) и M(class. eclass). Первый означает, что существует однозначное погружение eclass в class, т.е. путь от class к eclass, на котором каждое из направленных ребер имеет отметку single. Предикат М означает, что существует многозначное погружение eclass в class, т.е. путь от class к eclass, содержащий по крайней мере одно ориентированное ребро с отметкой multl.

с) Предикат Q(class, eclass) означает, что в графе классов есть путь от class к eclass, но он в любом случае не является однозначным путем. Здесь можно использовать предикаты, определенные ранее при выполнении этого упражнения.

Star

multi single

Movie Studio

multi multi

Рие. 4.27. Предстовлекив сврзей в виде грофо

4.5 Ограничения на отношения

Реляционная модель предоставляет средства выражения обших ограничений типа ограничений ссылочной иелостности, введенных в разделе 2.5. Фактически, реляционная алгебра открывает широкие возможности и лля выражения огромного множества других офаничений. Как следует из примера 4.44, в реляционной алгебре можно выразить даже функциональные зависимости. Ограничения имеют важное значение в программировании БД. В главе 6 будет показано, как системы БД SQL вводят в действие ограничения, которые можно выразить в реляционной алгебре.

В этом упражнении пустые пути не считаются п1тями .

4.5.1 Реляционная а.1гебра как язык ог1заничений

Есть два сносом применения выражений реляиионной алгебры мя формулировки ограничениП.

1. Еслн R - выражение реляционной алгебры, w R=~ офаничение, которое гласит: Значение выраже1Н1я Л должно быть пустым (другими словами: Результат выражения R не содержит кортежей ).

2. Еслн R и 5-выражения реляционной алгебры, то Л с 5-ограничение, которое гласит: Каждый кортеж нз результата Л должен входить и в результат 5 . Разумеется, результат S может содержать дополнительные кортежи, не порождаемые R.

.Эти способы эквивалентны по своим результатам, но иногда один из них оказывается яснее и удобнее в применении, чем другой. С одной стороны, ограничение Л е 5 можно записать как R-S=fi. Действительно, если каждый кортеж из Л входит и в 5, то R-S пусто. И наоборот, если в Л - 5 нет кортежей, то каждый кортеж из R должен входить и в .5 (в противном случае он входил бы в R-S).

С другой стороны, ограничение R = 0 можно записать как R е 0- Технически 0 не является выражением реляиионной алгебры, но, поскольку для его оценки можно применить другие выражения, например Л-Л, вполне допускается использовать 0 в качестве выражения реляиионной алгебры.

В следующи.ч разделах будет показано, как выразить важные ограничения одним из этих способов. Из главы б вы узнаете, что в программировании SQL наиболее широко применяется первый из них - равенстао с пустым множеством. Однако, как было сказано выше, при желании можно рассуждать в терминах включения одного множества н другое, а затем преобразовать ограничение в стиле равенства пустому множеству.

4-5.2 Ограничения ссылочной целостности

Согласно общему ограничению, названному в разделе 2.5 ссылочной целостностью , значение, возникающее в одном контексте, входит также и в другой, связанный с ним контекст. Ссьшочная целостность - это вопрос придания смысла связям. То есть, если объект или сущность j4 связаны с объектом шш сущностью В, то в должно :>еалыю существовать. Например, в терминологии ODL, если связь в объекте А физически представлена указателем, он ие может быть пустым и должен указывать на подлинный объект.

В реляционной модели ограничения целостности выглядят несколько иначе. Если в кортеже отиошения R есть значение v, то, исходя из целей проекта, можно предполагать, что v будет отдельным компонентом кортежа другого отношения Следующий пример показывает, как выразигь ссьиючную целостность реляционной MOflejm в реляционной алгебре.

Пример 4.42. Рассмотрим два отношения из схемы БД идущих в прокате фильмов:

Movie(title. year, length. inColor, studioName. producerC#) MovieExec(name, address, cert#. netWorth)

Вполне разумно предположить, что производитель каждого фильма входит в от1Юше11не MovieExec. В противном сяхчае что-то не так, и желательно, чтобы система- ре.глизуюшзя реляционную БД, сообщала хотя бы о наличии фильма, о производителе которого в системе нет никакой информации.