Datalog

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

[ред. | ред. код]

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

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

  1. забороняє складні вирази, як аргументи предикатів, наприклад, p (1, 2) допустимо, але не p (f (1), 2),
  2. накладає певні обмеження стратифікації[en] на використання заперечення та рекурсії,
  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 [Архівовано 26 січня 2016 у Wayback Machine.] Hadoop Бібліотека Clojure для запиту даних, що зберігаються на кластерах Hadoop. Apache
Clojure Datalog [Архівовано 28 грудня 2015 у Wayback Machine.] Бібліотека, що реалізує аспекти Datalog Eclipse Public License 1.0
Datascript [Архівовано 22 березня 2019 у Wayback Machine.] в пам'яті Незмінна база даних і рушій запитів 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[en] Фреймворк Semantic Web, який включає в себе реалізацію Datalog як частину свого механізму загального призначення, що забезпечує підтримку OWL і RDFS[en].[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 [Архівовано 26 січня 2022 у Wayback Machine.][27] Реалізація з відкритим вихідним кодом для навчання Datalog у курсах. GNU LGPL
Python pyDatalog [Архівовано 13 червня 2020 у Wayback Machine.] 11 діалектів SQL Додає логічне програмування до інструментів Python. Може виконувати логічні запити щодо баз даних або об'єктів Python, а також використовувати логічні пропозиції для визначення поведінки класів Python. GNU LGPL
Racket Datalog for Racket[28] GNU LGPL
Datafun[29] Узагальнений Datalog на Semilattices GNU LGPL
Ruby bloom [Архівовано 8 травня 2019 у Wayback Machine.] / bud Ruby DSL для програмування з конструктами, орієнтованими на дані, на основі розширення Dedalus [Архівовано 26 березня 2019 у Wayback Machine.] Datalog, який додає до логіки часовий вимір. BSD 3-Clause
Rust Datafrog [Архівовано 22 квітня 2019 у Wayback Machine.] 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[en] — це розподілена база даних, розроблена для забезпечення масштабованої, гнучкої та інтелектуальної програми, що працює на нових хмарних архітектурах. Він використовує Datalog як мову запитів.
  • FoundationDB[en] надає безкоштовну прив'язку бази даних для pyDatalog, з підручником з його використання.[33]
  • Leapsight Semantic Dataspace (LSD) — це розподілена дедуктивна база даних, яка пропонує високу доступність, відмовостійкість, простоту роботи та масштабованість. LSD використовує Leaplog (реалізацію Datalog) для запитів і міркувань. Була створена компанією Leapsight.[34]
  • LogicBlox, комерційна реалізація Datalog, використовується для роздрібного вебпланування та страхування.
  • .QL[en], комерційний об'єктно-орієнтований варіант Datalog, створений компанією Semmle[35].
  • SecPAL[en] — мова політики безпеки, розроблена компанією Microsoft Research[36].
  • Stardog — це база даних графів, реалізована в Java. Вона забезпечує підтримку RDF і всіх профілів OWL 2, забезпечуючи широкі можливості роздумів, включаючи оцінку даних.

Див. також

[ред. | ред. код]

Посилання

