Методы оптимизации выполнения запросов в реляционных СУБД


Логическая оптимизация запросов - часть 15


Outerjoin (R,S;J) = Union (Join (R,S;J), Product (Antijoin (R,S;J), NULL-S)).

Здесь Union - оператор теоретико-множественного объединения, Join - оператор реляционного соединения, Product - оператор декартова произведения, а NULL-S - кортеж из неопределенных значений той же арности, что и S. Попросту говоря, отношение, получаемое в результате внешнего соединения двух отношений, содержит все кортежи, входящие в соединение этих отношений, а если некоторый кортеж первого отношения не соединяется ни с одним кортежем второго отношения, то по нему формируется кортеж результата путем дополнения его неопределенными значениями.

Преобразованный запрос выражается в терминах операций расширенной алгебры, порядок исполнения которых, вообще говоря, может изменяться. При этом не все возможные в принципе варианты выразимы через введенные операции. Для обеспечения максимальной гибкости при преобразованиях введены еще две операции - обобщенные соединение и ограничение. Обобщенное соединение отношений R и S по предикату J, сохраняющее атрибуты X отношения R, определяется как

G-Join (R,S;X;J) = Union (Join (R,S;J),

Product (Delta-Project (Antijoin (R,S;J);X), NULL-YS)), где NULL-YS - кортеж из неопределенных значений над множеством атрибутов Y = R.* - X и S. Если R не содержит дубликатов, то G-Join (R,S;0;J) - это обычное соединение, а G-Join (R,S;R.*;J) - внешнее соединение.

Оператор обобщенного ограничения отношения R по предикату P с сохранением атрибутов X определяется как

G-Restrict (R;X;P) = Union (Restrict (R;P), Product (Delta-Project((R Minus Restrict (R,P));X), NULL-Y)).

В [65] демонстрируется большое количество возможных преобразований с использованием свойств введенных операторов. Кроме тех сложных предикатов SQL, которые рассматривались Кимом, анализируются и предикаты с кванторами EXISTS и NOT EXIST, введенные в SQL уже после написания Кимом его работы. Для точности заметим, что в [65] не рассматриваются преобразования запросов с предикатами типа D в терминологии Кима.

Хотя в [65] предлагается более строгий и последовательный подход, чем в [57], мы сочли необходимым посвятить основную часть этого раздела работе Кима, поскольку, на наш взгляд, она положила начало новому подходу в оптимизации запросов, сформулированных на языке SQL. Пусть эта работа была не вполне корректной и точной, но тем не менее именно она указала новый путь повышения эффективности реляционных СУБД.

| |




Начало  Назад  Вперед



Книжный магазин