Compiler

Компилятор запросов

Compiler_Constants

Константы Компилятора запросов

Compiler_Types

Типы Компилятора запросов

Compiler_Functions

Функции Компилятора запросов

Компилятор запросов выполняет построение дерева запроса. Язык запросов прототипа параллельной СУБД основан на использовании аппарата реляционной алгебры. Поддерживаются следующие операции реляционной алгебры: тета-выборка и естественное соединение.

Операция тета-выборки (RESTRICT) определяется четверкой

{номер атрибута, номер отношения, оператор тета, литерал}. 

Номер атрибута указывает атрибут, по которому осуществляется выборка. Номер отношения указывает отношение, из которого выбираются кортежи. Скалярный оператор сравнения тета (>, < и т.д.) указывает тип сравнения значений соответствующего атрибута с заданным литералом (целым числом).

Операция естественного соединения (JOIN) определяется тройкой

{номер атрибута, номер отношения1, номер отношения2}.

Номер атрибута указывает, по какому атрибуту осуществляется соединение. Номера отношений указывают, какие отношения базы данных подлежат соединению.

Формальное определение операций реляционной алгебры можно найти, например, в книге

Дейт К.Дж. Введение в системы баз данных. - М.: Диалектика, 1998.

Запрос хранится в текстовом файле с фиксированным именем (определяемым в константе QUERY_FNAME). Количество строк в данном файле совпадает с количеством узлов в дереве запроса, которое должно быть построено компилятором. В каждой строке данного файла описан один узел дерева запроса.

Примеры запросов:

Запрос

 
0 J 1 #0 #1

означает

 
R0 JOIN R1 OVER A1

т.е. соединение по атрибуту с номером 1 отношений с порядковыми номерами 0 и 1.

Примечание. Номер 0 в начале строки показывает порядковый номер узла в дереве запроса. Символ # ("решетка") перед номерами 0 и 1 показывает, что в операции соединения участвует отношение базы данных с указанным порядковым номером.

Запрос

 
0 J 2 #2 1
1 R 3 > 10 #3

означает

 
R2 JOIN (R3 WHERE A3 > 10) OVER A2 

т.е. соединение по атрибуту с номером 2 отношения с порядковым номером 2 и выборки кортежей из отношения с порядковым номером 3, имеющих в атрибуте с номером 3 значение больше, чем 10.

Примечание. Номера 0 и 1 в начале строк показывают порядковые номера узлов в дереве запроса. Символ # ("решетка") перед номерами 2 и 3 показывает, что в операции соединения участвует отношение базы данных с указанным порядковым номером. Отсутствие символа # перед номером 1 в описании 0-го узла дерева запроса показывает, что вторым соединяемым отношением является узел дерева запроса с порядковым номером 1.

Запрос

 
0 J 1 1 2
1 R 3 > 10 #2
2 R 0 < 20 #1

означает

 
(R2 WHERE A3 > 10) JOIN (R1 WHERE A0 < 20) OVER A1

т.е. соединение по атрибуту с номером 1 выборки кортежей из отношения с порядковым номером 2, имеющих в атрибуте с номером 3 значение больше, чем 10, и выборки кортежей из отношения с порядковым номером 1, имеющих в атрибуте с номером 0 значение меньше, чем 20.

Запрос

 
0 J 1 1 3
1 R 3 > 10 #2
2 R 0 < 20 #1

содержит синтаксическую ошибку: узел с порядковым номером 0 ссылается на остутствующий в дереве запроса узел с порядковым номером 3.

Формальное описание узла дерева запроса (с помощью формул Бэкуса-Наура):

<узел дерева запроса>::=<порядковый номер строки> <описание операции реляционной алгебры>
<описание операции реляционной алгебры>::=<описание операции выборки> | <описание операции соединения>
<описание операции выборки>::=R <порядковый номер атрибута> <оператор сравнения> <литерал> <отношение>
<описание операции соединения>::=J <порядковый номер атрибута> <отношение> <отношение>
<отношение>::=<порядковый номер строки> | #<порядковый номер отношения>
<оператор сравнения>::= > | < | =
<порядковый номер строки>::=<целое без знака>
<порядковый номер атрибута>::=<целое без знака>
<порядковый номер отношения>::=<целое без знака>

Семантические ограничения:

1. Порядковый номер атрибута может принимать значения от 0 до ATTRIBUTES_IN_RELATION-1 включительно.
2. Порядковый номер отношения может принимать значения от 0 до RELATIONS_IN_DATABASE-1 включительно.
3. Порядковый номер строки файла с запросом может принимать значения от 0 до (2^TREE_LEVEL_MAX)-1 включительно.

Результат выполнения запроса выдается на экран (т.е. не сохраняется в отношении базы данных).

Author:

(c) 2004 М.Л. Цымблер, Л.Б. Соколинский

Version:

1.0 от 30.03.2004 12:50:40

See Also:

DatabaseGenerator PlanGenerator

Alphabetic index