Datalog (Datalog)

Перейти к навигации Перейти к поиску
Datalog
Класс языка Логический, Декларативное
Появился в 1986; 38 лет назад (1986)
Система типов Слабая
Диалекты Datomic, pyDatalog, Dyna и т.д.

Datalog — язык декларативного логического программирования. Хотя синтаксически он выглядит как подмножество Prolog, Datalog обычно использует восходящую, а не нисходящую модель разрешения выражений. Это отличие приводит к значительному отличию поведения и свойств от Пролога. Он часто используется в качестве языка запросов для дедуктивных баз данных. В последние годы Datalog нашел новое применение в интеграции данных, извлечении информации, создании сетей, анализе программ, безопасности, облачных вычислениях и машинном обучении[1][2].

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

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

[править | править код]

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

В отличие от Пролога, Datalog:

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

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

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

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

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

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

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

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

[править | править код]

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

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

parent(xerces, brooke).
parent(brooke, damocles).

Вот что они означают: xerces является родителем brooke, а brooke является родителем damocles. Имена пишутся строчными буквами, потому что строки, начинающиеся с прописной буквы, обозначают переменные.

Примечания

[править | править код]
  1. Huang, Green, and Loo, "Datalog and Emerging applications", SIGMOD 2011 (PDF), UC Davis, Архивировано (PDF) 22 октября 2020, Дата обращения: 17 августа 2022{{citation}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка) Источник. Дата обращения: 17 августа 2022. Архивировано 22 октября 2020 года..
  2. Mei, Hongyuan; Qin, Guanghui; Xu, Minjie; Eisner, Jason (2020). "Neural Datalog Through Time: Informed Temporal Modeling via Logical Specification". Proceedings of ICML 2020. arXiv:2006.16723.
  3. Logic and data bases. — New York, 1978. — viii, 458 pages с. — ISBN 0-306-40060-X, 978-0-306-40060-5.
  4. S. Abiteboul. Foundations of databases. — Reading, Mass.: Addison-Wesley, 1995. — xviii, 685 pages с. — ISBN 0-201-53771-0, 978-0-201-53771-0.
  5. Datalog (презентация). web.archive.org (25 марта 2017). Дата обращения: 20 августа 2022. Архивировано 25 марта 2017 года.
  6. Bancilhon. "Magic sets and other strange ways to implement logic programs" (PDF). PT: UNL. Архивировано из оригинала (PDF) 8 марта 2012. {{cite journal}}: Cite journal требует |journal= (справка)
  7. Pfenning, Frank; Schuermann, Carsten. "Twelf User's Guide". CMU. Архивировано 22 августа 2022. Дата обращения: 22 августа 2022. {{cite journal}}: Cite journal требует |journal= (справка)
  8. "Efficient top-down computation of queries under the well-founded semantics" (PDF). Архивировано (PDF) 4 октября 2013. Дата обращения: 22 августа 2022. {{cite journal}}: Cite journal требует |journal= (справка)
  9. Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data : 2004, Paris, France, June 13-18, 2004.. — [New York]: Association for Computing Machinery, 2004. — xvii, 988 pages с. — ISBN 1-58113-859-8, 978-1-58113-859-7.
  10. Gerd G Hillebrand, Paris C Kanellakis, Harry G Mairson, Moshe Y Vardi. Undecidable boundedness problems for datalog programs (англ.) // The Journal of Logic Programming. — 1995-11. — Vol. 25, iss. 2. — P. 163–190. — doi:10.1016/0743-1066(95)00051-K. Архивировано 7 мая 2021 года.