Datalog

Datalog — це декларативна логічна мова програмування, яка синтаксично є підмножиною мови Prolog. Вона часто використовується як мова запитів для дедуктивних баз даних. В останні роки Datalog знайшла нове застосування в інтеграції даних, добуванні даних, мережах, аналізі програм, безпеці та хмарних обчисленнях.[1]

Її походження сходить до початку логічного програмування, але вона стала відомою, як окрема область, близько 1977 року, коли Херве Галлер і Джек Мінкер організували семінар з логіки і баз даних.[2] Термін Datalog приписується Девіду Майєру.[3]

Особливості, обмеження та розширення

На відміну від Прологу, твердження програми Datalog можна вказати в будь-якому порядку. Крім того, Datalog-запити на скінченних множинах гарантовано припиняються, тому Datalog не має оператора cut. Це робить Datalog повністю декларативною мовою.

На відміну від Prolog, Datalog:

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

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

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

Кілька розширень були зроблені для Datalog, наприклад, для підтримки агрегатних функцій, для забезпечення об'єктно-орієнтованого програмування, або для забезпечення можливих роз'єднань як керівників речень. Ці розширення суттєво впливають на визначення семантики Datalog і на реалізацію відповідного інтерпретатора Datalog.

Приклад

Ці два рядки визначають два факти, тобто речі, які завжди виконуються:

parent(bill, mary).
parent(mary, john).

Це означає, що вони мають на увазі: Білл є батьком Мері, а Мері є батьком відносно Джона. Імена записуються малими літерами, оскільки рядки, що починаються з великої літери, позначають змінні.

Ці два рядки визначають правила, які визначають, як нові факти можуть бути виведені з відомих фактів.

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

meaning:

  • X предок Y, якщо X є батьком для Y.
  • X предок Y, якщо X батько деякого Z, і Z предок Y.

Цей рядок є запитом:

?- ancestor(bill, X).

Цей запит означає: знайти всіх таких Х, для яких Білл є предком? Запит поверне Мері та Джон, якщо він буде виконаний у програмі Datalog, яка містить факти та правила, описані вище.

Детальніше про правила: правило має :- символ посередині: частина ліворуч від цього символу є головою правила, частина праворуч — тіло. Правило читається так: <head> вважається істиною, якщо <body> є істинним. Великі літери в правилах позначають змінні: у прикладі ми не знаємо, хто X або Y, але деякий X є предком деякого Y, якщо X є батьком Y. Впорядкування пунктів не має значення в Datalog, на відміну від Prolog, який залежить від впорядкованості виразів для обчислення результату виклику запиту.

Datalog розрізняє символи екстенсійних предикатів (визначених фактами) і інтенсійні предикатні символи (визначені правилами)[9]. У наведеному вище прикладі ancestor є інтенсійним предикатним символом, а parent — екстенсійним. Предикати також можуть бути визначені фактами та правилами, а тому не можуть бути чисто ні повністю екстенсенційними, ні інтенціональними, але будь-яку програму Datalog можна переписати в еквівалентну програму без таких предикатних символів з ролями, що дублюються.

Системи, що реалізують Datalog

Ось короткий перелік систем, які базуються на Datalog або надають інтерпретатор Datalog:

