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

12.25.Nicolas J.M. Mutual Dependencies and Some Results on Undecomposable Relations Proc. 4th Intern. Conf. on Very Large Data Bases. - Berlin, FDR. - September, 1978. В работе вводится концепция взаимной зависимости, которая в действительности представляет собой частный случай зависимости соединения, не являющейся многозначной или функциональной зависимостью, и включает точно три проекции (как в примере с зависимостью соединения, упомянутой в разделе 12.3). Однако эта концепция не имеет ничего общего с понятием взаимной зависимости, описанным в главе 11.

12.26.0sbom S.L. Towards а Universal Relation Interface Proc. 5th Intern. Conf on Very Large Data Bases. - Rio de Janeiro, Brazil. - October, 1979.

В статье предполагается, что если две или более последовательностей соединений в системе на основе универсального отношения генерируют потенциальный ответ на заданный запрос, то желательным откликом будет соединение всех таких потенциальных ответов. Приводятся алгоритмы для генерации всех таких последовательностей соединений. 12.27.Рагкег D.S., Delobel С. Algorithmic Applications for a New Result on Multivalued Dependencies Proc. 5th Intern. Conf. on Very Large Data Bases. - Rio de Janeiro, Brazil. -October, 1979.

Здесь описано применение результатов работы [12.12] для решения различных проблем, например для тестирования операции декомпозиции без потерь. 12.28.Sagiv Y., Delobel С, Parker D.S., Fagin R. An Equivalence between Relational Database Dependencies and a Subclass of Prepositional Logic JACM.- June,

1981. -28,Jo3.

Это комбинация работ [10.8] и [12.29]. 12.29.Sagiv У., Fagin R. An Equivalence between Relational Database Dependencies and a

Subclass of Propositional Logic IBM Research Report RJ2500. - March, 1979.

Здесь результаты работы [10.8], полученные для функциональных зависимостей,

расширены для многозначных зависимостей. 12.30.Sciore Е, А Complete Axiomatization of Full Join Dependencies JACM.- April,

1982. -29,Jo2.

Здесь результаты работы [12.2], полученные для функциональных зависимостей, расширены для многозначных зависимостей. 12.31.Smith J.M. А Normal Form for Abstract Syntax Proc. 4th Intern. Conf. on Very Large Data Bases. - Berlin, FDR. - September, 1978.

Здесь впервые представлено понятие нормальной формы типа (3,3)НФ.

12.32.Ullman J.D. On Kents Consequences of Assuming a Universal Relation ACM

TODS. - December, 1983. - 8, № 4. l2.33.Ullman J.D. The U.R. Strikes Back Proc. 1st ACM SIGFACT-SIGMOD Symposium

on Principles of Database Systems. - Los Angeles, Calif - March, 1982.

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

12.1. Сначала приведем выражение для МЗЗ для переменной-отношения СТХ.

CONSTRAINT CTX MVD

WITH

(СТХ RENAME COURSE AS С, TEACHER AS T, TEXT AS X)

AS Tl,

(EXTEND Tl

ADD (CTX WHERE COURSE = C) {T} AS A)

AS T2,

(EXTEND T2

ADD (CTX WHERE COURSE = С AND TEXT = X) {T} AS B)

AS T3,

(T3 WHERE A ;t B) AS T4 : IS EMPTY (T4) ;

Для нее существует, конечно, и более простое выражение.

CONSTRAINT CTX MVD СТХ = СТХ {COURSE, TEACHER} JOIN

СТХ {COURSE, TEXT} ;

A вот выражение для зависимости соединения для переменной-отношения SPJ.

CONSTRAINT SPJ JD SPJ = SPJ {S*, P*} JOIN

SPJ {PI, Jl} JOIN SPJ {J#, SI} ;

12.2. Прежде всего обратите внимание, что переменная-отношение R содержит все возможные значения атрибута А в паре со всеми возможными значениями атрибута В. Более того, множество всех возможных значений атрибута А, например S, такое же, как и множество всех значений атрибута В. Следовательно, переменная-отношение R равносильна декартову произведению множества S с самим собой. Эквивалентная формулировка такова: переменная-отношение R равносильна декартову произведению проекции переменной-отношения R по атрибуту А и проекции переменной-отношения R по атрибуту В. Таким образом, переменная-отношение R удовлетворяет следующим многозначным зависимостям (которые не являются тривиальными, поскольку не удовлетворяют всем двойным переменным-отношениям).

{ } А I В

Эквивалентно также утверждение, что переменная-отношение R удовлетворяет зависимости соединения *(А, В) (вспомните, что соединение без общих атрибутов вырождается в декартово произведение его операндов). Отсюда следует, что переменная-отношение R не находится в 4НФ и может быть подвергнута декомпозиции без потерь на две проекции по атрибутам А и В (причем тела этих проекций будут, безусловно, идентичны). Однако переменная-отношение R находится в НФБК (поскольку является полностью ключевой) и не удовлетворяет никаким нетривиальным функциональным зависимостям.

Замечание. Переменная-отношение R также удовлетворяет двум многозначным зависимостям.

А В I { }

В А I { }

Однако они являются тривиальными, поскольку удовлетворяют любым двойным переменным-отношениям с атрибутами А и В.

12.3. Сначала введем три переменные-отношения, первичными ключами которых будут имена торговых агентов, названия регионов и названия товаров соответственно.

REP { REPi, ... } KEY { REPi }

AREA { AREA#, ... } KEY { AREA! }

PRODUCT { PRODI, ... } KEY { PRODI }

Затем представим связь между торговыми агентами и регионами с помощью следующей переменной-отношения.

RA { REPI, AREA! } KEY { REPI, AREA! }

Связь между торговыми агентами и продукцией представим с помощью переменной-отношения RP.

RP { REPI, PRODI } KEY { REPI, PRODI }

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

АР { AREAI, PRODI } KEY { AREAI, PRODI }

Для представления связей, существующих между регионами и продукцией, установим ограничение (назовем его С).

АР = AREA { AREAI } TIMES PRODUCT { PRODI }

Обратите внимание на следующее: в ограничении С подразумевается, что переменная-отношение АР не находится в четвертой нормальной форме (см. упр. 12.2). На самом деле переменная-отношение АР не дает никакой дополнительной информации, которая не может быть получена из других переменных-отношений.

АР { AREAI } = AREA { AREAI } АР { PRODI } = PRODUCT { PRODI }

Тем не менее пока будем считать, что переменная-отношение АР включена в проект создаваемой базы данных.

Условие, что никаких два торговых агента не продают один и тот же вид продукции в одном и том же регионе, означает, что заданной комбинации атрибутов