Лог данных - Datalog

Лог данных это декларативный логическое программирование язык, который синтаксически является подмножеством Пролог. Часто используется как язык запросов за дедуктивные базы данных. В последние годы Datalog нашел новое применение в интеграция данных, извлечение информации, сеть, программный анализ, безопасность, облачные вычисления и машинное обучение.[1][2]

Его происхождение восходит к началу логическое программирование, но она стала отдельной областью примерно в 1977 году, когда Эрве Галлер и Джек Минкер организовал семинар по логика и базы данных.[3] Дэвид Майер приписывают создание термина Datalog.[4]

Возможности, ограничения и расширения

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

В отличие от Prolog, Datalog

  1. не допускает сложных терминов в качестве аргументов предикаты, например, p (1, 2) допустим, но не p (f (1), 2),
  2. навязывает определенные стратификация ограничения на использование отрицания и рекурсия,
  3. требует, чтобы каждая переменная, которая появляется в заголовке пункт также появляется в неарифметическом положительном (т. е. не отрицании) буквальный в тексте статьи,
  4. требует, чтобы каждая переменная, появляющаяся в отрицательном литерале в теле предложения, также появлялась в некотором положительном литерале в теле предложения[5]

Оценка запросов с помощью Datalog основана на логика первого порядка, и, таким образом, звук и полный. Однако Datalog не Тьюринг завершен, и поэтому используется как предметно-ориентированный язык которые могут использовать преимущества эффективных алгоритмов, разработанных для разрешения запросов. Действительно, были предложены различные методы для эффективного выполнения запросов, например, алгоритм Magic Sets,[6] табличное логическое программирование[7] или разрешение SLG.[8]

Некоторые широко используемые системы баз данных включают идеи и алгоритмы, разработанные для Datalog. Например, SQL: 1999 стандарт включает рекурсивные запросы, а алгоритм Magic Sets (первоначально разработанный для более быстрой оценки запросов Datalog) реализован в IBM DB2.[9] Более того, двигатели Datalog отстают от специализированных системы баз данных например, база данных Intellidimension для семантическая сеть.[нужна цитата ]

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

Фрагменты

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

Некоторые синтаксические фрагменты Datalog были определены, например, следующие (от наиболее ограниченных до наименее ограниченных):

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

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

Выразительность

В проблема ограниченности для Datalog спрашивает при наличии программы Datalog, ограниченный, т.е. максимальная глубина рекурсии, достигаемая при оценке программы во входной базе данных, может быть ограничена некоторой константой. Другими словами, этот вопрос спрашивает, можно ли переписать программу Datalog как нерекурсивную программу Datalog. Решение проблемы ограниченности произвольных программ Datalog неразрешимый,[10] но его можно решить, ограничившись некоторыми фрагментами Datalog.

Пример

Эти две строки определяют два факты, то есть вещи, которые всегда актуальны:

родитель(xerces, ручей).родитель(ручей, дамокл).

Вот что они означают: xerces - родитель Брук и Брук является родительницей дамокла. Имена пишутся в нижнем регистре, потому что строки, начинающиеся с заглавной буквы, обозначают переменные.

Эти две строки определяют правила, которые определяют, как новые факты могут быть выведены из известных фактов.

предок(Икс, Y) :- родитель(Икс, Y).предок(Икс, Y) :- родитель(Икс, Z), предок(Z, Y).

смысл:

  • X является предком Y, если X является предком Y.
  • X является предком Y, если X является предком некоторого Z, а Z является предком Y.

Эта строка представляет собой запрос:

?- предок(xerces, Икс).

Он спрашивает следующее: Кто все X, предком которых является xerces? Он вернется ручей и дамокл при противопоставлении системе Datalog, содержащей факты и правила, описанные выше.

Подробнее о правилах: у правила есть :- символ посередине: часть слева от этого символа - это голова правила правая часть - это тело. Правило звучит так: считается истинным, если известно, что истинно. Заглавные буквы в правилах обозначают переменные: в примере мы не знаем, кто Икс или же Y есть, но некоторые Икс является предком некоторых Y если это Икс является родителем этого Y. Порядок предложений не имеет значения в Datalog, в отличие от Prolog, который зависит от порядка предложений для вычисления результата вызова запроса.

Datalog различает экстенсиональные предикатные символы (определяется фактами) и интенсиональные предикатные символы (определяется правилами).[11] В приведенном выше примере предок - интенсиональный предикатный символ, и родитель экстенсионально. Предикаты также могут быть определены фактами и правилами и, следовательно, не могут быть чисто экстенсиональными или интенсиональными, но любую программу Datalog можно переписать в эквивалентную программу без таких предикатных символов с повторяющимися ролями.

