Cтраница 3
Отметим, что до сих пор описание методики для выбора минимальных моделей Эрбрана было неформальным к неполным. Следовательно, нужно расширить нашу методику для работы с программами Дейталога 1, состоящими из нескольких правил. Однако, как будет показано, наша методика неприменима ко всем программам. Она работает для большого класса программ, называемых стратифицируемыми. [31]
Сначала мы рассмотрим синтаксис Дейталога и введем несколько полезных понятий из области логического программирования и автоматического доказательства теорем. Затем строго определим теоретике-модельную семантику языка и представим полную и обоснованную теорию доказательства для Дейталога, которая непосредственно приводит к процедуре восходящих вычислений программ Дейталога. Мы рассмотрим также теорию неподвижной точки Дейталога и покажем, как программы Дейталога могут вычисляться обратным выводом при помощи нисходящего метода. [32]
Метод статической фильтрации также является общим и применимым к любой программе Дейталога с целью, имеющей связанный аргумент. Методы статической фильтрации и магических множеств, примененные к программе вычисления предка, приведенной выше, дают одинаковый результат, как и программа, переписанная профессиональным программистом. Последний метод полунепосредственных вычислений переписыванием при оптимизации не анализирует структуру цели и может применяться к программам Дейталога без целей. [33]
Ниже рассматривается система ADE - результат совместных усилий Университета Калабрии и фирмы ENIDATA ( Италия. Система ADE поддерживает простое расширение чистого Дейталога, включающее отрицание и объекты. Объект образуется множеством кортежей, расположенных в нескольких отношениях и имеющих один и тот же уникальный идентификатор объекта. Программы Дейталога транслируются в Пролог с сохранением семантики неподвижной точки Дейталога. При этом обеспечивается безопасность реализации, позволяющая получать множество всех ответов. Для компиляции используется мини-магический метод, представляющий собой вариант метода магических множеств. Рассматривается также и метод магического подсчета. [34]
Все методы и алгоритмы, представленные в этой части, сформулированы независимо от структуры базы данных. Подразумевается, что все необходимые в процессе работы программы Дейталога данные доступны непосредственно. [35]
Ниже мы сначала рассмотрим аксиому замкнутости мира и покажем, что она может использоваться для вывода отрицательной информации из программ Дейталога. Первый подход, называемый стратифицируемым Дейталогом, является естественным расширением чистого Дейталога. Он основан на том предположении, что предикаты программы Дейталога следует вычислять в определенном порядке. Второй подход основан на концепции инфляционной семантики и с вычислительной точки зрения более мощный, чем первый. [36]
Ниже мы уточним высказанные выше суждения. Прежде всего нам необходимо формально определить, что подразумевается, когда мы говорим, что основные факты являются логическим следствием множества основных дизъюнктов и правил Дейталога. Для этой цели мы сначала введем понятия интерпретации Эрбрана и модели Эрбрана. Мы покажем, что концепция минимальной модели Эрбрана тесно связана с семантикой программ Дейталога. [37]
Провести строгое сравнение обсуждаемых здесь методов оптимизации достаточно трудно, потому что оценки зависят от многих факторов и сами методы сильно отличаются друг от друга. Ниже мы обсудим только два аспекта проблемы. Сначала мы рассмотрим методы с качественной стороны, чтобы выделить основные принципы оптимизации, присущие всем методам. Затем мы представим оценки производительности, которые были проведены на некоторых специфических классах программ Дейталога. [38]