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

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

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

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

УДК 681.3.016

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

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

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

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

Москва - 1992

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

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

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

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

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

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

вычислительный центр Московского Государственного Университета (НИВЦ МГУ)

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

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

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

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

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

I Общая характеристика работы

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

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

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

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

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

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

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

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

СИНТЕЗ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Добавление указанных особенностей требует дополнительных исследс ваний по определению строгой семантики запросов, сохранению эффектш ности и безопасности вычислений. В настоящее время эти вопросы изучен недостаточно. В частности было показано, что реляционная алгебра, ра< ширенная оператором наименьшей неподвижной точки (¿.ГР-оператором эквивалентна логике хорновских дизъюнктов без функциональных симв< лов. Однако возникает целый ряд проблем при вычислении опора тоу

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

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

Р ■ ~ ?ь<72,-,<7™,

где р и qi являются литералами. При этом р называется головой правил а конъюнкция литералов - телом правила. Правило с пустым телом , I содержащее переменных, называется фактом. Дедуктивная база данных о стоит из множества фактов (базовых или экстенсиональных предикатов) множества правил (определяющих производные или интенсиональные пр дикатпы). Первое множество называют экстенсиональной базой дата. (ЭБД), второе - ингпесиональной базой данных (ИБД). Факт Р являет* выводимым из ДБД, если существует правило, голова которого сопостав: ма с Р, а тело содержит либо базовые предикаты либо предикаты, выв димые из данной ДБД. Запросом к ДБД называется некоторый частич] конкретизированный литерал, ответом на запрос являются все его основш экземпляры (факты), выводимые из данной ДБД. Запрос является безопа ным, если ответ на него конечен. Следует отмстить, что под запросом (и: дед])ктивным запросом) мы часто будем понимать логическую программ (список правил), при этом из контекста всегда будет ясно, о чем идет рсч

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

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

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

В русле концепции ДБД работа велась по целому ряду исследователь-ких проектов. Результаты их сравнительного обзора в сжатом виде пх>и-|едены в табл. 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) имена классов {сх, со ...}, 3) имена атрибутов {«1, а2,...}, 4) имена переменных {г>1, г>2, ...}, 5) имена МеТОДОВ {7711,7712,...}.

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

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

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

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

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

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

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

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

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

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

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

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

Атом (предикат) имеет вид p(t\,..., tn), где р - предикатный символ , а i, - термы.

Формула либо является атомом, либо имеет вид: W\ & XU2 (wi и W2) W\ | W2 (w 1 ИЛИ VJ2)

~W2 (не W2)

ail x/t (toi — > W2) (для всех x типа t если w\ то w-î) ex x/t (w) (для некоторых x типа t выполняется w), где w,w\,w2 - формулы, x - набор переменных, t - набор типов.

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

Правила представляют из себя замкнутые формулы вида at : — w, где at есть атом, а w - формула, at называется головой, а w - телом правила. Если формула используется в качестве запроса к базе информационных ресурсов (такой запрос называется фильтром) и имеет свободные переменные xi,...,x,n, то ответом на запрос является множество подстановок правильно типизированных значений rej,..., хп, па каждой из которых фильтр при интерпретации на базе информационных ресурсов становится истинным. Совокупность правил языка СИНТЕЗ образует программу.

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

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

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

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

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

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

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

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

Универсум языка запросов системы СИНТЕЗ есть множество, эле-[ентами которого являются: константы, идентификаторы объектов, имена редикатов. Если Нь и^...., ип являются элементами 57/, а р - имя предика-а, то элементами Би могут быть: [с^ : «1,02 '• Щ,-—,ап '■ «п], {и\,и2-> •—,ип} ли р(щ,и?, ...,«„) . Далее, стандартным образом определяются понятия азиса БВ и интерпретации языка СИНТЕЗ, логические значения фактов, ормул и правил, типизированное означивание, обобщающее понятие уни-икации при наличии типов и вычислимых функций. Факт С является тедствием из программы Г (обозначается Р (= (?) тогда и только тогда, )гда каждая интерпретация, удовлетворяющая Р, удовлетворяет также

Пусть ЕБВ - элементы 5Р, имена предикатов которых принадлежат ножеству имен экстенсиональных предикатов, 1БВ - элементы БВ, имена юдикатоп которых принадлежат множеств)' имен интенсиональных прокатов.

На вход СИНТЕЗ-программы Р поступает некоторое конечное мно> ство ЕБВ < ЕБВ. На выходе получаем множество сопьЕОВ(Р), содер} щее интенсиональные факты, являющиеся следствием из Р П ЕПВ-.

сопзЕОВ{Р) = < <?1 Е 1БВ Л (Р и ЕБВ) |= С?}

Рассмотрим следующее множество: Ь = {У\У < БВ).

СИНТЕЗ-программа Р определяет на Ь оператор непосредственного с дования Тр, который каждому V < 5В ставит в соответствие множес Гр(V), содержащее непосредственные следствия из Р и V , вычисляем следующим образом: для каждого правила Н : — /(1ц,..., Ьп) из Р, и , каждого правильно типизированного означивания в'т, если ${61ТЬ\,..., 0'т истинна на V, то факт 9'тЬа доказан.

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

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

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

Тогда сопзу{Р) - //р(Г'р(К)) \ V.

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

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

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

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

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

¿ГР(Гр(^))=//р(Т'Р„(

ттР1)))...).

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

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

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

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

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

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

На рис. 1 приведен фрагмент дерева Правило/Цель (ПЦ-дерева), традиционно используемого для представления нисходящего вычисления логических программ для случая правил с конъюнктивным телом. Предполагается, что аргументы ii,ijt подцели G; являются связанными (аргумент связан, если все входящие в него переменные означены константами), Ans-rel - полное результирующее отношение для G,-, ans-rel - часть отношения Ans-rel, произведенная правилом Отношение magjp содержит иформа-цию о связываниях переменных для G¿, supTi.j - дополняющие отношения (supplementary relations) содержащие информацию о ГРИ.

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

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

ГЗ : Ро(Уо)_ : - /(pi(Vi), где Vd^b •••>Vn - векторы аргументов предикатов po,pi,-~,p,„ f - некоторая формула языка СИНТЕЗ, />,■ - интенсиональный предикат. Предположим,

™Рг,л(ии...,ие) : -

яыРг,.«-1(Л'1, ..., Л'/) &

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

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

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

зирГз.о{Уи~; Ц) : — тад1с^ро(В), где VI,...- переменные, которые входят в аргументы вектора В.

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

яирГз.,-_1(Л') : -«гфГз.о(А"1) к г/.р{, где г/_р, - существенная формула для /),-, Л' - вектор переменных, означиваемых в результате вычисления тела данного правила, которые входят либо в последующие предикаты тела, либо в головной предикат.

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

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

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

тГ. Н :- /(С1 ,..,Оп), где /((?!,..., С„) - некоторая формула языка СИНТЕЗ, определенная на предикатах й 1,...)СП.

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

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

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

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

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

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

ых из рассмотрения (Fi и F2), возрастает с увеличением NR (рис. 2с).

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

W

R

с) W

R

NR NR NIi' NR* NR

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Kalinichenko L., Zadorozhny V. A generalized information resource query language and basic query evaluation technique, Proc. of the Second Int. Conf. on DOOD, Munich, December 1991, LNCS, N. 5G6 , p. 546-566.