Меню
Главная
УСЛУГИ
Авторизация/Регистрация
Реклама на сайте
Основы реляционной алгебрыАлгебра логикиРеляционная и модальная интерпретация
Основы реляционной алгебрыАлгебра логикиРеляционная и модальная интерпретация
Метод построения модели векторной направленности семантических...Общее описание компании – инициатора инвестиционного проектаОбщее описание модели
Функциональные многозначные MV-зависимостиФУНКЦИОНАЛЬНЫЕ СТИЛИПсихологические аспекты интернет-зависимости
 
Главная arrow Информатика arrow Базы данных
< Предыдущая   СОДЕРЖАНИЕ   Следующая >

Свойства реляционной алгебры

Рассмотрим свойства операций реляционной алгебры [4].

I. Коммутативность:

Унарные операции:

1) ;

2) , еслиА1= А2;

3) , если Аttr(F1)А1;

4) , если Attr(F1)A1.

Бинарные операции:

5) JF(R, S) → JF(S, R);

6) U(R, S) → U(S, R);

7) CP(R, S) → CP(S, R).

II. Ассоциативность бинарных операций:

1) U(U(R, S), Т) → U(R, U(S, Т));

2) CP(CP(R, S), Т) → CP(R, CP(S, Т));

3)

III. Идемпотентность унарных операций:

1), если А = А1, А Í А2;

2), если F = F1 Ç F2.

IV. Дистрибутивность бинарных операций между бинарными:

1) SF(U(R, S)) → U(Sf(R), Sf(S));

2) Sf(DF(R, S)) → DF(Sf(R), SF(S));

3) Sf(CP(R, S)) → CP(Sf(R), S), если Attr(F) Í Attr(S);

4) Sf1 (Jf(R, S)) → Jf(Sf(R), SF(S)), если Attr(F) Í Attr(S);

5) Pa(U(R, S)) → U(Pa(R), Pa(S));

6) Pa(CP(R, S)) → CP(Pa(R), Pa(S)).

V. Факторизация унарных операций:

1) U(Sf(R), Sf(S)) → Sf(U(R, S));

2) CP(Sfr(R), Sfs(S)) → Sf(CP(R, S)), где F = FR Ç FS;

3) JF(SF(R), SF(S)) → Sf(Jf(R, S)), где F = FR Ç FS;

4) DF(Sfr(R), Sr(S)) → Sfr(DF(R, S)), где FR → FS;

5) U(Pa(R), Pa(S)) → Pa(U(R, S));

6) CP(Par(R), Pas(S)) → Pa(CP(R, S)), где A = AR u AS.

Реляционная алгебра в процедуре использования БД

Перечисленные правила используются прежде всего при формировании и оптимизации запросов.

Описание построения БД

Реляционная алгебра больше предназначена для описания процедур запросов (выборки) и обновления. Дело в том, что РА (равно как и РИ, как будет показано позднее) не затрагивают вопросы обеспечения целостности при создании и обновлении БД. Иными словами, они непригодны для того, чтобы СУБД могла автоматически проверить истинность или ложность следствий из заданных в схеме БД [9] ограничений целостности.

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

Это удалось сделать с помощью функционального подхода (формул однозначных {1:1, 1:М} F-зависимостей и многозначных {1:М и прежде всего – М:М} MV-зависимостей) и, как следствие, путем выполнения процедуры нормализации.

F-зависимости обеспечивают переход к первой (ΙΗΦ), второй (2НФ), третьей (ЗНФ) нормальным формам представления данных. MV-зависимости позволяют строить четвертую (4НФ) и пятую (5НФ) нормальные формы.

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

Функциональные (однозначные) F-зависимости

Функциональные зависимости являются обобщением понятия ключа: значения кортежа на одном множестве X атрибутов определяют значения на другом множестве Y атрибутов; X, Y Î R; R – схема отношения R.

Пусть имеется r(R) и X, Y Î R.

Отношение удовлетворяет функциональной зависимости (ФЗ) X → Y, если πY (σх_х (R)) имеет не более одного кортежа для любого (V)x Î X. Проверка проводится так (рис. 4.1): если кортежи t1(X) = t2(X), то должно удовлетворяться условие t1(Y) = t2(Y).

Такие однозначные зависимости называются F-зависимостями. Множество F-зависимостей также обозначается F. Иначе сказанное записывается в виде: F Ì X → Y влечет X → Y или говорят об аксиоме вывода.

Рис. 4.1. F-зависимость

Аксиома вывода (правило): если отношение удовлетворяет некоторым F-зависимостям, то оно должно удовлетворять и другим F-зависимостям.

Пример 4.1. Пусть имеем расписание занятий "Расписание" (День, Время, Аудитория, Преподаватель, Группа). Введем две ФЗ:

f1: День Время Аудитория → Преподаватель Группа,

f2: День Время Преподаватель → Аудитория Группа.

Далее используем следующие ФЗ:

f1: Студент → Курсовая работа,

f2: Студент → Преподаватель,

f3: Преподаватель → Кафедра,

f4: Кафедра → Факультет,

f5: Студент → Факультет.

Пусть R = {a, ..., А}; X, Y, Z, W Î R. Для любого r(R) справедливы следующие аксиомы вывода.

F1. Рефлексивность: X = X. Проекция от селекции πX(σX=х (r)) имеет не более одного кортежа. Например, Студент → Студент.

F2. Транзитивность: если X → Υ и Υ → Ζ, то X → Ζ. Если t1(X) = t2(X), то t1(Y) = t2(Y) по определению. Если t,(Y) = t2(Y), то и t,(Z) = t2(Z). Следовательно, если t1(X) = t2(X), то t1(Z) = t2(Z).