Синтаксис

Программа Datalog состоит из списка фактов и правил (Роговые оговорки ).[12] Если постоянный и Переменная два счетный наборы констант и переменных соответственно и связь это счетное множество предикатные символы, то следующая грамматика выражает структуру программы Datalog:

<программа> ::= <факт> <программа> | <правило> <программа> | ɛ<факт> ::=  <связь> "(" <постоянный список> ")." <правило> ::= <атом> ":-" <атом-список> "."<атом> ::= <связь> "(" <список терминов> ")"<атом-список> ::= <атом> | <атом> "," <атом-список><срок> ::= <постоянный> | <Переменная><список терминов> ::= <срок> | <срок> "," <список терминов><постоянный список> ::= <постоянный> | <постоянный> "," <постоянный список>

Атомы также называют литералы в литературе.

Семантика

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

Модельная теория

Факт или правило называется земля если все его подтермы являются константами. Основное правило р1 это наземный экземпляр другого правила р2 если р1 это результат замена констант для всех переменных в р2.

В База Herbrand (видеть Вселенная Herbrand ) программы Datalog - это набор всех основных атомов, которые могут быть созданы с помощью констант, указанных в программе. An интерпретация (также известный как экземпляр базы данных) является подмножеством базы Эрбранда. Основной атом верен в интерпретации я если это элемент я. Правило верно в интерпретации I if для каждого основного экземпляра этого правила, если все предложения в теле истинны в я, то глава правила верна и в я.

А модель программы Datalog п это интерпретация я из п который содержит все основные факты п, и соблюдает все правила п правда в я. Теоретико-модельная семантика утверждает, что смысл программы Datalog - это ее минимальная модель (эквивалентно пересечение всех ее моделей).[13]

Семантика фиксированных точек

