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

Российская Академия Наук Институт проблем информатики

На правах рукописи

ЗАДОРОЖНЫЙ Владимир Иосифович

УДК 681.3.016'

Поддержка развитых логических языков

запросов в дедуктивных базах данных

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 1992

Работа выполнена в Институте проблем информатики Российской Академии Наук

Научный руководитель

доктор физико-математических наук, профессор Л.А. Калиниченко

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

доктор технических наук, профессор А.Л. Щерс; кандидат физико-математических наук, Н.В. Сомин

Ведущая организация - Научно-исследовательский

вычислительный центр Московского Государственного Университета

(НИВЦ МГУ)

Защита состоится "_" _ 19 г. в - часов нь

заседании специализированного совета Л 003.50.01 при Институте проблед/ информатики Российской АН по адресу: 117334, ГСП-1, г.Москва, В-334 -ул. Вавилова, 30/6.

С диссертацией можно ознакомиться в библиотеке Института проблеи

«

информатики РАН.

Автореферат разослан " Ж" Ж,

Ученый секретарь специализированного совета доктор технических наук

апсс'"')« •>•>;'.'

! ;

Общая характеристика работы этугУ!упн!тьп])()Пл"М!Л.С'кол1)к(10!1|Пуд(, м,|гп!](|П|)(н. решение проблем

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

Принципиальные проблемы создания сред информационных ресурсов, >торые могли бы взаимодействовать для совместного решения задачи (ин-роперабельных информационных ресурсов), исследуются в контексте про-та СИНТЕЗ (Система ИНТЕграции Знаний). Проект СИНТЕЗ разраба-лвается в ИПИРАН в целях обеспечения однородного представления и [тегрированного использования разнообразных баз данных, знаний и про->амм, накопленных в организациях и составляющих их информационный сурс.

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

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

нисходящем построении дерева доказательства, в Дейталоге использует восходящая схема вычислений (вычисление наименьшей неподвижной т< ки программы). При этом строится все множество логических следствий заданной совокупности утверждений. В "чистом" Дейталоге также отс1 ствуст отрицание, а в качестве термов допускается использование тол! переменных и констант. Концепция чистого Дейталога, сыгравшая важн роль в решении теоретических проблем, оказалась малопригодной на пр; тике. За последние годы в области ДБД имеется существенный прогре связанный главным образом с созданием целого ряда логических языг запросов, расширяющих чистый Дейталог целым рядом особенностей (< рицание, встроенные предикаты, процедурные средства управления п] граммой, использование новых моделей данных и т.д.). Однако при эт усложняется семантика запросов и возникают дополнительные проблег. связанные с корректностью и эффективностью вычислений.

Решения, принятые в проекте СИНТЕЗ, находятся в соответствии с ] следними достижениями в области дедуктивных объектно-ориентироваш языков запросов, к классу которых относится логический язык систс] СИНТЕЗ.

Логический язык системы СИНТЕЗ использует в качестве основы п> множество языка многосортной логики предикатов. При этом в телах п] вил может применяться широкий класс формул логики первого поряд включающих кванторы, импликацию и конструкции специального ви, Кроме того, язык характеризуется такими возможностями как рекурс группирование, использование временной информации и уникальной ид тификации объектов. Средства языка СИНТЕЗ характеризуют целый кл. дедуктивных языков запросов. Далее при упоминании языка СИНТЕЗ I дет подразумеваться также класс характеризуемых его средствами язык Для данного класса языков актулыгой является задача определения стро] семантики запросов, сохранения эффективности и безопасности вычис ний. В настоящее время эти вопросы изучены недостаточно.

