Compiler

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

o Compiler_Constants
Константы Компилятора запросов
o Compiler_Types
Типы Компилятора запросов
o 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


Banner for Parallel DBMS Prototype Functions Guider
Справочник по функциям прототипа параллельной СУБД

замечания и предложения направлять по адресу mzym@csu.ru