Ориентированный ациклический граф вывода

Ориентированный (directed) ациклический (acyclic) граф (DA-граф) – это орграф, не имеющий циклов. Помеченный DA-граф – это DA-граф, каждой вершине которого поставлен в соответствие некоторый элемент из множества меток L.

Определение. Пусть F – множество ФЗ над схемой R. DA-граф вывода над F – это DA-граф, помеченный символами атрибутов из R и построенный по следующим правилам.

1. Множество изолированных вершин является DA-графом вывода над F.

2. Пусть DA-граф вывода над F содержит n вершин _i с метками A_i и в F существует ФЗ A₁A₂…A_kCZ (k  n). Определим новый граф, добавив к исходному DA-графу вывода вершину u с меткой C и дуги (₁, u), (₂, u),…, (_k, u). Полученный граф является DA-графом вывода над F.

3. Никакой другой граф не является DA-графом вывода над F.

Сокращённо DA-граф вывода над F называют DDA-графом над F (от английского derivation directed acyclic). Любой DDA-граф получается однократным применением правила (1) и многократным применением правила (2).

Пример

Пусть F – множество ФЗ из предыдущего примера: F = {ABE, AGJ, BEI, EG, GIH}. Ниже представлены разные этапы построения DDA-графа над F.

Конец примера

Определение. Пусть H – DDA-граф, содержащий вершину , которая не имеет входящих дуг. Тогда  называется начальной вершиной. Начальная вершина добавляется с помощью правила (1).

Определение. Пусть H – DDA-граф над F. H называется DDA-графом для XY, если X – множество меток начальных вершин и каждый атрибут в Y – метка вершины в H.

Определение. Используемым множеством в DDA-графе H над F U(H) называется множество всех ФЗ в F, использованных при применении правила (2) во время построения графа H.

Пример

В предыдущем примере DDA-граф для ФЗ ABAB содержит две изолированных вершины. Его используемое множество пусто.

Конец примера

Теорема. Для множества ФЗ F над R и ФЗ XY следующие утверждения эквивалентны:

1. F |= XY;

2. Существует последовательность вывода на F для XY;

3. Существует DDA-граф над F для XY.

Следствие. DDA-граф H над F для XY с U(H)=G существует тогда и только тогда, когда существует RAP-последовательность вывода на F для XY c используемым множеством G.

В [14] приводится алгоритм, проверяющий принадлежность XY множеству F⁺ (выводимость функциональной зависимости) с временной сложностью O(n), где n – количество ФЗ в F.

Определение реляционной базы данных

Сформулируем определение ключа на языке ФЗ. Ключ для схемы R – это подмножество K  R, такое, что любое отношение r(R) удовлетворяет ФЗ KR, но никакое собственное подмножество K  K этим свойством не обладает.

Будем считать, что схема R некоторого отношения состоит из двух частей: S и K, где S – множество атрибутов, K – множество выделенных ключей. Выделенным ключом может быть, в частности, суперключ. Введём обозначение R=(S, K).

Определение. Пусть U – множество атрибутов. Схемой реляционной БД R над U называется совокупность схем отношений {R₁, R₂,…, R_n}, где R_i=(S_i, K_i), i = 1,2,…, n, ⁿ_i=1 S_i = U, и S_i S_j при i  j.

Определение. Реляционной БД d со схемой БД R называется такая совокупность отношений {r₁, r₂,…, r_n}, r_i = r_i(S_i), что для каждой схемы R = (S, K) из R существует отношение r в d со схемой S и удовлетворяющее каждому ключу из K.

время

Рейс	Время
83	10:00
83	10:00
83	10:00
81	05:00
81	05:00
81	05:00
41	13:00
31	18:00
16	13:00
16	13:00

Пример

рейсы

Пилот	Рейс	Дата
Иванов	83	09.01.2000
Петров	83	11.01.2000
Сидоров	83	13.01.2000
Петров	81	08.01.2000
Федоров	81	09.01.2000
Федоров	81	13.01.2000
Федоров	41	15.01.2000
Петров	31	12.01.2000
Иванов	16	10.01.2000
Сидоров	16	12.01.2000

БД d={рейсы, время} имеет схему R = {(Пилот Рейс Дата, {Пилот Дата}), (Рейс Время, {Рейс})}.

Конец примера