Цель и задачи работы. Целью диссертационной работы является £ работка методов и программных средств для поддержки развитых ло: ческих языков запросов (характеризуемых средствами языка СИНТЕЗ дедуктивных базах данных.

При этом решались следующие задачи:

1. Определение вычислительной семантики программ логического языка

СИНТЕЗ

2. Разработка эффективной стратегии выполнения логических СИНТЕЗ-программ, основанной на методе магических множеств

3. Разработка претранслятора логических СИНТЕЗ-программ, обеспечивающего контроль их корректности и оптимизацию выполнения.

Методы исследования. При работе над диссертацией использовались методы математической логики и общей алгебры.

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

• определен базовый метод выполнения логических СИНТЕЗ-программ, основанный на вычислении наименьшей неподвижной точки задаваемого программой оператора непосредственного следования

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

• расширено определение восходящего метаинтерпретатора Дейталог-программ и на его основе определена нисходящая схема выполнения СИНТЕЗ-программ. Сформулирована и доказана теорема о локальной стратифицируемости расширенного метаинтерпретатора.

• разработана методика переписывания логических СИНТЕЗ-программ по принципу магических множеств. При этом введено понятие существенной формулы предиката, на основании которой определяются

соответствующие дополняющие отношения. Приведен алгоритм построения существенной формулы, основанный на анализе контекстов вхождений предикатов в тело правила. Рассмотрен метод магических множеств для логических СИНТЕЗ-программ, а также более эффективный улучшенный метод магических множеств.

Практическая ценность полученных результатов. Полученные в работе результаты представляют собой методологическую основу для организации дедуктивного вывода в базах данных, для класса логических языков, подобных СИНТЕЗу. На базе этих результатов разработан пре-транслятор логических программ языка СИНТЕЗ, который осуществляет анализ программ на допустимость, обеспечивает контроль безопасности программ и выполняет переписывание программ по методу магических множеств. Важной функцией прстранслятора является обеспечение работы приложений, использующих рекурсивные запросы к базе информационных ресурсов. Результаты работы внедрены в проект СИНТЕЗ, разрабатываемый в соответствии с планами Российской Академии Наук и по программе Информатизация России.

Апробация работы. Основные положения работы докладывались на научных семинарах по проекту СИНТЕЗ в Звенигороде, Бердянске, Киеве, Москве (1991, 1992); Всесоюзном научно-техническом семинаре "Программное обеспечение новых информационных технологий" (Тверь, 1991); о Всесоюзной конференции "Системы баз данных и знаний" (Львов, 1991); 2 Международной конференции "Deductive and Object-Oriented Databases" (Munich, 1992), Международном семинаре "Методы конструирования программ" (Планерскос, Крым,1992).

Публикации. По материалам диссертации опубликовано пять печатных работ и выпущен один научно-технический отчет.

Структура работы. Диссертация состоит из введения, четырех глав и заключения (118 страниц) в формате машинописного текста, куда входит: рисунков и таблиц - 22, список литературы из 90 наименований. Оригинал-макет диссертации подготовлен автором при помощи системы типографского набора 1ДТ]?Х.

I Содержание работы

> первой'главе содержится введение в дедуктивные базы данных, опреде-ены основные понятия, дан обзор исследовательских прототипов по ДБД, в онтексте которого проведено общее рассмотрение средств языка СИНТЕЗ.

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

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

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

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

запросов и делает их более удобными для пользователя.

Добавление указанных особенностей требует дополнительных исслех ваний по определению строгой семантики запросов, сохранению эффект!: ности и безопасности вычислений. В настоящее время эти вопросы изучи недостаточно. В частности было показано, что реляционная алгебра, р; ширенная оператором наименьшей неподвижной точки (LFP-onepaTopoj эквивалентна логике хорновских дизъюнктов без функциональных симг лов. Однако возникает целый ряд проблем при вычислении LFР-опсрлго в нехорновских базах данных. Например, наличие в телах правил констр) ции отрицания может повлиять на монотонность вывода. Исключить таи влияние часто удастся путем задания строгого порядка вычисления прав (стратификация программы). В следующей главе понятие стратификац рассматривается более подробно в контексте СИНТЕЗ-программ.

Введем некоторые определения. Если не оговорено особо, будем счита: что используется система обозначений, принятая в языке Пролог. Прт лом является утверждение вида

Р :- <7ь<72,-,Чп,

