автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование и разработка языковой системы SQL сервера

\ • ' РОССИЙСКАЯ АКАДЕМИЯ НАУК

ИНСТИТУТ СИСТЕМНОГО ПРОГРАММИРОВАНИЯ

/ '' ' ' » г . 1 * \ . *

На правах рукописи УДК 681.3.513

КИМЕЛЬМАН Михаил Леонидович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ЯЗЫКОВОЙ ПОДСИСТЕМЫ SQL СЕРВЕРА

05.13.11 -МАТЕМАТИЧЕСКИЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ МАШИН, КОМПЛЕКСОВ, СИСТЕМ И СЕТЕЙ.

Аз-горвф epav диссертации на соискание ученой с.гепекхх кандидата фпзико-матема.тичсскхх яаух

Москва 1995

Работа выполнена в Институте Системного Программирования Российской Академии Наук..

Научный руководитель кандидат физико-математических наук, доцент С.С. Гайсаряи.

Официальные оппоненты: *

доктор физико-математических наук Серебряков В.А.

кандидат технических наук Кагаловский М.Р.

Ведущая организация: Институт Проблем Информатики РАН.

•. I

I ■ .

Защита состоится ? сЛ^сЦ!_ 1996 тч вч:ас.

на заседании диссертационного совета Д200.50.01 в Институте Системного Программирования РАН, Москса, Б.Коммунистическая 25.:

С .диссертацией можно ознакомится...в библиотеке ИСП РАН. Автореферат разослан п ¿Р ¿у 1996.

Ученый секретарь диссертационного'совета

/С.Прохоров/

ОБЩАЯ ХАРАКТЕРИСТИКА РАБССЫ

Данная диссертационная работа посвящена разработке компилятора SQL свободно распространяемого SQL-сервера. Проект свободно распространяемого SQL-сервера входит в число первых проектов, выполняемых в России под эгидой FSF ("Фонд свободного программного обеспечения" - общественная организация,- гпчпанная в Масоачусетскоы Технологическом Институте и поддерживаемая многими производителями компьютеров - HP, SGI и др.)- Целью этого проекта являлось создание мобильной, -гибкой, настраиваемой системы управления базами данных- С этой точки зрения компилятор языка управления данными, должен быть легко адаптируемым к последующей эволюции как языка, так и подсистемы хранения данных.

Целью диссертационной работы было исследование методов компиляции непроцедурных языков и языков управления базами данных, анализ и выработка схемы компиляции запросов, разработка:компилятора SQL и его технологического окружения.

Актуальность работа определяется прежде всего возраставшими потребностями различных категорий отечественных пользователей в современной многопользовательской реляционной СУБД и практической невозможностью для многих- из них легально приобрести какую-либо качественную зарубежную коммерческую систему по причине чрезмерно высокой стоимости таких систем (по крайней мере для госбюджетных организаций и университетов). Кроме того, в ходе предшествующих проекту исследований, в процессе проектирования системы и ее разработки были применены и развиты наиболее современные методы, выработана технология организации подобных систем и был получен большой практический опыт. Все это может быть с успехом применено в будущих исследованиях и разработках.

В работе получены следующие основные мтучяиа ps-зулыV&VBIZ

