Информатика и выч. техника \ Системы управления базами данных

Изучение основных алгоритмов теории реляционных баз данных, страница 6

Если  ,- реляционные выражения со схемами  и  соответственно, условие

выбора  представимо в виде , где  определено только на атрибутах из,  - только на атрибутах из,  - на атрибутах из и, то

 .

  1. Перестановка проекции  с объединением

Если  ,- реляционные выражения со схемой  и , то

.

Для операций пересечения и разности справедливо соотношение «содержится»:

,

.

  1. Перестановка проекции  с соединением

Если  ,- реляционные выражения со схемами  и  соответственно и , то

, где

,

.

Данные законы используют для модификации запросов к БД, заданных в форме реляционных выражений. Цель модификации  - эффективность вычислений. Учитывают следующие особенности реляционных операций:

1)  селекция уменьшает число кортежей в операнде;

2)  проекция уменьшает число атрибутов в схеме операнда;

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

Приложение 2

Вычисление Х+. Проверка принадлежности к F+.

Вычисление Х+ (замыкания  над F) можно выполнить по следующему

алгоритму SX+  (рис.2.1).

Алгоритм SX+ (X, F)

Вход:  X - множество атрибутов;

F - множество ФЗ,   определенное на R.

Выход: замыкание X над F.

Begin

    OLD :=Ø; NEW :=X;

    While NEW ≠ OLD do begin

OLD :=NEW;

For каждая ФЗ W →   do

    If NEW  then NEW: = NEW

End;

     Return (NEW)

End.

Рис. 2.1

Правильность алгоритма SX+ вытекает из правил вывода F1-F6 (почему?). Сложность алгоритма по времени есть O(nm2), где n=|R|, m=|F|.

Используя теорему 3 и алгоритм SX+ (X, F), легко выполнить проверку принадлежности

Скачать файл