[ред. | ред. код]
  1. ↑ Huang, Green, and Loo, Datalog and Emerging applications, SIGMOD 2011 (PDF), UC Davis, архів оригіналу (PDF) за 22 жовтня 2020, процитовано 28 квітня 2019.
  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 (PDF). PT: UNL. Архів оригіналу (PDF) за 8 березня 2012.
  6. ↑ Pfenning, Frank; Schuermann, Carsten. Twelf User's Guide. CMU. Архів оригіналу за 2 лютого 2019. Процитовано 28 квітня 2019.
  7. ↑ Efficient top-down computation of queries under the well-founded semantics (PDF). Архів оригіналу (PDF) за 4 жовтня 2013. Процитовано 28 квітня 2019.
  8. ↑ Gryz; Guo; Liu; Zuzarte (2004). Query sampling in DB2 Universal Database (PDF). Proceedings of the 2004 ACM SIGMOD international conference on Management of data - SIGMOD '04. с. 839. doi:10.1145/1007568.1007664. ISBN 978-1581138597.
  9. ↑ Lifschitz (2011). Datalog Programs and Their Stable Models. Datalog Reloaded. Lecture Notes in Computer Science. Т. 6702. DE: Springer. с. 78—87. CiteSeerX 10.1.1.225.4027. doi:10.1007/978-3-642-24206-9_5. ISBN 978-3-642-24205-2.
  10. ↑ The XSB System, Version 3.7.x, Volume 1: Programmer's Manual (PDF), архів оригіналу (PDF) за 3 квітня 2020, процитовано 23 квітня 2019.
  11. ↑ Coral Database Project web page, архів оригіналу за 15 березня 2019, процитовано 23 квітня 2019.
  12. ↑ DLVSYSTEM S.r.l. | DLV. www.dlvsystem.com (амер.). Архів оригіналу за 13 вересня 2019. Процитовано 29 листопада 2018..
  13. ↑ DLVSYSTEM S.r.l. | DLV. www.dlvsystem.com (амер.). Архів оригіналу за 13 вересня 2019. Процитовано 29 листопада 2018.
  14. ↑ 4QL, архів оригіналу за 21 червня 2011, процитовано 23 квітня 2019.
  15. ↑ RDFox web page, архів оригіналу за 17 квітня 2019, процитовано 23 квітня 2019.
  16. ↑ RDFox licence, архів оригіналу за 21 лютого 2018, процитовано 29 листопада 2018.
  17. ↑ Souffle Compiler, 12 грудня 2018, архів оригіналу за 11 червня 2018, процитовано 23 квітня 2019.
  18. ↑ Dyna, Dyna web page, архів оригіналу за 17 січня 2016, процитовано 7 листопада 2016.
  19. ↑ AbcDatalog, архів оригіналу за 11 квітня 2019, процитовано 23 квітня 2019.
  20. ↑ Iris reasoner, архів оригіналу за 2 лютого 2022, процитовано 23 квітня 2019.
  21. ↑ Jena. Source forge. Архів оригіналу за 5 травня 2019. Процитовано 5 травня 2019.
  22. ↑ SociaLite homepage, архів оригіналу за 11 вересня 2017, процитовано 12 жовтня 2015.
  23. ↑ Graal library, архів оригіналу за 6 травня 2019, процитовано 23 квітня 2019.
  24. ↑ Flix The Programming Language, flix.github.io (англ.), архів оригіналу за 19 квітня 2019, процитовано 3 травня 2017.
  25. ↑ Ramsdell, Datalog, Tools, NEU, архів оригіналу за 11 січня 2011, процитовано 23 квітня 2019.
  26. ↑ Sangkok, Y, Wrapper, Mitre Datalog, Git hub{{citation}}: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url (посилання), (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), архів оригіналу за 1 червня 2019, процитовано 23 квітня 2019.
  29. ↑ Datafun, Datafun in Racket (Links to paper, talk and github site), архів оригіналу за 9 квітня 2019, процитовано 23 квітня 2019.
  30. ↑ Kenny, Kevin B (12–14 November 2014). Binary decision diagrams, relational algebra, and Datalog: deductive reasoning for Tcl (PDF). Twenty-first Annual Tcl/Tk Conference. Portland, Oregon. Процитовано 29 грудня 2015.[недоступне посилання з 01.12.2016]
  31. ↑ bddbddb, Source forge, архів оригіналу за 28 липня 2011, процитовано 23 квітня 2019.
  32. ↑ ConceptBase, архів оригіналу за 1 квітня 2009, процитовано 23 квітня 2019.
  33. ↑ FoundationDB Datalog Tutorial, архів оригіналу за 9 серпня 2013.
  34. ↑ Leapsight. Архів оригіналу за 11 листопада 2018.
  35. ↑ Semmle, архів оригіналу за 24 квітня 2019, процитовано 23 квітня 2019
  36. ↑ SecPAL. Microsoft Research. Архів оригіналу за 23 лютого 2007.
Отримано з https://uk.wikipedia.org/w/index.php?title=Datalog&oldid=41969160