— технология генерации исполняемого кода, при которой процедурный план выполнения операторов начинает вырабатываться- на ранних фазах компилятора (решения принимаются, как только извле-

кается необходимая для их принятия информация, а не' откладываются до последней фазы);

- система команд интерпретатора, позволяющая оставлять инварианты внутри .цикла без потери производительности;

- инструментальные средства распознавания и преобразования деревьев промежуточного представления ~ компактные, минимальные, естественные (форма описания соответствует существу представления) . -

В основе построенной системы лежит синтез технологических методой* используемых для компиляции традиционных языков программирования, с идеями и алгоритмами оптимизации запросов и построения эффективных планов;

Существенными особенностями созданной системы является :

- генерация планов и оптимизация запросов для исполнительной системы, использующей предикатные захваты;

- использование интерпретатора без потери производительности;

- реализация базового механизма триггеров; - - компактность кода.

В частности хотелось бы отметить:

- использование компилятором одноуровневого промежуточного представления;

- протокол взаимодействия с клиентом,.позволяющий безболезненно переносить клиентов- в не-ШТХ -среду;

-подсистему, ответственную за отображение интерпретируемого кода, его загрузку и редакцию связей.

Дракглгееехая: ценность рабогви состоит в создании современной мобильной реляционной системы с полной реали- . зацией стандартного языка баз данных, пригодной для построения прикладных информационных систем, инструментальных систем высокого уровня применения в учебных целях и для проведения научно-исследовательских работ. Особое значение имеют свободный характер распространения сисгте'йы вместе с документацией и исходными текста-

ми и наличие отечественного сопровождения и технической поддержки. Следует отметить также, что система разрабатывалась в рамках международного проекта GNU и должна быть включена в Фонд свободного программного обеспечения, доступный программистам всето мира.

На защиту втюсятсл:

- Реализация . компилятора SQL (схема компиляции запросов к реляционной базе данных, техника автоматизации процесса разработки и модификации компилятора);

- технологическое окружение и инструментальные средства;.

- средства оптимизации запросов.

Результаты .работы докладывались на конференции SUUG-93.

КРАТКОЕ С0ДКРЖАНИ2 РА50ТЫ

Работа состоит из введения, пяти глав, заключения и списка литературы. Объем диссертации составляет 66 страниц машинописного текста. Список литературы состоит из 7 9 названий.'

Во введении обосновываются цели и задачи данной работы, указываются основные полученные, результаты и дается обзор всей диссертации.

Первая глага посвящена обзору развития языков управления данными, методов' оптимизации запросов, схем компиляции языков управления данными и используемых для построения " компиляторов инструментальных средств. В этой же главе обсуждается принципы формирования диалекта реализации.

Основным предназначением СУБД является обеспечение эффективного многопользовательского доступа к большим объемам данных. Можно выделить три сравнительно независимые части, вносящие свой вклад в достижение этой цели. Это, во-первых, подсистема хранения данных нижнего уровня, обеспечивающая эффективные формы хранения, размещения и выборки данных - из внешней памяти. В случае распределенной базы данных эта же подсистема отвечает также и за эффективное использование копий данных, вы-

бранных с другого компьютера (кэширование, репликация и т.п.). Вторым элементом, влияющим на производительность СУБД, является блок управления и синхронизации транзакций. От того, насколько стратегия, используемая этим блоком, позволяет отразить реальную зависимость транзакций, зависит уровень параллелизма системы на уровне транзакций и, соответственно, ее производительность. И, наконец, последним.блоком является языковая подсистема, которая должна, . в идеале, о'беспечивать компактный, выразительный, прозрачный и максимально эффективный доступ к данным, используя все возможности подсистемы хранения данных.

Развивающиеся в настоящее время системы третьего поколения основываются на существующем фундаменте реляционных 'систем и двигаются в сторону поддержания сложных структур данных и активных элементов (правил и действий) , встроенной оптимизации запросов к распределенным ресурсам, поддержки современных архитектур (внутренний параллелизм в запросах) , большей открытости и совместимости как друг с другом, так и с новыми аппаратными платформами и операционными системами.

Единственной реальной возможностью для нас была oiiopa на Стандарт SQL'89 с необходимыми уточнениями и расширениями. Ориентация на использование языка Си в качестве основного (и на первых порах единственного) языка со встроенным SQL позволила в первой версии системы ограничиться поднабором типов, определяемых стандартом, которые соответствуют базовым типам данных языка Си. В целом при формировании реализационного диалек-" -та SQL руководствовались следующими требованиями:

— диалект не должен противоречить стандарту SQL'89;

— язык должен быть достаточно мощным, чтобы обеспечить возможность практического использования системы;

— расширения языка должны быть практически оправданы, не должны приводить к чрезмерному усложнению реализации и соответствовать стандарту SQL'92;

- сокращения языка по отношению к стандарту не должны приводить к полной утрате соответствующего механизма в реализации.

Пторая ттятчя содержат ппипанир реализуемого лиалек-та SQL. Описываются его взаимосвязь с объемлющем языком Си, указываются встроенные ограничения и набор операторов манипулирования- схемой и данными.

Диалект данной реализации описывает SQL, рассчитанный на встраивание в Си, и использует ASCII-совместимый набор символов. Диалект допускает использование величин с типами, адекватными базовым типам Си,- а также строк переменной длины. Операции определения данных позволяют создавать и удалять отношения и представления, а также передавать права на операции с ними другим пользователям. Поддерживаемые средства ограничения целостности могут блокировать ввод неопределенных значений и задавать на отношениях ограничения уникальности. Допускается также задание проверочных ограничений на таблице (условий, которые должны выполняться для каждой из строк) и ограничений целостности по Ссылкам.

Операции манипулирования данными включают добавление, изменение и удаление данных из отношений. При выборке данных допускаются объединения (с еозможным удалением дубликатов), соединения и вложенные подзапросы. Допускается сортировка выборки по возрастанию или убыванию. При покортежной обработке данных курсор последовательно выбирает строки полученной в результате запроса таблицы.

Диалект предполагает работу в среде UNIX. Из нее берется идентификатор полномочий (имя пользователя) и имя модуля, ассоциируемого с данной программой на Си со встроенным SQL. Последнее формируется как имя файла, содержащего эту программу, квалифицированное именем пользователя.

Явные операторы подключения к базе данных (CONNECT) диалектом в данной версии не поддерживаются. Подключение .выполняется автоматически к указанному при компиляции серверу SOL. В качестве имени сервера SQL используется сетевое имя компьютера, на котором установлен сервер.

Операторы динамического SQL в явном виде не поддерживаются. Вместо них представлен функционально эквивалентный набор функций.

Третья глава описывает общую архитектуру SQL-сервера и место компилятора в нем. 3 ней рассмотрен функциональный интерфейс исполнительной системы, предложенная система команд интерпретатора и формат исполняемого кода.

Исполнительная подсистема GNU SQL сервера базируется на работе, начатой в рамках проекта кластерной операционной системы и исходно ориентированной на то, чтобы обеспечить основу реляционной СУБД в среде этой операционной системы. Впоследствии уже в рамках проекта GNU SQL-сервера подсистема управления данными и транзакциями кластерной операционной системы (далее ПУДТ) была перенесена в среду ОС UNIX и доработана. Функции ПУДТ включают синхронизацию транзакций, управление хранимыми данными, восстановление после сбоев и т.д. Помимо ПУДТ, исполнительная подсистема включает интерлрета-. тор, который является ее верхним уровнем и ответственен зг вызов функций ПУДТ и организацию сложных запросов.

Система предназначена для работы в распределенных открытых UNIX-подобных системах и следует архитектуре "клиент-сервер". Можно выделить- два слоя процессов БД. Внутренний слой представляет собой группу процессов ПУДТ. Они предоставляют сервисы Синхронизатора, Логического Журнала (модификаций логического уровня)',. Микрожурнала (журнал микроопераций), Буфера (обмены .с диском, захваты буферов) и Сортировщика. Кроме них в ПУДТ входят утилиты восстановления от сбоев и модули транзакций.. Последние являются библиотекой и реализуют внешний интерфейс подсистемы на уровне вызовов функций. Взаимодействие процессов в этом слое осуществляется с помощью обменов сообщениями и разделяемой памяти. Следующий слой образуют работающие на том же компьютере серверные процессы компилятора и интерпретатора запросов SQL. Они .содержат в себе модули транзакций и через них осуществляют доступ к ядру и данным. Сервис, предоставляемый этим слоем, доступен через механизм удаленного вызова процедур. Серверная часть системы содержит также процесс Администратора, который слгдит за состоя- В

нием всех прочих. процессов системы и со'здает по мере необходимости сервисы компилятора и интерпретатора. Этот процесс осуществляет связь с процессами внутреннего слоя с помощью сигналов и передачи сообщений и доступен для внешних обращений через механизм удаленного вызоаа ирицедур й мижет и crib ЗарвГ-ИСхрйрОЗаН Б СйСГсмс как интернетовский демон.

Клиентская часть системы, находящаяся на любом из компьютеров сети, состоит из программы компилятора-клиента и библиотеки, содержащей клиентскую часть интерпретатора.. Для работы клиентской части необходимо, что бы среда поддерживала механизм удаленного вызова процедур (RFC).

Решение об использовании специального интерпретируемого языка без формирования представления операторов SQL в машинных кодах было принято главным образом в целях увеличения мобильности и надежности системы.

Следующими по важности после непосредственно выборки данных из таблицы являются вычисления сложных условий в запросах (простые условия вида "значение поля индекса равно константе" могут быть учтены и раньше), контроль ограничений целостности и поддержка динамического SQL. Такая функциональность достигается генерацией промежуточного интерпретируемого кода. Тут надо отметить , что исполнительная подсистема должна быть.легко переносима на новые платформы и. адаптируема к распределенной работе в сети.

Система команд интерпретатора была построена таким образом, чтобы вынести весь анализ на этап компиляции или, в худшем случае, в код интерпретатора, оставив в генерируемом коде лишь минимальные настройки. При этом требовалось, чтобы она была:

- предельно компактной (команда вводилась, только если была абсолютно необходима или значительно повышала эффективность);

- емкой (если мы обнаруживали часто повторяемую последовательность команд, она заменялась, на одну .

' единственную команду)

- адекватной набору низкоуровневых операций доступа к БД (ПУДТ) и легко адаптируемой к изменениям в нем;

В сформированной системе команд большую часть составляют команды доступа к БД. . Помимо них и команд арифметики и управления, интерфейс системы включает формат скомпилированного кода, и предопределенный контекст . Под последним подразумевается информация о системных таблицах, содержащих сведения о структуре всех таблиц (и своей'собственной в том числе).

Для решения 'этих задач динамической загрузки и редакции связей была написана библиотека, схема которой похожа на "общепринятую сейчас в ЭВМ схему сегментно-страничной адресации. Для настройки межсегментной адресации используется . таблица перемещаемых адресов (relocation table), ассоциируемая с каждым сегментом, и список экспортируемых имен с соответствующими им перемещаемыми адресами для разрешения внешних ссылок. Для организации работы с памятью указанным образом используются примитивы создания, удаления, связывания, сохранения сегментов, выделения, освобождение памяти в сегменте, регистрации экспортируемого имени, перемещаемого адреса и внешней ссылки и функция преобразования виртуальных адресов в физические. .

Интерпретируемый модуль представляет из себя набор объектов. Одий из них обладает зарезервированным именем (.экспортируемым) "Module_JumpTable" и содержит адреса всех объектов, соответствующих операторам"*'SQL Б исход- ~ ном тексте, и служит для идентификации требуемых объектов по номеру оператора. Прочие объекты при взгляде извне представляются как массив описателей точек входа. Содержимое объекта скрываются интерфейсом. Объекты могут обладать именами, зная которые можно получить ссылку на эти объекты. Это особенно полезно при генерации кода для динамических операций модификации по курсору.

Все выражения, требующие вычисления, хранятся отдельно в виде двоичных деревьев, каждый узел которых содержит код узла, тип соответствующего узлу значения и адрес выделенной для этого значения области памяти, а также две битовых маски - зависимостей и изменений -используемых для оптимизации пересчета поддеревьев. Кою

манды интерпретатора содержат ссылки на вершины дере-вьез, которые необходимо вычислить при выполнении команды. Узлы деревьев соответствуют логическим операциям, предикатам сравнения и т.п.

Деревья выражений значительно сократили набор команд интерпретатора. Команды, связанные с вызовом подпрограмм и возвратом результатов, тесно связаны с общей структурой интерпретируемого кода. Основу кода составляют объекты (сканеры), имеющие несколько точек входа и сохраняющие состояние между вызовами. Стандартная команда вызова подпрограммы получает в качестве параметра адрес такого объекта и номер -точки входа. Интерфейс объектов предполагает, что оСъект в начале содержит количество точек входа и массив их описателей. Описатель точки входа представляет из себя адрес точки входа в. модуле и ссылки на описатели входных и выходных параметров. Описатель параметров содержит, в свою очередь, число параметров и массив описателей параметров, состоящих из описателя типа и адреса выделенной для параметра области.

Операции отката и фиксации транзакций не входят в набор команд интерпретатора. Они вызываются либо интерпретатором при гозникновении исключительных ситуаций (rollback), либо активизируются пользователем напрямую, то есть пользовательская программа посылает посылает серверу БД команду на завершение - с откатом или без него.

ЧЕстасрсгз клала посвящена собственно компиляции. В . ней описывается общая стратегия компиляции, её фазы и их задачи. Далее подробно рассматриваются генерируемые блоки интерпретирумого кода и приводятся примеры типичных преобразований. Здесь ;ке подробно рассмотрены задачи оптимизационной части 'и представлен механизм описания оптимизирующих правил.

Компилятор должен преобразовывать декларативный язык с определяемым окружением контекстом в последовательность высокоуровневых интерпретируемых команд. Каждый оператор входного языка является независимым. Код SQL может содержась внешние объекты (переменные Си, например) , реальный типовой контроль для которых компиля-

тором SQL невыполним. Возможна только генерация дополнительных текстов на объемлющем языке, которые позволят в" дальнейшем компилятору объемлющего, языка это прове- . рить . Язык содержит не только операторы манипулирования и описания.данных, но и операторы компиляции этих операторов. Кроме того, при компиляции SQL очень высоко значение оптимизации, поскольку разница .вэффективности между оптимальным и неоптим^льным вариантами кода может составлять несколько порядков. Кроме того., процесс компиляции должен быть "организован так, чтобы новые стра-. тегии оптимизации могли бы добавляться легко и, по возможности", безболезненно. Последнее тем более существенно, что проект является свободно распространяемым и наверняка будет й дальнейшем гмодифицироваться.

Компилятор использует одноуровневое промежуточное представление на- всех фазах обработки оператора SQL. Это представление, с одной стороны, близко к исходному -языку. По мере преобразований в нем появляется несколько дополнительных конструкций (например sort вместо order by) и заполняются дополнительные атрибуты части существующих узлов (идентификаторы используемых индексов в узлах экземпляров таблиц). В результате на последней фазе из этого "почти SQL", представления можно получить желаемый исполняемый код, однозначным образом ■ интерпретируя конструкции промежуточного представления. Для оптимизации вычислений каждый узел условий (и тем более подзапросы) имеет маску зависимостей и лежащее под ним поддерево пересчитывавтся только когда 'это.действительно необходимо. Фактически основной целью всех промежуточных преобразований является перестроение дерева запроса так, чтобы создать иерархию подзапросов, в которой, самые внутренние почти не перевычислялись бы.

На первой фазе (грамматический разбор) выполняется лексический и синтаксический анализ оператора,. представленного на языке SQL, в результате которого строится неполное .дерево внутреннего представления. Это дерево отражает структуру оператора и содержит информацию об именах использованных в операторе объектов (отношений, полей, констант и переменных). Что именно соответствует этим именам и соответствует ли им хоть что-нибудь к этому моменту еще не выясняется. На этой же фазе генерируется код на языке Си, который может

быть использован для замены текста компилируемого оператора SQL в случае статической компиляции. Для части операторов SQL, выполнение которых не зависит от контекста БД (например rollback) , промежуточное представление не. генерируется и их обработка на этой фазе и завершается.

Вторая фаза компиляции (семантический анализ) проводит полного контроль существования использованных таблиц, представлении, столбцов, заменяет имена объектов БД на внутренние идентификаторы и проверяет корректность типов в выражениях. Информация о хранимых в база, данных объектах выбирается из системных каталогов базы данных. На этой же фазе производится контроль прав доступа (для тех операторов, для которых это уместно).

На третьей фазе оператор SQL в своем внутреннем представлении подвергается логической оптимизации. В компиляторе SQL-сервера применяются различные преобразования, "улучшающие" начальное представление операторов. Среди этих преобразований имеются эквивалентные преобразования, после проведения которых получается внутреннее представление, синтаксически эквивалентное начальному (например, приведение запроса к канонической форме). Применяются и семантические преобразования, когда получаемое представление не является синтаксически эквивалентным начальному, но гарантируется, что результат выполнения преобразованного оператора совпадает с результатом оператора в начальной форме при соблюдении ограничений целостности, существующих в базе данных.

Четвертый этап обработки запроса состоит в выборе на основе информации, которой располагает оптимизатор, набора альтернативных процедурных планов выполнения данного оператора в соответствии с его внутреннем представлением, полученным на предыдущей фазе. Кроме того, для каждого плана оценивается предполагаемая стоимость выполнения запроса по этому плану. При оценках используется статистическая информация о состоянии базы данных, корректируемая при каждой модификации данных. Из полученных альтернативных планов выбирается наиболее "дешевый", и именно его внутреннее представление будет соответствовать оОрабетываемому запросу. На этой фазе определяются используемые индексы, генерир\/ются подза-

просы, создающие временные таблицы и соединения из более чем двух таблиц преобразуются в дерево подзапросов, реализующих парные соединения.

На пятой фазе (собственно кодогенерация) по внутреннему представлению наиболее оптимального плана выполнения запроса формируется выполняемое представление плана — модуль из команд интерпретатора.

Последняя, фаза компилятора, работающая только в режиме статической компиляции, сохраняет полученный интерпретируемый модуль в базе данных. Она также генерирует Си-код для раскрытия макровызовов, сгенерированных на фазе грамматического разбора. В этом коде формируется вся информация, необходимая компилятору Си для .контроля типов пёраметров, и подставляются вызовы runtime-библиотеки клиента.

Как уже было' сказано, оптимизация является наиболее неоднозначной частью обработки операторов SQL. Не было ' ни возможности, ни смысла пытаться учесть все возможные способы оптимизации. Вместо этого была разработана. структура, позволяющая легко добавлять новые методы оптимизации по мере необходимости. Ниже описаны основные шаги оптимизации в компиляторе. В пятой .главе описываются инструментальные средства, упрощающие добавление новнх правил в оптимизатор.

С технической точки зрения задачей оптимизатора'является реструктуризация запросов и добавление информации об используемых при сканировании индексах.\ реструктуризация касается в первую очередь соединений, представлений и подзапросов. На выходе оптимизатора ожи- -дается дерево, содержащее иерархию запросов с не более чем парными соединениями с указанием их типа (вложенный цикл, эквисоединение и т.д.), описание буферных временных таблиц, типов и параметров сканирования таблиц и прочие данные необходимые для прямой генерации кода.

На первом шаге запросы упрощаются и приводятся к более декларативному виду.- Базовыми элементами, здесь является поднятие представлений, спуск предикатов, приведение условий к КНФ,4 приведение простых предикатов к виду "Col op Expr" и свертка константных выражений. В качестве основы для преобразования запросов взята система лргвил, предложенная в Starbuxst, Эти правила вы-

годно отличаются тем, что корректно отслеживают порождение дубликатов. Все подзапросы тем или иным способом сводятся к подзапросу Exist. (Если подзапрос должен порождать в точности одну строку, то это отмечается специальным* флагом). Отдельный случай представляют собой операторы групповой вставки, модификации и удаления. Эти операторы в ряде случаев необходимо переформулировать , разделяя выборку по условию и собственно операцию модификации данных." Типичным примером может служить оператор увеличения уникального ключа на константу для зсех записей таблицы.

Следующие 2 шага традиционной схемы (генерация возможных методов реализации и полный перебор всех вариантов с оценкой стоимости для поиска наиболее дешевого) в нашем случае объединены в одну. Сборка оптимального плана выполнения запроса происходит снизу вверх. Сначала анализируются и формируются оптимальные планы вычисления подзапросов и вычисляется их стоимость. Стоимость формируется в виде "X (cost(i)*T(i)) " формулы зависимости от внешних объектов, что позволяет учитывать перевычисление подзапросов при изменении порядке сканирования внешних объектов. С другой стороны, свойство деревьев условий содержать маски зависимостей позволяет при выполнении обходить перевычисление подзапросов, если внешние объекты не изменялись. После этего генерация гланов и выбор наиболее дешевого повторяется для объемлющего блока. Эта схема значительно сокращает пространство межблочного перебора, но блокирует такие варианты оптимизации, как близкие к эквисоединению алгоритмы сканирования таблиц подзапроса, хотя надо заметить, что подобные случаи довольно редки. Для сокращения затрат времени на поиск оптимального плана внутри блока (оптимизация сканирования и построение дерева соединений) используются методы отсечения по текущему минимуму (рассматриваемый вариант. отбрасывается, если нарастающая оценка стоимости превышает стоимость уже выбранного варианта), и времени (время компиляции не должно превышать оценку наилучшего времени выполнения). Кроме того для вычисления затрат на выполнение плана сначала делаются частичные и полная оценки этих затрат снизу, а в каадоы варианте отсчет идет относительно за-

ранее вычисленного минимума, что позволяет быстрее обнаруживать неэффективные варианты.

Оценки стоимости выборки выполняются на основе хранимой в БД статистики. Для каждого отношения в БД хранится количество используемых -страниц, количество .строк, а также статистическая информация по столбцам отношения и по индексам. Для индексов хранится глубина индекса и общее число страниц. Статистическая информация о столбцах включает минимальное и максимальное значения. Обновление данных происходит автоматически по мере модификации•данных.

Пятая глава представляет kitty: инструмент для описания правил трансформации деревьев. Этот программа позволяет встраивать в тексты на Си описания деревьев для их генерации и/или распознавания. При разработке генератора мы ставили перед собой-следующие цели:

- минимальность - генератор должен максимально опираться на уже имеющийся программный код;

— ненавязчивость - при использовании генератора программист должен иметь столько свободы сколько ему нужно;

- простота в использовании - входные конструкции генератора должны быть самоочевидны, а их использование смотреться естественно в тексте пррграмм;

'.'v

— гибкость - генератор должен легко настраиваться на изменения, происходящие с.библиотекой поддержки деревьер и вообще быть легко адаптируемым к новым требованиям.

Kitty считывает правила преобразования, написанные в том же формате, что и дампы деревьев, и генерирует код на С, содержащий функции распознавания и преобразования деревьев. Эти конструкции могут считываться как из отдельного файла, так и из файла, содержащего С программу, причем в последнем случае kitty работает как препроцессор. Kitty поддерживает в качестве допустимых действий генерацию новых деревьев, еызое других правил,

подстановку произвольного кода на С, а также выполнение некоторых базовых операций с деревьями.

В шаблонах правил kitty можно задавать коды узлов, конкретные значения атрибутов, проверять битовые флаги или задать имя функции, проверяющую некоторое достаточно сложное условие на узел и возможно все поддерево. При выполнении сгенерированных kitty процедур от:; 2=6-лоны вновь будут созданы и переданы для сравнения вместе с входным деревом специальной функции сравнения библиотеки поддержки. Кроме того, в режиме препроцессора kitty воспринимает и отдельно стоящие в тексте на Си конструкторы деревьев. При записи конструкций kitty в тексте на Си они предваряются стоящим в первой, позиции символом '#' или должны начинаться с последовательности ' #{'. Для спецификации внешних.переменных в этом режиме используется конструкция '<var>' при задании атрибутов, ссылки вида (Ор:п) при задании ссылок на узлы (массив л0р' необходимо предварительно вручную проинищйшизиро-вать) или специальных узлов Ccode.. Ниже рассмотрен пример добавления списка сыновей и описателя столбца к уже имеющимся сыновьям заданного дерева.

В процессе эксплуатацгта kitty выяснилось, что ее. используют в режиме препроцессора существенно активнее, чем это предполагалось при разработке. Основные проблемы связанц с ограниченным числом и не слишко.-i мнемонич-ным именованием локальных переменных правил. Некоторую проблему в Kitty представляла генерация значений для атрибутов узлов-, что было изменено в последней версии системы. Однако несмотря на это данный инструмент оказался достаточно удобен для большинства наших задач,-легко вписался в систему и позволил значительно сэкономить время при описании алгоритмов преобразования деревьев.

Основные полученные результаты заключаются в следующем:

1.Разработан мобильный компилятор .свободного SQL. сервера, поддерживающий стандарт языка SQL 1989 г.

и частично 3 992.

2.3 разработке применены современные средства оптимизации запросов, включая методы семантической и логической оптимизации, а также технологические •средства построения компиляторов..

3.Построено, технологическое окружение компилятора языка запросов. Спроектированы и разработаны необходимые инструментальные средства.

В целом это привело к мобильности, гибкости, компактности и расширяемости полученного кода компилятора. В настоящее время система находится на фазе бета-тестирования. Ближайшие перспективы - настройка системы, повышение ее эффективности и расширение для поддержки более полного диалекта языка. В дальнейшем 'систему предполагается развивать - для поддержки распределенных БД, объектно-ориентированных расширений и в ка-" честве основы для различных экспериментов.

Лично автором осуществлялась разработка стратегии компиляции и инструментальных средств. Реализованы фазы лексического и грамматического разбора, логической оптимизации, библиотеки поддержки и kitty.

Автор приносит свою искреннюю благодарность .своим ксллегам Е.В.Воинову, К.В.Дышлевому, В.Н.Пономаренко,

A.B.Яхину, О.В.Дмитриевой за постоянную поддержку, внимание и терпимость в течении проекта и без ежедневного труда которых он вряд ли был бы.осуществим. Мне особенно хотелось бы поблагодарить руководителя_ группы С.Д,Кузнецова и моего научного : руководителя С.С.Гайсаряна за внимание и -готовность отвечать 'на мои вопросы, а также обсуждать мои не всегда внятные идеи. Я также весьма признателен руководителю института

B.П.Иванникову, чья поддержка и понимание наших проблем позволила нам завершить эту работу.

По теме диссертации опубликованы следующие работы:

1. Е.В-Воинов, С,С.Гайсарян, О.Л.Дмитриева,

К.В.Дышлевой, Н.Д.Кимельман, С.Д.Кузнецов,

В.Н.Пономаренко, А.Л.Рыбаков. Свободный SQL-сервер: состояние дел и ближайшие планы /Тезисы докладов международной конференции SUUG-ЭЗ. //Москва, МЦНТИ, SDUG, 1?93.

2. Е.В.Воинов, С.С_Гайсарян, ' О.JI..Дмитриева,

К.В. Дыпшевой, М.Л.Кгаяельыан, С.Д.Кузнецов,

В.Д .Покомаренко, А ..Л .'Рыба ков. Российский проект свободно распространяемой СУБД. / ж."Открытые Системы". Осань 1993.

3_ М.Кимельман*А.Яхин. "Kitty; Управляемый-, правилами генератор преобразователей деревьев". /, вып. ■"Вопросы Кибернетики - приложения системного программирования". // сборник ВК-180, РАН, Москва, . 1995.

4. К.Дылшевой, М»ЗСимел ьман "Оптимизация запросов в GNU SQL Сервере". Г в печати. вьго. "Вопросы Кибернетики - приложения системного программирования" // РАН, Москва 1996.

Подписано в печать 15.04.96 Заказ № 4 6/174 Тираж 100 экз.

Ротапринт НПО им.Лавочкина