Datalog
Ця стаття є сирим перекладом з англійської мови. Можливо, вона створена за допомогою машинного перекладу або перекладачем, який недостатньо володіє обома мовами. Будь ласка, допоможіть поліпшити переклад. (23 квітня 2019) |
Datalog — це декларативна логічна мова програмування, яка синтаксично є підмножиною мови Prolog. Вона часто використовується як мова запитів для дедуктивних баз даних. В останні роки Datalog знайшла нове застосування в інтеграції даних[en], добуванні даних, мережах, аналізі програм[en], безпеці та хмарних обчисленнях.[1]
Її походження сходить до початку логічного програмування, але вона стала відомою, як окрема область, близько 1977 року, коли Херве Галлер і Джек Мінкер[en] організували семінар з логіки і баз даних.[2] Термін Datalog приписується Девіду Майєру[en].[3]
Особливості, обмеження та розширення
На відміну від Прологу, твердження програми Datalog можна вказати в будь-якому порядку. Крім того, Datalog-запити на скінченних множинах гарантовано припиняються, тому Datalog не має оператора cut. Це робить Datalog повністю декларативною мовою.
На відміну від Prolog, Datalog:
- забороняє складні вирази, як аргументи предикатів, наприклад, p (1, 2) допустимо, але не p (f (1), 2),
- накладає певні обмеження стратифікації[en] на використання заперечення та рекурсії,
- вимагає, щоб кожна змінна, що з'являється в заголовку речення, також з'являлася в неарифметичному позитивному (тобто не запереченому) літералі в тілі речення,
- вимагає, щоб кожна змінна, що з'являється в негативному літералі в тілі речення, також з'являлася в деякому позитивному літералі в тілі речення.[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, забезпечуючи широкі можливості роздумів, включаючи оцінку даних.
Див. також
- Програмування наборами відповідей
- SWRL[en]
- D4 (мова програмування)[en]
- Кон'юнктивний запит[en]
Посилання
- ↑ Huang, Green, and Loo, Datalog and Emerging applications, SIGMOD 2011 (PDF), UC Davis, архів оригіналу (PDF) за 22 жовтня 2020, процитовано 28 квітня 2019.
- ↑ 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.
- ↑ Abiteboul, Serge; Hull, Richard; Vianu, Victor (1995), Foundations of databases, с. 305, ISBN 9780201537710.
- ↑ Datalog
- ↑ Bancilhon. Magic sets and other strange ways to implement logic programs (PDF). PT: UNL. Архів оригіналу (PDF) за 8 березня 2012.
- ↑ Pfenning, Frank; Schuermann, Carsten. Twelf User's Guide. CMU. Архів оригіналу за 2 лютого 2019. Процитовано 28 квітня 2019.
- ↑ Efficient top-down computation of queries under the well-founded semantics (PDF). Архів оригіналу (PDF) за 4 жовтня 2013. Процитовано 28 квітня 2019.
- ↑ 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.
- ↑ 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.
- ↑ The XSB System, Version 3.7.x, Volume 1: Programmer's Manual (PDF), архів оригіналу (PDF) за 3 квітня 2020, процитовано 23 квітня 2019.
- ↑ Coral Database Project web page, архів оригіналу за 15 березня 2019, процитовано 23 квітня 2019.
- ↑ DLVSYSTEM S.r.l. | DLV. www.dlvsystem.com (амер.). Архів оригіналу за 13 вересня 2019. Процитовано 29 листопада 2018..
- ↑ DLVSYSTEM S.r.l. | DLV. www.dlvsystem.com (амер.). Архів оригіналу за 13 вересня 2019. Процитовано 29 листопада 2018.
- ↑ 4QL, архів оригіналу за 21 червня 2011, процитовано 23 квітня 2019.
- ↑ RDFox web page, архів оригіналу за 17 квітня 2019, процитовано 23 квітня 2019.
- ↑ RDFox licence, архів оригіналу за 21 лютого 2018, процитовано 29 листопада 2018.
- ↑ Souffle Compiler, 12 грудня 2018, архів оригіналу за 11 червня 2018, процитовано 23 квітня 2019.
- ↑ Dyna, Dyna web page, архів оригіналу за 17 січня 2016, процитовано 7 листопада 2016.
- ↑ AbcDatalog, архів оригіналу за 11 квітня 2019, процитовано 23 квітня 2019.
- ↑ Iris reasoner, архів оригіналу за 2 лютого 2022, процитовано 23 квітня 2019.
- ↑ Jena. Source forge. Архів оригіналу за 5 травня 2019. Процитовано 5 травня 2019.
- ↑ SociaLite homepage, архів оригіналу за 11 вересня 2017, процитовано 12 жовтня 2015.
- ↑ Graal library, архів оригіналу за 6 травня 2019, процитовано 23 квітня 2019.
- ↑ Flix The Programming Language, flix.github.io (англ.), архів оригіналу за 19 квітня 2019, процитовано 3 травня 2017.
- ↑ Ramsdell, Datalog, Tools, NEU, архів оригіналу за 11 січня 2011, процитовано 23 квітня 2019.
- ↑ Sangkok, Y, Wrapper, Mitre Datalog, Git hub
{{citation}}
: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url (посилання), (compiled to JavaScript). - ↑ 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.
- ↑ Datalog, Racket (technical documentation), архів оригіналу за 1 червня 2019, процитовано 23 квітня 2019.
- ↑ Datafun, Datafun in Racket (Links to paper, talk and github site), архів оригіналу за 9 квітня 2019, процитовано 23 квітня 2019.
- ↑ 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]
- ↑ bddbddb, Source forge, архів оригіналу за 28 липня 2011, процитовано 23 квітня 2019.
- ↑ ConceptBase, архів оригіналу за 1 квітня 2009, процитовано 23 квітня 2019.
- ↑ FoundationDB Datalog Tutorial, архів оригіналу за 9 серпня 2013.
- ↑ Leapsight. Архів оригіналу за 11 листопада 2018.
- ↑ Semmle, архів оригіналу за 24 квітня 2019, процитовано 23 квітня 2019
- ↑ SecPAL. Microsoft Research. Архів оригіналу за 23 лютого 2007.