Вільне програмне забезпечення або програми з відкритим вихідним кодом
Написана мовоюІм'яСпробувати онлайнЗовнішні бази данихОписЛіцензія
C XSB Система логічного програмування та дедуктивних баз даних для Unix та MS Windows із табуляцією, що дає Datalog-подібне завершення та ефективність, включаючи інкрементальну оцінку[10] GNU LGPL
C++ Coral[11] Система дедуктивних баз даних, написана на С++ з напівнаївною оцінкою даних. Розроблена в 1988—1997 роках. користувацька ліцензія, безкоштовна для некомерційного використання
DLV[12] Розширення Datalog, яке підтримує диз'юнктивні твердження у заголовку. користувацька ліцензія, безкоштовна для академічного та некомерційного використання освіти, а також для використання неприбутковими організаціями[13]
Inter4QL[14] Інтерпретатор командного рядка з відкритим кодом Datalog-подібної мови запитів 4QL, реалізованої в C ++ для Windows, Mac OS X і Linux. Заперечення допускається як в заголовках, так і в тілах, а також у рекурсії GNU GPL v3
RDFox[15] RDF потрійне сховище з Datalog міркуванням. Реалізує алгоритм FBF для додаткової оцінки. користувацька ліцензія, безкоштовна для некомерційного використання[16]
Souffle[17] Компілятор Datalog у C++ з відкритим вихідним кодом, що перетворює Datalog у високопродуктивний, паралельний C ++ код, спеціально розроблений для складних запитів Datalog над великими наборами даних, наприклад, тих, що зустрічаються в контексті статичного аналізу програми. UPL v1.0
Clojure Cascalog Hadoop Бібліотека Clojure для запиту даних, що зберігаються на кластерах Hadoop. Apache
Clojure Datalog Бібліотека, що реалізує аспекти Datalog Eclipse Public License 1.0
Datascript в пам'яті Незмінна база даних і рушій запитів Datalog, який працює в браузері Eclipse Public License 1.0
Haskell Dyna[18] Dyna є декларативною мовою програмування для статистичного програмування штучного інтелекту. Мова базується на Datalog, підтримує як пряме, так і зворотне зв'язування, а також інкрементну оцінку. GNU AGPL v3
Java AbcDatalog[19] AbcDatalog є реалізацією мови логічного програмування Datalog з відкритим кодом, написаної на Java. Вона надає готові до використання реалізації загальних алгоритмів оцінки Datalog, а також деяких експериментальних багатопотокових двигунів оцінки. Вона підтримує мовні особливості поза ядром Datalog, такі як явна (дис-)уніфікація виразів і стратифіковане заперечення. Крім того, AbcDatalog розроблений, щоб бути легко розширюваним з новими двигунами оцінки та новими функціями мови. BSD
IRIS[20] IRIS розширює Datalog функціональними символами, вбудованими предикатами, локально стратифікованими або нестратифікованими логічними програмами (з використанням обґрунтованої семантики), небезпечними правилами та типами XML-схем. GNU LGPL v2.1
Jena Фреймворк Semantic Web, який включає в себе реалізацію Datalog як частину свого механізму загального призначення, що забезпечує підтримку OWL і RDFS.[21] Apache v2
SociaLite[22] SociaLite — це варіант Datalog для великомасштабного аналізу графів, розробленого в Стенфорді Apache v2
Graal[23] Graal — це інструментарій Java, присвячений запитам баз знань у рамках екзистенціальних правил, тобто Datalog +/-. CeCILL v2.1
Flix[24] Функціональна та логічна мова програмування, натхненна Datalog, розширена за допомогою визначених користувачем решіток та монотонних фільтрів / функцій передачі. Apache v2
Lua Datalog[25] Так[26] Легка система дедуктивної бази даних. GNU LGPL
Prolog DES[27] Реалізація з відкритим вихідним кодом для навчання Datalog у курсах. GNU LGPL
Python pyDatalog 11 діалектів SQL Додає логічне програмування до інструментів Python. Може виконувати логічні запити щодо баз даних або об'єктів Python, а також використовувати логічні пропозиції для визначення поведінки класів Python. GNU LGPL
Racket Datalog for Racket[28] GNU LGPL
Datafun[29] Узагальнений Datalog на Semilattices GNU LGPL
Ruby bloom / bud Ruby DSL для програмування з конструктами, орієнтованими на дані, на основі розширення Dedalus Datalog, який додає до логіки часовий вимір. BSD 3-Clause
Rust Datafrog Datafrog — це легкий рушій Datalog, призначений для вбудовування в інші програми Rust. MIT License / Apache 2.0
Tcl tclbdd[30] Реалізація на основі бінарних діаграм прийняття рішень. Створений для підтримки розробки оптимізувального компілятора для Tcl. BSD
Інші або невідомі мови програмування bddbddb[31] Реалізація Datalog виконана у Стенфордському університеті. В основному він використовується для запиту байт-коду Java, включаючи аналіз точок на великі програми Java GNU LGPL
ConceptBase[32] Дедуктивна та об'єктно-орієнтована система баз даних, заснована на оцінювачі запитів Datalog. В основному він використовується для концептуального моделювання та метамоделювання BSD 2-Clause