где р и cji являются литералами. При этом р называется головой прави. а конъюнкция литералов 7, - телом правила. Правило с пустым телом , содержащее переменных, называется фактом. Дедуктивная база данных i стоит из множества фактов (базовых или экстенсиональных предикатов множества правил (определяющих производные или интенсиональные п\ дикатпы). Первое множество называют экстенсиональной базой дани (ЭБД), второе - интпссиональной базой данных (ИБД). Факт F являет выводимым из ДБД, если существует правило, голопа которого сопоста] ма с F, а тело содержит либо базовые предикаты либо предикаты, вьи димые из данной ДБД. Запросом к ДБД называется некоторый части' конкретизированный литерал, ответом на запрос являются все его основн экземпляры (факты), выводимые из данной ДБД. Запрос является безоп ным, если ответ на него конечен. Следует отметить, что под запросом (и дедуктивным запросом) мы часто будем понимать логическую програь (список правил), при этом из контекста всегда будет ясно, о чем идет ре

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

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

Было показано, что восходящие стратегии предпочтительнее в прило-ениях Саз данных. Однако в случае, когда запрос содержит означенные временные, они оказываются весьма неэффективными: множество запра-[иваемых в ДБД фактов часто много больше множества фактов, реле-штных запросу. Дополнительные трудности связаны с обработкой ре-^'рсивных запросов, где нельзя ограничиться простой подстановкой кон-гант вместо переменных исходного определения. Нисходящие стратегии , эторые в процессе выполнения учитывают информацию об означиваниях еременных запроса (подцели), такого недостатка лишены. Это наблю-ение положено в основу целого ряда смешанных стратегий, оптимизпру-|щих восходящее вычисление логических программ. Суть их состоит в тсдующем: при помощи определения дополнительных предикатов и после-ующего переписывания исходной программы моделируются информацион-ые потоки нисходящих стратегий. Восходящее вычисление переписанных равил вместо исходных позволяет существенно уменьшить множество из-лекаемых из ДБД фактов. Дополнительные предикаты называются маги-ескими, а генерируемые ими кортежи образуют магические множества. Стратегии магических множеств сочетают достоинства нисходящих и вос-одящих стратегий. Рассмотрению стратегии магических множеств для .'ИПТЕЗ-программ посвящена третья глава настоящей работы.

В русле концепции ДБД работа велась по целому ряду исследоватсль-ких проектов. Результаты их сравнительного обзора в сжатом виде приедены в табл. 1 и 2, где представлены характеристики рассмотренных роектов и языков с точки зрения поддержки объекто-орнентированной мо-ели данных и расширенных языковых средств. Использовались следую-дие обозначения: "+" - указанное средство поддерживается системой, + -" - частично поддерживается, "-" - не поддерживается.

Во второй главе приводится описание языка запросов системы СИНТЕЗ и определяется его семантика.

Рассмотрим упрощенную модель информационных ресурсов.

В схеме информационных ресурсов различаются следующие множества

Табл. 1:. Поддержка концепций объектно-ориентированной модели да] ных в обозреваемых языках и проектах

Сложные Уникальная Типи- Насле- Инкапсу-

объекты идентификация зация дование ляция

объектов

LDL + - - - -

NAIL! + - - - - -

ALGRES + - - + - - -

POSTGRES + - + - - -

PRISMA + - - + - - -

COL + - + - - -

IQL + + + - + +

LOGRES + + + - + +

СИНТЕЗ + + + + +

Табл. 2:. Поддержка расширенных языковых средств

Отрицание Встроенные предикаты Средства обновления данных Группирование Агрегатные функции I'

LDL + + + + - + -

NAIL! + - - + - -

ALGRES + - + + + - + -

POSTGRES + + + + - + -

PRISMA + + + - + +

COL + - - - -

IQL + - + - -

LOGRES + - + - -

СИНТЕЗ + + + + +