Иначе говоря, из Студент-4 Преподаватель и Преподаватель -4 Кафедра следует Студент → Кафедра.

F3. Пополнение: если X → Y, то XZ → Y.

Из X → Y следует (), что πY(σx=x(R)) имеет не более одного кортежа для "x Î X. Если Z Î R, то σ XZ=xz (R) Í σ X=х (R) и πY(σXZ=xz(R)) Í πY(σX=x(R)) имеет не более одного кортежа.

Следовательно, если Студент → Преподаватель, то Студент Кафедра → Преподаватель.

Или из А → В следует АС → В и AD → В, АВС → В, ABD → В, ACD → В, ABCD → В.

F4. Псевдотранзитивность: если X → Y, YZ → W, то XZ → W.

Если t1(X) = t2(X), то t1(Y) – t2(Y) по определению. Если t1(YZ) = t2 (YZ), то и t1(W) = t2(W). Следовательно, из t1(XZ) = t2(XZ) имеем t1(X) = t2(X) и t1(Z) = t2(Z), t1(Y) = t2(Y), t1(YZ) = t2(YZ) и t1(W) = t2(W). Иначе, если Студент → Преподаватель, Преподаватель Кафедра → Факультет, то Студент Кафедра → Факультет или из A → В, ВС → D следует АС → D.

F5. Аддитивность: если X → Y и X → Z, то X → YZ.

По определению pY(sx=x(R)) и pz(sx=z(R)) имеют не более одного кортежа. Если sYZ(sX=x(R)) имеет более одного кортежа, то хотя бы одна зависимость имеет более одного кортежа.

Следовательно, Студент → Преподаватель, Студент → Кафедра, то Студент Преподаватель → Кафедра или из А → В, А → С следует А → ВС.

F6. Проективность (в определенной степени обратна аддитивности): если X → ΥΖ, то X → Υ и X → Ζ.

По определению pyZ(σX=x(R)) и pz(σX=z(R)) имеют не более одного кортежа. Однако pY(R))) = pY(σX=x(R)) и pY(σx=x(R)) тоже имеет более одного кортежа, т. e. X → Y.

Итак, Студент → Преподаватель Кафедра, то Студент → Преподаватель и Студент → Кафедра или если А → ВС, то А → С и А → В.

Система F1-F6 является полной: с ее помощью можно получить (путем многократного применения) любую F-зависимость для множества F. Аксиомы F2, F5, F6 выводятся из F1, F3, F4. Покажем лишь два вывода.

Транзитивность F2 – частный случай аксиомы F4. Аксиома F5: если X → Y, X → Z, то из F1 следует YZ → YZ, из F4 следует XZ → YZ, из F4 следует X → YZ.

Аксиомы F1, F3, F4 иногда называют аксиомами Армстронга.

Замыканием множества F называется множество функций F+, содержащее все те зависимости, которые могут быть получены применением к F аксиом Армстронга.

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

Лемма. Функциональная зависимость X → Y выводима из аксиом Армстронга, если Y с Х+.

Доказательство приводится в [4].

Вычисление F+ достаточно сложная процедура. Например, если F = (Аt → Вt, ..., Аn → Вп), то F+ включает А → Y, где Y – подмножества множеств {В1, ..., Bn} и их количество составляет 2n.

Более того, если F-множество F-зависимостей над R и X Í R, то в F+ существует зависимость X → Y такая, что подмножество Y максимально, т. e. Z Ì Y для любой другой F-зависимости X → Z в F+.

Если F = {А → D, АВ → DE, СЕ → G, Е → Н}, то можно показать, что (АВ)+= ABCDEH.

Для F = {АВ → С, АЕ → G, ВС → D, D → Е, В → AЕ, EG → К} (АВ)+ = ABCDEGK.

Сложность алгоритма во времени зависит от размера входного множества F-зависимостей. Следовательно, надо стремиться к минимизации F-множества. Это способствует согласованности и целостности БД (меньше проверок при модификации).

Действительно, множество F = {А → В, В → С, А → С, АВ → С, А → ВС} выводимо из множества G = {А → В, В → С}. Говорят, что множество G покрывает множество F (G эквивалентно F или G Î F).

На пути минимизации возникает две проблемы: неизбыточность; устранение постороннего атрибута (редуцирование).

Множество F-зависимостей F называется неизбыточным, если нет F' с F такого, что F' º F. В неизбыточном множестве могут быть посторонние атрибуты, которые могут быть удалены (множество может быть редуцировано).

Пусть имеется множество F-зависимостей F = {Xi → Yi, i = 1, n}. Множество атрибутов Zi Ì Υi называется посторонним в Xi, если (ΧiΖi) →ji. может быть получено в замыкании F+i.

Множество F-зависимостей F называется каноническим, если любая F-зависимость из F имеет вид X → A, a F – редуцировано и неизбыточно.

Множество F-зависимостей F минимально, если оно содержит не более F-зависимостей, чем любое эквивалентное множество F-зависимостей.

Теория F-зависимостей используется при нормализации (1НФ – ЗНФ), однако, кроме F-зависимостей, могут существовать MV-зависимости. Для них используются несколько иные правила.

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Предметы
Агропромышленность
Банковское дело
БЖД
Бухучет и аудит
География
Документоведение
Журналистика
Инвестирование
Информатика
История
Культурология
Литература
Логика
Логистика
Маркетинг
Медицина
Менеджмент
Недвижимость
Педагогика
Политология
Политэкономия
Право
Психология
Религиоведение
Риторика
Социология
Статистика
Страховое дело
Техника
Товароведение
Туризм
Философия
Финансы
Экология
Экономика
Этика и эстетика