Оптимизация запросов в системах баз данных
1942e8f8

Табло


Табло, как они были определены Ахо и др. [Aho et al. 1979a, 1979b, 1979c] являются табличной нотацией для подмножества запросов реляционного исчисления, характеризующихся наличием только связанных через AND термов и отсутствием кванторов всеобщности. Таким образом табло-запросы представляют собой частный вид конъюнктивных запросов [Chandra and Merlin 1977; Rosenkrantz and Hunt 1980].

Табло представлют собой специализированные матрицы, столбцы которых соответствуют атрибутам соответствующей схемы базы данных. Первая строка матрицы, сводка (summary), служит тем же целям, что целевой список выражения реляционного исчисления. Остальные строки описывают предикат. Символы, появляющиеся в табло, являются выделенными (distinguished) переменными (соответствующими свободным переменным), невыделенными (nondistinguished) переменными (соответствующими переменным под знаком квантора существования), константами, пробелами и тэгами (указывающими отношения областей определения).

На рис. 3 иллюстрируется конструирование табло, представляющего запрос из Примера 2.1. Процесс начинается с табло для одиночных отношений и продолжается путем комбинирования этих табло в новые табло для все больших выражений. Выделенные переменные отмечаются символами a; невыделенные - символом b.

Рис. 3. Пошаговое конструирование табло T, представляющего запрос из Примера 2.1

Выражения, содержащие дизъюнкцию (объединение множеств) и отрицание (вычитание множеств) могут представляться наборами табло [Sagiv and Yannakakis 1980]. В [Klug 1983] и Johnson and Klug 1983] набора табло используются для представления общих конъюгктивных запросов. Конкретная значимость табло в отношении оптимизации запросов обсуждается в разд. 3.2.



Содержание раздела