попарно различных имен: 1) имена типов {¿1, ¿2, ■••}, 2) имена классов {с1, сг, ...}, 3) имена атрибутов {а^ аг,...}, 4) имена переменных {г/1, г>2> -"К 5) имена методов {тп\,тп2, ■■■}■

В базе информационных ресурсов могут размещаться и обрабатываться константы различных типов {^Д'г,...} и уникальные идентификаторы объектов {о], 02,...}. В состав базовых типов языка СИНТЕЗ включены : тип целый, логический, вещественный, символьный, типы битовой и символьной строки, тип перечисления, тип последовательности, тип отрезка, АТД, тип массива, тип функции. Далее Б обозначает множество имен произвольного базового типа, С - множество имен классов.

Набор представляющих интерес в данном контексте конструкторов типа языка СИНТЕЗ определяется следующим образом:

1. Ь 6 В и с 6 С являются типами;

2. тип кортежа (записи) определяется типовым выражением вида; : ¿1,..., Ап : <„], где ЛЬ...,Л„,

(п > 0) - имена атрибутов, и - типы или типовые выражения;

3. если £ есть тип, то {¿} - тип множества;

4. если <1 и ¿2 - типы, то (¿1^2) - типовое выражение, определяющее тип, являющийся размеченным объединением типов.

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

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

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

та и переменная в формулах - типизированы. Предикаты в формулах соответствуют классам, методам и функциям, введенным в модулях определения информационных ресурсов.

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

Атом (предикат) имеет вид ...,<„), где р - предикатный символ , а и - термы.

Формула либо является атомом, либо имеет вид: & и)2 {ш 1 и шг) Ю1 | и>2 (^1 или шг) ;

"и»2 (не шг)

а11 х\1 (ш1 — > шг) (для всех х типа < если то и^) ех х/< (и>) (для некоторых х типа I выполняется ги), где ш,1и1,г1/2 - формулы, х - набор переменных, 4 - набор типов.

Переменные связываются в формулах кванторами. Нотация х/< определяет, что тип переменной х есть I.

Правила представляют из себя замкнутые формулы вида а£ : —ги, где а< есть атом, а ш - формула, а< называется головой, а ги - телом правила. Если формула используется в качестве запроса к базе информационных ресурсов (такой запрос называется фильтром) и имеет свободные переменные х1,...,£п, то ответом на запрос является множество подстановок правильно типизированных значений Х1,...,Х„, на каждой из которых фильтр при интерпретации на базе информационных ресурсов становится истинным. Совокупность правил языка СИНТЕЗ образует программу.

Каждому имени класса с п атрибутами или каждому множеству 5, определенному на типе п-атрибутной записи (или на классе), может быть поставлено в соответствие в формулах 2" — 1 различных предикатных символов (атомов), определенных на различных сочетаниях атрибутов из п. В формулах такие предикаты обозначаются именем класса (множества), за которым следуют термы соответствующих типов (имена атрибутов, имена переменных, отождествленных с именами атрибутов, или атомы, имена предикатов которых однозначно соответствуют определенному атрибуту класса или отношения).

Если имя предиката является именем функции или метода, то ему со-

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

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

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

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

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

Универсум языка запросов системы СИНТЕЗ SU есть множество, элементами которого являются: константы, идентификаторы объектов, имена предикатов. Если U\,U2,..., ип являются элементами SU, а р - имя предиката, то элементами SU могут быть: [ai : 111,0,2 : U2,--,an : , {uj, U2,..., un} или р(щ , ii2,..., ип) . Далее, стандартным образом определяются понятия базиса SB и интерпретации языка СИНТЕЗ, логические значения фактов, формул и правил, типизированное означивание, обобщающее понятие унификации при наличии типов и вычислимых функций. Факт G является следствием «з программы Р (обозначается Р (= G) тогда и только тогда, когда каждая интерпретация, удовлетворяющая Р, удовлетворяет также G.

Пусть ESB - элементы SB, имена предикатов которых принадлежат множеств}' имен экстенсиональных предикатов, ISB - элементы SB, имена предикатов которых принадлежат множеству имен интенсиональных предикатов.

На вход СИНТЕЗ-программы Р поступает некоторое конечное множество ЕИВ < ЕБВ. На выходе получаем множество соп.чЕОВ(Р), содержащее интенсиональные факты, являющиеся следствием из Р П ЕБВ: сопзЕОВ{Р) = < в! £ 1БВ Л (Р и ЕБВ) С} Рассмотрим следующее множество: Ь = {У\V <БВ}.