Невільне програмне забезпечення
  • Datomic — це розподілена база даних, розроблена для забезпечення масштабованої, гнучкої та інтелектуальної програми, що працює на нових хмарних архітектурах. Він використовує Datalog як мову запитів.
  • FoundationDB надає безкоштовну прив'язку бази даних для pyDatalog, з підручником з його використання.[33]
  • Leapsight Semantic Dataspace (LSD) — це розподілена дедуктивна база даних, яка пропонує високу доступність, відмовостійкість, простоту роботи та масштабованість. LSD використовує Leaplog (реалізацію Datalog) для запитів і міркувань. Була створена компанією Leapsight.[34]
  • LogicBlox, комерційна реалізація Datalog, використовується для роздрібного веб-планування та страхування.
  • Profium Sense є рідною RDF-сумісною базою даних, написаною на Java. Вона використовує Datalog для оцінки підтримки користувацьких правил.
  • .QL, комерційний об'єктно-орієнтований варіант Datalog, створений компанією Semmle[35].
  • SecPAL — мова політики безпеки, розроблена компанією Microsoft Research[36].
  • Stardog — це база даних графів, реалізована в Java. Вона забезпечує підтримку RDF і всіх профілів OWL 2, забезпечуючи широкі можливості роздумів, включаючи оцінку даних.

Див. також

Посилання
  1. Huang, Green, and Loo. Datalog and Emerging applications. SIGMOD 2011. UC Davis..
  2. Gallaire, Hervé; Minker, John ‘Jack’, ред. (1978). Logic and Data Bases, Symposium on Logic and Data Bases, Centre d'études et de recherches de Toulouse, 1977. Advances in Data Base Theory. New York: Plenum Press. ISBN 978-0-306-40060-5..
  3. Abiteboul, Serge; Hull, Richard; Vianu, Victor (1995). Foundations of databases. с. 305. ISBN 9780201537710..
  4. Datalog
  5. Bancilhon. Magic sets and other strange ways to implement logic programs. PT: UNL. Архів оригіналу за 8 березня 2012.
  6. Pfenning, Frank; Schuermann, Carsten. Twelf User's Guide. CMU.
  7. Efficient top-down computation of queries under the well-founded semantics.
  8. Gryz; Guo; Liu; Zuzarte (2004). Query sampling in DB2 Universal Database. Proceedings of the 2004 ACM SIGMOD international conference on Management of data - SIGMOD '04. с. 839. ISBN 978-1581138597. doi:10.1145/1007568.1007664. Проігноровано невідомий параметр |chapter-format= (довідка)
  9. Lifschitz (2011). Datalog Programs and Their Stable Models. Datalog Reloaded. Lecture Notes in Computer Science 6702. DE: Springer. с. 78–87. ISBN 978-3-642-24205-2. doi:10.1007/978-3-642-24206-9_5. Проігноровано невідомий параметр |citeseerx= (довідка)
  10. The XSB System, Version 3.7.x, Volume 1: Programmer's Manual..
  11. Coral Database Project web page..
  12. DLVSYSTEM S.r.l. | DLV. www.dlvsystem.com (амер.). Процитовано 29 листопада 2018..
  13. DLVSYSTEM S.r.l. | DLV. www.dlvsystem.com (амер.). Процитовано 29 листопада 2018.
  14. 4QL..
  15. RDFox web page..
  16. RDFox licence. Архів оригіналу за 21 лютого 2018. Процитовано 29 листопада 2018..
  17. Souffle Compiler. 12 грудня 2018..
  18. Dyna. Dyna web page. Архів оригіналу за 17 січня 2016. Процитовано 7 листопада 2016..
  19. AbcDatalog..
  20. Iris reasoner..
  21. Jena. Source forge.
  22. SociaLite homepage. Архів оригіналу за 11 вересня 2017. Процитовано 12 жовтня 2015..
  23. Graal library..
  24. Flix The Programming Language. flix.github.io (англ.). Процитовано 3 травня 2017..
  25. Ramsdell. Datalog. Tools. NEU..
  26. Sangkok, Y. Wrapper. Mitre Datalog. Git hub., (compiled to JavaScript).
  27. Saenz-Perez (2011). DES: A Deductive Database System. Electronic Notes in Theoretical Computer Science (ES) 271: 63–78. doi:10.1016/j.entcs.2011.02.011..
  28. Datalog. Racket (technical documentation)..
  29. Datafun. Datafun in Racket (Links to paper, talk and github site)..
  30. Kenny, Kevin B (12–14 November 2014). Binary decision diagrams, relational algebra, and Datalog: deductive reasoning for Tcl Twenty-first Annual Tcl/Tk Conference. Portland, Oregon. Процитовано 29 грудня 2015.[недоступне посилання з 01.12.2016]
  31. bddbddb. Source forge..
  32. ConceptBase..
  33. FoundationDB Datalog Tutorial. Архів оригіналу за 9 серпня 2013..
  34. Leapsight. Архів оригіналу за 11 листопада 2018.
  35. Semmle.
  36. SecPAL. Microsoft Research. Архів оригіналу за 23 лютого 2007.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.