Позволять я быть набором интерпретаций программы Datalog п (т.е. я = п(ЧАС) куда ЧАС база Herbrand п и п это powerset оператор. Определить карту из я к я следующим образом: Для каждого основного экземпляра каждого правила в п, если каждое предложение в теле находится во входной интерпретации, добавляем заголовок наземного экземпляра в выходную интерпретацию. Тогда неподвижной точкой этой карты является минимальная модель программы. Семантика фиксированной точки предлагает алгоритм для вычисления минимальной модели: начните с набора основных фактов в программе, затем несколько раз добавляйте последствия правил, пока не будет достигнута фиксированная точка.[14]

Оценка

Есть много разных способов оценки программы Datalog с разными характеристиками.

Стратегии оценки снизу вверх

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

Наивная оценка

Наивная оценка отражает семантика фиксированной точки для программ Datalog. Наивная оценка использует набор «известных фактов», который инициализируется фактами в программе. Он продолжается путем повторного перечисления всех основных экземпляров каждого правила в программе. Если каждый атом в теле основного экземпляра входит в набор известных фактов, то головной атом добавляется к набору известных фактов. Этот процесс повторяется до тех пор, пока не будет достигнута фиксированная точка, и больше нельзя будет вывести факты. Наивная оценка дает полную минимальную модель программы.[15]

Системы, реализующие Datalog

Вот краткий список систем, которые либо основаны на Datalog, либо предоставляют интерпретатор Datalog:

Бесплатное программное обеспечение / открытый исходный код

Написано вИмяПопробуйте онлайнВнешняя база данныхОписаниеЛицензия
CXSBСистема логического программирования и дедуктивной базы данных для Unix и MS Windows с таблицами, обеспечивающими завершение и эффективность, как в Datalog, включая инкрементную оценку[16]GNU LGPL
C ++Коралловый[17]Дедуктивная система баз данных, написанная на C ++, с полунаивной оценкой журнала данных. Разработан в 1988-1997 гг.индивидуальная лицензия, бесплатно для некоммерческого использования
DLV[18]Расширение Datalog, поддерживающее дизъюнктивные главные предложения.пользовательская лицензия, бесплатная для академического и некоммерческого образовательного использования, а также для использования некоммерческими организациями[19]
Inter4QL[20]интерпретатор командной строки с открытым исходным кодом для Datalog-подобного языка запросов 4QL, реализованного на C ++ для Windows, Mac OS X и Linux. Отрицание разрешено в заголовках и текстах правил, а также в рекурсии.GNU GPL v3
RDFox[21]RDF Triple Store с аргументацией Datalog. Реализует алгоритм FBF для инкрементальной оценки.индивидуальная лицензия, бесплатно для некоммерческого использования[22]
Суфле[23]компилятор Datalog-to-C ++ с открытым исходным кодом, конвертирующий Datalog в высокопроизводительный параллельный код C ++, специально разработанный для сложных запросов Datalog по большим наборам данных, например встречается в контексте статического анализа программUPL v1.0
ClojureКаскалогHadoopбиблиотека Clojure для запроса данных, хранящихся в кластерах HadoopApache
Clojure Datalogдополнительная библиотека, реализующая аспекты DatalogОбщественная лицензия Eclipse 1.0
CruxдаАпач КафкаБаза данных общего назначения с «разукрупненной» архитектурой, использующая потоковую передачу документов и транзакций, ориентированную на журнал, для достижения значительной архитектурной гибкости и элегантного горизонтального масштабирования. Подключаемые компоненты включают Kafka, RocksDB и LMDB. По умолчанию индексы являются битемпоральными для поддержки запросов журнала данных на определенный момент времени. Предоставляются API Java и HTTP.Лицензия MIT
Datascriptв памятиНеизменяемая база данных и механизм запросов к журналу данных, работающий в браузереОбщественная лицензия Eclipse 1.0
ДаталевинLMDBФорк Datascript, оптимизированный для долговечного хранилища LMDB.Общественная лицензия Eclipse 1.0
Datahikeфайл, в памятиФорк Datascript с надежной серверной частью, использующий автостоянка.Общественная лицензия Eclipse 1.0
ErlangЛог данныхБиблиотека предназначена для запроса и формализации связи n-мерных потоков с помощью журнала данных. Он реализует специальный механизм запросов с использованием упрощенной версии общего логическое программирование парадигма. Библиотека облегчает разработку приложений для интеграции данных, обмена информацией и семантических веб-приложений.Apache v2
HaskellДина[24]Dyna - это декларативный язык программирования для статистического программирования ИИ. Язык основан на Datalog, поддерживает прямую и обратную цепочки, а также инкрементную оценку.GNU AGPL v3
DDlog[25]DDlog - это инкрементный типизированный механизм журнала данных в памяти. Он хорошо подходит для написания программ, которые постепенно обновляют свой вывод в ответ на изменения ввода. Программист DDlog декларативно определяет желаемое отображение ввода-вывода, используя диалект Datalog. Затем компилятор DDlog синтезирует эффективную инкрементную реализацию. DDlog основан на дифференциальном потоке данных[26] библиотека.Лицензия MIT
ЯваAbcDatalog[27]AbcDatalog - это реализация с открытым исходным кодом языка логического программирования Datalog, написанного на Java. Он предоставляет готовые к использованию реализации общих алгоритмов оценки Datalog, а также некоторые экспериментальные многопоточные механизмы оценки. Он поддерживает языковые функции, выходящие за рамки основного Datalog, такие как явное (не) унификация терминов и стратифицированное отрицание. Кроме того, AbcDatalog спроектирован так, чтобы его можно было легко расширять с помощью новых оценочных механизмов и новых языковых функций.BSD
ИРИС[28]IRIS дополняет Datalog функциональными символами, встроенными предикатами, локально стратифицированными или не стратифицированными логическими программами (с использованием хорошо обоснованной семантики), небезопасными правилами и типами данных схемы XMLGNU LGPL v2.1
Йенафреймворк семантической паутины, который включает реализацию журнала данных как часть механизма правил общего назначения, который обеспечивает СОВА и RDFS поддерживать.[29]Apache v2
SociaLite[30]SociaLite - это вариант журнала данных для крупномасштабного анализа графов, разработанный в Стэнфорде.Apache v2
Грааль[31]Graal - это набор инструментов Java, предназначенный для запросов к базам знаний в рамках экзистенциальных правил, также известных как Datalog +/-.CeCILL v2.1
Flix[32]даФункциональный и логический язык программирования, вдохновленный Datalog, расширенный определяемыми пользователем решетками и монотонными функциями фильтрации / передачи.Apache v2
LuaЛог данных[33]да[34]легкая дедуктивная система баз данных.GNU LGPL
OCamlлог данных[35]Реализация журнала данных в памяти для OCaml с алгоритмами восходящего и нисходящего типов.BSD 2-пункт
ПрологDES[36]реализация с открытым исходным кодом, которая будет использоваться для обучения Datalog на курсахGNU LGPL
PythonpyDatalog11 диалектов SQLдобавляет логическое программирование в набор инструментов Python. Он может выполнять логические запросы к базам данных или объектам Python и использовать логические предложения для определения поведения классов Python.GNU LGPL
РакеткаДаталог для ракетки[37]GNU LGPL
Datafun[38]Обобщенный журнал данных по полурешеткам.GNU LGPL
Рубинцвести / бутонРубин DSL для программирования с использованием конструкций, ориентированных на данные, на основе Дедал расширение Datalog, которое добавляет логике временное измерение.BSD 3-пункт
РжавчинаКрепCrepe - это библиотека, которая позволяет вам писать программы декларативной логики на Rust с синтаксисом, подобным Datalog. Он предоставляет процедурный макрос, который генерирует эффективный, безопасный код и легко взаимодействует с программами Rust. Он также поддерживает такие расширения, как стратифицированное отрицание, полунаивное вычисление и вызов внешних функций в правилах Datalog.Лицензия MIT / Apache 2.0
DatafrogDatafrog - это легкий движок Datalog, предназначенный для встраивания в другие программы Rust.Лицензия MIT / Apache 2.0
Tcltclbdd[39]Реализация на основе диаграммы бинарных решений. Создан для поддержки разработки оптимизирующего компилятора для Tcl.BSD
Другой или неизвестный языкbddbddb[40]внедрение Datalog сделано в Стэндфордский Университет. Он в основном используется для запроса байт-кода Java, включая анализ точек на большие программы Java.GNU LGPL
ConceptBase[41]дедуктивная и объектно-ориентированная система баз данных, основанная на оценщике запросов журнала данных: Пролог для инициируемых процедур и перезаписей, аксиоматизированный журнал данных под названием «Телос» для (мета) моделирования. В основном используется для концептуального моделирования и метамоделирования.BSD 2-пункт

Несвободное программное обеспечение

  • Datomic - это распределенная база данных, предназначенная для поддержки масштабируемых, гибких и интеллектуальных приложений, работающих на новых облачных архитектурах. В качестве языка запросов он использует Datalog.
  • FoundationDB предоставляет бесплатную привязку к базе данных для pyDatalog с руководством по его использованию.[42]
  • Семантическое пространство данных Leapsight (LSD) - это распределенная дедуктивная база данных, которая обеспечивает высокую доступность, отказоустойчивость, простоту эксплуатации и масштабируемость. LSD использует Leaplog (реализацию Datalog) для запросов и рассуждений и был создан Leapsight.[43]
  • LogicBlox, коммерческое внедрение Datalog, используемое для веб-приложений планирования розничной торговли и страхования.
  • Профиум Sense - это нативный RDF-совместимый база данных графов написано на Java. Он обеспечивает поддержку оценки Datalog для определенных пользователем правил.
  • .QL, коммерческий объектно-ориентированный вариант Datalog, созданный Semmle для анализа исходного кода с целью обнаружения уязвимостей.[44]
  • SecPAL язык политики безопасности, разработанный Microsoft Research.[45]
  • Звездная собака это база данных графов, реализованный в Ява. Он обеспечивает поддержку RDF и все СОВА 2 профили, обеспечивающие обширные возможности рассуждений, включая оценку журнала данных.
  • StrixDB: коммерческое хранилище графиков RDF, SPARQL совместимый с Lua Возможности вывода API и журнала данных. Может использоваться как httpd (HTTP-сервер Apache ) или автономный (хотя бета-версии находятся под Perl Artistic License 2.0).

Смотрите также

Рекомендации

  1. ^ Хуанг, Грин и Лу, «Журнал данных и новые приложения», SIGMOD 2011 (PDF), Калифорнийский университет в ДэвисеCS1 maint: несколько имен: список авторов (связь).
  2. ^ «Нейронный журнал данных во времени: обоснованное временное моделирование с помощью логической спецификации». Материалы ICML 2020.
  3. ^ Галлер, Эрве; Минкер, Джон Джек, ред. (1978), "Логика и базы данных, Симпозиум по логике и базам данных, Центр исследований и исследований Тулузы, 1977", Достижения в теории баз данных, Нью-Йорк: Plenum Press, ISBN  978-0-306-40060-5.
  4. ^ Абитебул, Серж; Халл, Ричард; Виану, Виктор (1995), Основы баз данных, п. 305, г. ISBN  9780201537710.
  5. ^ Лог данных
  6. ^ Бансилхон. «Волшебные наборы и другие странные способы реализации логических программ» (PDF). PT: UNL. Архивировано из оригинал (PDF) на 2012-03-08. Цитировать журнал требует | журнал = (помощь)
  7. ^ Пфеннинг, Франк; Schuermann, Карстен. «Руководство пользователя Twelf». CMU. Цитировать журнал требует | журнал = (помощь)
  8. ^ «Эффективное нисходящее вычисление запросов при хорошо обоснованной семантике» (PDF). Цитировать журнал требует | журнал = (помощь)
  9. ^ Грызь; Го; Лю; Зузарте (2004). «Выборка запросов в DB2 Universal Database» (PDF). Материалы международной конференции ACM SIGMOD 2004 по управлению данными - SIGMOD '04. п. 839. Дои:10.1145/1007568.1007664. ISBN  978-1581138597. S2CID  7775190.
  10. ^ Хиллебранд, Герд Дж. Канеллакис, Пэрис С; Майерсон, Гарри Джи; Варди, Моше Y (1995-11-01). «Неразрешимые проблемы ограниченности для программ регистрации данных». Журнал логического программирования. 25 (2): 163–190. Дои:10.1016 / 0743-1066 (95) 00051-К. ISSN  0743-1066.
  11. ^ Лифшиц (2011). «Программы регистрации данных и их стабильные модели». Даталог перезагружен. Конспект лекций по информатике. 6702. DE: Springer. С. 78–87. CiteSeerX  10.1.1.225.4027. Дои:10.1007/978-3-642-24206-9_5. ISBN  978-3-642-24205-2.
  12. ^ Кери, Готтлоб и Танка 1989, п. 146.
  13. ^ Кери, Готтлоб и Танка 1989, п. 149.
  14. ^ Кери, Готтлоб и Танка 1989, п. 150.
  15. ^ Кери, Готтлоб и Танка 1989, п. 154.
  16. ^ Система XSB, версия 3.7.x, Том 1: Руководство программиста (PDF).
  17. ^ Веб-страница проекта базы данных кораллов.
  18. ^ "DLVSYSTEM S.r.l. | DLV". www.dlvsystem.com. Получено 2018-11-29..
  19. ^ "DLVSYSTEM S.r.l. | DLV". www.dlvsystem.com. Получено 2018-11-29.
  20. ^ 4QL.
  21. ^ Веб-страница RDFox.
  22. ^ Лицензия RDFox, заархивировано из оригинал на 2018-02-21, получено 2018-11-29.
  23. ^ Компилятор суфле, 2018-12-12.
  24. ^ "Дина", Веб-страница Dyna, заархивировано из оригинал на 2016-01-17, получено 2016-11-07.
  25. ^ DDlog
  26. ^ Дифференциальный поток данных
  27. ^ AbcDatalog.
  28. ^ Ирис рассуждающий.
  29. ^ «Йена». Источник кузница.
  30. ^ SociaLite домашняя страница, заархивировано из оригинал на 2017-09-11, получено 2015-10-12.
  31. ^ Библиотека Грааля.
  32. ^ "Flix - язык программирования", flix.dev, получено 2019-08-26.
  33. ^ Рамсделл, "Даталог", Инструменты, NEU.
  34. ^ Сангкок, Y, "Обертка", Даталог Mitre, Git hub, (скомпилировано в JavaScript).
  35. ^ Cruanes, Simon, "datalog", лог данных, GitHub.
  36. ^ Саенс-Перес (2011), "DES: дедуктивная система баз данных", Электронные заметки по теоретической информатике, ES, 271: 63–78, Дои:10.1016 / j.entcs.2011.02.011.
  37. ^ "Лог данных", Ракетка (техническая документация).
  38. ^ "Datafun", Datafun в Racket (Ссылки на статью, обсуждение и сайт github).
  39. ^ Кенни, Кевин Б. (12–14 ноября 2014 г.). Диаграммы двоичных решений, реляционная алгебра и журнал данных: дедуктивные рассуждения для Tcl (PDF). Двадцать первая ежегодная конференция Tcl / Tk. Портланд, штат Орегон. Получено 29 декабря 2015.[постоянная мертвая ссылка ]
  40. ^ "bddbddb", Источник кузница.
  41. ^ ConceptBase.
  42. ^ Учебное пособие по FoundationDB Datalog, заархивировано из оригинал на 2013-08-09.
  43. ^ «Прыжок». Архивировано из оригинал на 2018-11-11.
  44. ^ Semmle QL.
  45. ^ «SecPAL». Microsoft Research. Архивировано из оригинал 23 февраля 2007 г.

Библиография

дальнейшее чтение