СИНТЕЗ-программа Р определяет на Ь оператор непосредственного следования Тр, который каждому V < БВ ставит в соответствие множество Тр(У), содержащее непосредственные следствия из Р и V ^вычисляемые следующим образом: для каждого правила Я : — /(Ь\, ...,Ьп) из Р, и для каждого правильно типизированного означивания в1т, если /(в'тЬ],..., 01тЬп) истинна на V, то факт в1тЬо доказан.

В общем случае для нехорновских баз данных оператор Тр является немонотонным. Конструкции дедуктивного языка запросов, способные повли ять на монотонность оператора непосредственного следования будем пазы вать критичными. Использован единообразный подход к анализу конструк ций языка СИНТЕЗ на предмет критичности, основанный на рассмотренш монотонности соответствующего конструкции отображения аргументов ] переменные.

Обоснуем основную процедуру вычисления СИНТЕЗ-программ - итера цию наименьшей неподвижной точки или 1Гр-итерацию. Пусть Т'р(У) = Тр(у) и V. Имеет место следующая теорема:

Теорема 1 Пусть Р • СИНТЕЗ-программа, не содержащая критичны конструкций.

Тогда сошу(Р) = 1/р{Т'р(У)) \ V.

В общем случае, когда СИНТЕЗ-программы содержат критичные кон струкции, теорема 1 не имеет места и итерация неподвижной точки може приводить к получению некорректных результатов.

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

Стратификация СИНТЕЗ-программы Р состоит в разбиении множества имен предикатов программы Р ) на подмножества (страты) Р\, ...,Рп-Порядок выполнения предикатов соответствует порядку страт, который задается их индексами. Критерием такого разбиения является следующее требование: до вычисления предиката в голове правила должны быть полностью вычислены все предикаты, которые необходимы для вычисления подформул тела правила, входящих в критичные конструкции.

В работе дано более строгое определение стратификации, основанное на понятии графа зависимостей СИНТЕЗ-программы и сформулирован формальный критерий для распознавания допустимых программ.

Допустимая СИНТЕЗ-программа Г со стратификацией Р\,..., Рп вычисляется по стратам:

ЬРР(Т'р(У)) = 1/р(Т'г„(

■ 1/р(Т'ги~ -Шт'гЛ 1/р(Т'гЖ~)-

Далее определяется нисходящая схема вычисления СИНТЕЗ-программ. Для этого расширяется определение восходящего метаинтерпретатора программ Дейталога по Ф. Бри и специфицируется обратная процедура вычисления неподвижной точки (ВГР-процедура), которая осуществляет нисходящую обработку правил базы данных при помощи восходящей обработки правил метаинтерпретатора.

Рассматривается вопрос допустимости метаинтерпретатора. Метаинтерпретатор является нсстратифипирусмон и, следовательно, недопустимой СИНТЕЗ-программой. Однако, в случае допустимости объектной СИНТЕЗ-программы, метаинтерпретатор является локально стпртифицирусмым. При локальной стратификации производится разбиение базиса Б В СИНТЕЗ-программы на конечное число страт Б В],..., 8Вп, на основании которого задается порядок выполнения экземпляров предикатов программы. Для локально-стратифицируемых программ удается обеспечить монотонность оператора непосредственного следования. Таким образом, определение метаинтерпретатора СИНТЕЗ-программ корректно.

В третьей гларе на базе нисходящей схемы для СИНТЕЗ-программ определяется стратегия магических множеств, сочетающая достоинства вое-

ходящего и нисходящего вычисления.

При стратегии магических множеств для СИНТЕЗ-программ за счет восходящего моделирования информационных потоков нисходящей стратегии, организуется эффективное вычисление наименьшей неподвижной точки программы.

При нисходящей схеме вычисления программ языка СИНТЕЗ имеют место два основных режима предачи информации: унификация (при которой целевой предикат сопоставляется с головным предикатом правила, означивая некоторые переменные головы) и режим горизонтального распространения информации (ГРИ) . Суть последнего в следующем. Вычисляя предикат с некоторыми конкретизированными переменными, мы находим значения для остальных его переменных. Новые конкретизации могут быть переданы другим предикатам данного правила, что накладывает на эти предикаты дополнительные ограничения. ГРИ таким образом отражает то , как связывания для переменных головы правила, произведенные в результате унификации ее с запросом, используются при вычислении предикатов и формул в теле правила.

На рис. 1 приведен фрагмент дерева Правило/Цель (ПЦ-дерева), традиционно используемого для представления нисходящего вычисления логических программ для случая правил с конъюнктивным телом. Предполагается, что аргументы ii,..., i* подцели G; являются связанными (аргумент связан, если все входящие в него переменные означены константами), /Ins-re! - полное результирующее отношение для G,-, ana-ml - часть отношения Ans-rel, произведенная правилом г2. Отношение тад.р содержит иформа-цию о связываниях переменных для Gi, supri,j - дополняющие отношения (supplementary relations) содержащие информацию о ГРИ.

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

Рассмотрим правило, общий вид которого приведен ниже:

Гз : Po(Vb)_ : - f(lh(Vi),...,Pi(V),...,pn(Vn)), где VoЛ'ь • • ч V,i - векторы аргументов предикатов Pq,]>i, ■■.,]>п, f- некоторая формула языка СИНТЕЗ, pi - интенсиональный предикат. Предположим,

т\ : Н\ : - С],

Апя-гс1

•<"фг1..-1(А'ь...,Л*/) & С,

ап,н-гс1

г2 : ..,.■»„) : -

Рис. 1: Фрагмент ПЦ-дерева для случая правил с конъюнктивным телом

что сформулирован запрос ? — рп(В, Г), сопоставимый с головой правила г3. Здесь В - вектор связанных аргументов, Р - вектор свободных аргументов. При вызове правило г.ч квалифицируется константами В, полученными из запроса. Первое магическое правило (факт) будет иметь вид: тпа<)1с_рй(В).

На его основании определим нулевое дополняющее правило:

•,"Рг1.о(Уь-Л/() : — та(]1с-р$(В), где V],..., У/ - переменные, которые входят в аргументы вектора В.

При вычислении правила Гд определенные переменные вхождения предиката р, означиваются константами, полученными в результате вычисления некоторой формулы, содержащей определенные подформулы тела правила Такую формулу будем называть существенной. В общем виде (г — 1)-е дополняющее правило запишется следующим образом:

■?иРг3.¿-1 (А") : -яирГз.о(Л'1) & г/л, где т$- существенная формула для р,-, А' - вектор переменных, означиваемых в результате вычисления тела данного правила, которые входят либо в последующие предикаты тела, либо в головной предикат.

Далее вводится понятие контекста вхождения предиката в тело правила, который определяет местонахождение предиката в дереве грамматического

разбора (ДГР) тела. На основании анализа контекстов вхождений предикатов в тела правил определен алгоритм построения существенной формулы.

На вход алгоритма переписывания по методу магических множеств поступает СИНТЕЗ-программа, состоящая из правил вида

тГ. Н :-/(С1,..,Сп), где /(£?ь •••> Сп) - некоторая формула языка СИНТЕЗ, определенная на предикатах

При переписывании СИНТЕЗ-программ правила для магических и нулевых дополняющих предикатов определяются стандартным образом. При определении последующих дополняющих предикатов используются существенные формулы для предикатов тел правил исходной программы:

~ & г/-С,.

Здесь г/Л?; - существенная формула для С;, Л' - вектор переменных, означиваемых в результате вычисления тела данного дополняющего правила, которые входят либо в последующие предикаты тела исходного правила, либо в головной предикат исходного правила.

После определения магических и дополняющих предикатов каждое правило исходной программы заменяется на переписанное правило г'-: т'Г. Н : - зирп.0(У) к 1(Си...Сп).

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

Рассмотренному выше алгоритму переписывания СИНТЕЗ-программ по методу магических множеств присуща определенная избыточность вычислений. В работе рассмотрен более эффективный улучшенный метод магических множеств. Для обоих методов сформулированы теоремы корректности и дана схема их доказательств.

Пусть IV - множество фактов, произведенных СИНТЕЗ-программой, II и N11 - соответственно множества фактов, релевантных и нерелевантных запросу. На рис. 2а) и Ь) приведены зависимости IV от N11 соответственно для простого восходящего вычисления и для стратегии магических множеств. Во втором случае IV не зависит от N11, более того, эффект магических множеств, т. е. совокупность нерелевантных фактов, исключае-

