Оптимизация формулы реляционной алгебры

При оптимизации формулы используются следующие правила:

1. Если условие F является конъюнкцией нескольких условий ( ), то переместить каждую селекцию внутрь декартова произведения, используя законы 1, 4, 6, 7, 8.

2. Переместить каждую проекцию внутрь декартова произведения, используя законы 1, 3, 5, 9, 10.

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

.

В результате использования правил 1–3 формула реляционной алгебры (5.1), соответствующая исходному запросу, преобразуется в следующую формулу:

, (5.2)

где

– условие, сформулированное в исходном запросе SELECT;

f – условие соединения подзапросов {Q_i}.

Подчеркнутые в приведённой выше формуле отношения Q₁, …, Q_n имеют меньшую размерность, чем исходные отношения R₁, …, R_n , и потому запрос по формуле (5.2) выполняется быстрее, чем по формуле (5.1).

По формуле (5.2) можно построить логический план, представленный на рис. 1.1.

Рис. 1.1. Логический план выполнения запроса, соответствующий формуле (5.2)