Выражения с одной переменной
Выражения с одной переменной описывают условия для выборки элементов из одного отношения. Наивный подход к их вычислению состоит в чтении каждого элемента отношения и проверке того, удовлетворяет ли он каждому терму выражения. Поскольку этот подход является очень дорогостоящим при наличии крупных отношений и сложных выражений, используются разнообразные методы для сокращения числа обращений к элементам и числа проверок, применяемых к прочитанным элементам.
Прямой и упорядоченный доступ может обеспечиваться индексами, возможно, объединяемыми с мультисписочными структурами [Welch and Graham 1976; Yang 1977]. С концептуальной точки зрения, индекс является бинарным отношением, связывающим значения атрибутов со ссылками на элементы отношения, обычно называемыми идентификаторами кортежей (TID). Мы отличаем одномерные индексы, которые поддерживают доступ на основе одного атрибута отношения, от многомерных индексов, которые поддерживают доступ через комбинацию атрибутов. Одномерные индексы обычно реализуются на основе структур ISAM [IBM 1966] или B-деревьев [Bayer and McCreight 1972]. Обзор многомерных индексных структур приводится в [Bentley and Friedman 1979]. В число примеров входят работы [Shneiderman 1977] по комбинированным индексам, [Nievergelt et al. 1984] по грид-файлам и [Gardarin et al. 1984] по предикатным деревьям. Хотя пути доступа обычно невидимы для пользователей, сообщается об усилиях по разработке представлений на языках высокого уровня, доступных для тех программистов, которые настаивают на предельной эффективности. Такие языковые построения простираются от TID'ов [Jarke and Schmidt 1981; van de Riet et al. 1981] до абстрактных представлений полных путей доступа [Mall et al. 1984; Schmidt 1984; Tsichritzis 1976].
Число проверок, применяемых к выбранному элементу отношения во время вычисления выражения, может быть сокращено путем преобразований выражения во время выполнения. Оптимизация специального класса выражений, булевских выражений, на протяжении долгого времени является темой исследований в области конструирования компиляторов [Gries 1971].
Булевские выражения (т.е. безкванторные термы, связанные через AND/OR) являются составной частью ряда управляющих структур в языках программирования высокого уровня. Цель оптимизации булевских выражений состоит в генерации кода, который пропускает вычисление компонентов выражения, более не существенных для значения выражения в целом. Например, в операторе
IF A AND B THEN statement_l ELSE statement_2 END,
если терм A уже вычислен как "false", то вычисление терма B является избыточным, и может сразу выполняться ветвь ELSE. Если та же идея применяется для вычисления выражений с одной переменной [Gudes and Reiter 1973; Liu 1976], то запросы можно упрощать во время выполнения.
Другой подход, разработанный для совершенствования эффективности, состоит в изменении порядка вычисления индивидуальных компонентов выражения. Известно несколько алгоритмов для достижения в некоторых ситуациях оптимальных последовательностей выполнения; в некоторых из них предполагается наличие априорных вероятностей значений атрибутов [Hanani 1977], а другие работают без таких предположений [Breitbart and Reiter 1975]. Варрен [Warren 1981] применяет аналогичный метод для оптимизации программ, выраженных в логике.