х из рассмотрения и /2), возрастает с увеличением ТУТ? (рис. 2с). эбщсм случае множество фактов, элиминируемых стратегией магиче-[X множеств, равно объединению множеств нерелевантных фактов для к до го из атомарных запросов, вычисляемых при выполнении СИНТЕЗ-■>граммы. В реальных приложениях оно может быть очень большим, при >м жизнеспособность дедуктивной базы даных зависит от оптимизации гичсских множеств.

С) И'

ь).

И'

л

я

/

г-,

МП. ЛТД

1с. 2: Эффект стратегии магических множеств

Четвертая глава посвящена разработке претранслятора логических ШТЕЗ-программ.

Претранслятор логических СИЫТЕЗ-программ (ПЛСП) входит в состав мпилятора языка СИНТЕЗ и предназначен для контроля корректности и тимизации выполнения логических программ. Наличие ПЛСП как со-авной части компилятора обусловлено прежде всего необходимостью вы-[сления рекурсивных запросов к базе информационных ресурсов.

Функциями ПЛСП являются :

1. Проверка безопасности СИНТЕЗ-программ.

2. Проверка допустимости СИНТЕЗ-программ.

3. Переписывание СИНТЕЗ-программ с целью оптимизации вычисления шменьшей неподвижной точки.

4. Определение порядка вычисления предикатов допустимых СИНТЕЗ-эограмм (расслоение программ), обеспечивающего монотонность итера-

наименьшей неподвижной точки.

5. Определение правил для дифференциалов интенсиональных предика-)в при полунепосредственном вычислении наименьшей неподвижной точ-л.

Функционально ПЛСП находится между блоком синтаксического и с< мантического анализа, и транслятором логических программ в операци исполнительного механизма (расширенную алгебру объектов).

Структурная схема ПЛСП определяется набором реализуемых им фуш ций. При этом функционально первым блоком является блок tables, коте рый формирует информационные таблицы, используемые на последующи этапах претрансляции. Для контроля функционирования претранслятор в него включен также вспомогательный блок convert, выполняющий пр< образование программы из внутреннего представления в исходное.

Каждый из блоков ПЛСП реализован в виде независимого модуля может использоваться отдельно. Функциональная последовательность ис пользования блоков претранслятора зависит от вида исходной программь На вход ПЛСП поступает СИНТЕЗ-программа во внутреннем предел влении, сформированном блоком синтаксического и семантического аналЕ за, возможно включающая запросы - формулы,языка СИНТЕЗ. В качеств внутреннего представления используются деревья грамматического разбе ра (ДГР) специального формата. Вид внутреннего представления и.форма ДГР определяется решениями теоретического и практического характер;: принятыми при построении претранслятора и компилятора.

Правилу языка СИНТЕЗ соответствует ДГР, общий вид которого в скс бочной нотации приведен ниже: rule(< метка правила >,

head(< ДГР головы правила >),

body(< ДГР формулы тела правила >)). Составной формуле исходного правила соответсвует поддерево следую щего формата:

/(< метка формулы >, < операция >, < операнд 1 >, < операнд 2 >). Если операция унарна, то < операнд 2 > = void. Атомарной формуле (пре дикату) соответсвует терминальная вершина ДГР формулы вида: < контекст вхождения > — pred(name(< имя предиката >),

args(< список ДГР аргументов предиката >)) На основании внутреннего представления СИНТЕЗ-программы строят ся вспомагательные информационные таблицы, используемые блоками пре транслятора.

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

На втором этапе использовался язык Си. Программирование велось в среде Borland С++, при этом наличие отлаженного прототипа позволило существенпо ускорить работу. Было принято решение трактовать внутреннее представление логических СИНТЕЗ-программ (ДГР) как абстрактный тип данных, для работы с которым определен операционный интерфейс. Это позволило избежать многих проблем, связанных с реализацией языка большого размера, и в полной мере обеспечить модульность результирующего программного обеспечения. При этом общий объем программного обеспечения составил около 6000 строк на языке Си и 2000 строк на языке Пролог.

III Основные результаты работы

1. Определена теоретико-модельная семантика языка запросов СИНТЕЗ и понятие оператора непосредственного следования для СИНТЕЗ -программ. Определен базовый метод выполнения логических СИНТЕЗ-программ, основанный на вычислении наименьшей неподвижной точки задаваемого программой оператора непосредственного следования.

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

низм вычисления допустимых СИНТЕЗ-программ.

3. Расширено определение восходящего метаинтерпретатора' Дсйталог-щни'рнММ И ЯП 01 и «ЯНОМ0 опрело лица цисходйщл" схим^ ШПОЛДОИИЯ СЭДЬ ТЁЗ-программ. Для обоснования корректности данного определения введено понятие локальной стратификации СИНТЕЗ -программ. Сформулирована и доказана теорема о локальной стратифицируемости расширенного метаинтерпретатора.

4. Разработана методика переписывания логических СИНТЕЗ-программ по принципу магических множеств. Введено понятие существенной формулы предиката, на основании которой определяются отношения, содержащие информацию о связываниях переменных. Определен алгоритм построения существенной формулы, основанный на анализе контекстов вхождений предикатов в тело правила. Предложен также более эффективный улучшенный метод магических множеств. Сформулированы теоремы корректности и дана схема их доказательств. Данный метод естественно применим и к правилам с конъюнктивными телами, что позволяет рассматривать его как обобщение традиционного метода магических множеств.

5. Разработан претранслятор логических СИНТЕЗ-программ, входящий в состав компилятора языка СИНТЕЗ, основными функциями которого являются анализ программ на допустимость, обеспечение корректного выполнения допустимых программ и переписывание программ по методу магических множеств. Разработано внутреннее представление логических СИНТЕЗ-программ - дерево грамматического разбора (ДГР) специального формата. Работа блоков претранслятора основана на специально разработанных алгоритмах анализа и трансформации ДГР. При этом само ДГР трактуется как абстрактный тип данных, для работы с которым определен операционный интерфейс.

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

1. Задорожный В.И. Методы вычисления и оптимизации рекурсивных запросов в дедуктивных базах данных (обзор). Препринт. V Всесоюзная конференция "Системы баз данных и знаний", Львов. 1991, 47 с.

2. Задорожный В.И. Трансформация дедуктивного языка запросов пер-го порядка по методу магических множеств. Тезисы Всесоюзного научно-хничсского семинара "Программное обеспечение новых информационных хнологий". Тверь 1991.

3. Задорожный В.И., Калиниченко Л.А. Язык запросов к базе обоб-:нных информационных ресурсов и метод его реализации. Системы и едства информатики. Под ред. И.А. Мизина. М. Наука. 1992, с. 46-70.

4. Задорожный В.И., Никитченко Н.С. Алгебраический подход к форма-зации дедуктивных языков запросов к базам данных. Программирование, инято к опубликованию.

5. Kalinichenko L., Zadorozhny V. A generalized information resource query iguage and basic query evaluation technique, Proc. of the Second Int. Conf.

DOOD, Munich, December 1991, LNCS, N. 5GG , p. 546-566.