Cтраница 2
Тем не менее, как показано в следующем примере, с помощью встроенных предикатов достаточно легко писать небезопасные программы Дейталога. [16]
Ниже мы сначала рассмотрим аксиому замкнутости мира и покажем, что она может использоваться для вывода отрицательной информации из программ Дейталога. [17]
Безопасность общих запросов на Дейталоге рассматривается в [ Вап86Ь ], где программы, удовлетворяющие нашим достаточным условиям безопасности программ Дейталога ( разд. [18]
В книге рассмотрены синтаксис и логическая семантика Дейталога, эрбрановская теоретико-модельная интерпретация Дейталога, ориентированная на Дейталог теория логического вывода, подход к вычислению неподвижной точки программы Дейталога, идея трансляции программ на Дейталоге в систему уравнений на языке реляционной алгебры, вопросы полноты программ на Дейталоге. Важное место занимают методы оптимизации, предназначенные для достижения высокой эффективности запросов на Дейталоге. Рассмотрены различные расширения Дейталога, определяются дальнейшие усовершенствования, необходимые для применения Дейталога в реальных задачах. [19]
Хотя мы не вводили строгой формализации общих моделей, наше определение модели Эрбрана математически правильно. Эта концепция позволяет строго определить семантику программ Дейталога. [20]
Ниже мы коротко опишем, каким образом стратифицированную программу Дейталога 1 можно эквивалентно охарактеризовать, используя чисто декларативную семантику. [21]
Единственным существенным отличием является то, что результат программы Дейталога может содержать факты для нескольких интенсиональных предикатов, в то время как результат запроса обычно состоит из одного-единственного отношения. Тем не менее, если в дополнение к программе Дейталога мы задаем цель, результат состоит из основных фактов только для одного предиката. [22]
Пользуясь теорией моделей, мы можем точно охарактеризовать, что вычисляет прграмма Дейталога. Однако мы не объясняем, каким образом может быть вычислен результат программы Дейталога ( см. гл. [23]
Целевым утверждением ( целью) Дейталога является простой целевой дизъюнкт. Заметим, что мы не требуем, чтобы целевой предикат появлялся внутри программы Дейталога. Однако в более интересных случаях целевой предикат появляется в голове одного из дизъюнктов. [24]
В частности, рассмотрим использование встроенных предикатов, отрицания и сложных объектов в программах Дейталога. [25]
Формально встроенные предикаты можно рассматривать как предикаты EDB, отличающиеся от обычных предикатов EDB другой физической реализацией: они не хранятся явно в EDB, а реализованы в виде процедур, которые вычисляются во время выполнения программы. Однако встроенным предикатам в большинстве случаев соответствуют бесконечные отношения, что может повлиять на небезопасность программ Дейталога. [26]
Существуют и другие подходы к оптимизации, которые, хотя и не исследованы в достаточной степени, являются тем не менее многообещающими. В [ Sagi87 ] предложен алгоритм минимизации размера ( в терминах числа правил в программе и числа атомов в правиле) программы Дейталога при разрешимом условии общей эквивалентности. Другой тип оптимизации получен Рамакришнаном и др. [ Rama88 ], где объектом оптимизации является продвижение проекций ( а не операций выбора) в теле правила Дейталога. Это означает, что в литералах тела правила удаляются некоторые позиции аргументов, что иногда приводит к избыточности вычисления некоторых правил. [27]
Сначала мы рассмотрим синтаксис Дейталога и введем несколько полезных понятий из области логического программирования и автоматического доказательства теорем. Затем строго определим теоретике-модельную семантику языка и представим полную и обоснованную теорию доказательства для Дейталога, которая непосредственно приводит к процедуре восходящих вычислений программ Дейталога. Мы рассмотрим также теорию неподвижной точки Дейталога и покажем, как программы Дейталога могут вычисляться обратным выводом при помощи нисходящего метода. [28]
Язык логического программирования для манипулирования данными ( такой, как LDL) следует разрабатывать в соответствии с подходящей моделью данных, которая формализует принципы хранения и поиска и манипу-ляционные примитивы, поддерживаемые СУБД для используемых в языке объектов. Чистый Дейталог, например, может основываться на реляционной модели в первой нормальной форме ( которую в последнее время часто называют плоской реляционной моделью), поскольку концепция литерала прекрасно сопоставима с концепцией кортежа в отношениях данных, а единичные шаги вычисления программы Дейталога можно транслировать в соответствующую последовательность реляционных операций ( гл. С другой стороны, языки логического программирования ( такие, как LDL) имеют дело со структурированными объектами, которые требуют более сложных моделей данных. [29]
Каждый предикат IDB соответствует отношению-переменной. Каждый предикат EDB программы Дейталога соответствует отношению-константе. Нахождение решения этой системы соответствует определению значений отношений-переменных, которые удовлетворяют данной системе уравнений. [30]