Графы запросов
Графы используются для визуального представления структурированных объектов в ряде областей. Двумя хорошо известными примерами являются использование синтаксических деревьев при конструировании компиляторов и использование графов AND/OR в приложениях искусственного интеллекта. При оптимизации запросов графы используются для представления запросов и стратегий вычисления запросов. Можно выделить два класса графов: объектные графы и графы операций.
В объектных графах узлы представляют объекы, такие как переменные (отношений) и константы. Дуги описывают предикаты, которым эти объекты должны удовлетворять [Bernstein and Chiu 1981; Palermo 1972; Youssefi and Wong 1979]. Объектные графы содержат свойства результатов запросов и поэтому тесно связаны с реляционным исчислением. Графы операций описывают управляемые операциями потоки данных путем представления операций как узлов, связанных дугами, указывающими направление движения данных. В [Smith and Chang [1975]; Yao [1979] графы операций использовались для представления выражений алгебры. На рис. 1 и рис. 2 приведены примеры объектного графа и графа операций соответственно.
Рис. 1. Объектный граф, представляющий запрос из примера
Рис. 2. Граф операций, представляющий запрос из примера
У графов запросов имеется много привлекательных свойств. Визуальное представление запроса способствует более простому пониманию его структурных характеристик. Кроме того, в теории графов имеется много результатов, полезных для автоматического анализа графов, например, обнаружение циклов и свойства древовидности. Наконец, важным достоинством графов запросов является то, что их легко расширять дополнительной информацией. Например, расширение графов деталями физической организации данных предложено в [Rosenthal and Reiner 1982].
