Loading AI tools
З Вікіпедії, вільної енциклопедії
Datalog — це декларативна логічна мова програмування, яка синтаксично є підмножиною мови Prolog. Вона часто використовується як мова запитів для дедуктивних баз даних. В останні роки Datalog знайшла нове застосування в інтеграції даних[en], добуванні даних, мережах, аналізі програм[en], безпеці та хмарних обчисленнях.[1]
Ця стаття є сирим перекладом з англійської мови. Можливо, вона створена за допомогою машинного перекладу або перекладачем, який недостатньо володіє обома мовами. (23 квітня 2019) |
Її походження сходить до початку логічного програмування, але вона стала відомою, як окрема область, близько 1977 року, коли Херве Галлер і Джек Мінкер[en] організували семінар з логіки і баз даних.[2] Термін Datalog приписується Девіду Майєру[en].[3]
На відміну від Прологу, твердження програми Datalog можна вказати в будь-якому порядку. Крім того, Datalog-запити на скінченних множинах гарантовано припиняються, тому Datalog не має оператора cut. Це робить Datalog повністю декларативною мовою.
На відміну від Prolog, Datalog:
Оцінка запитів за допомогою 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:
Цей рядок є запитом:
?- ancestor(bill, X).
Цей запит означає: знайти всіх таких Х, для яких Білл є предком? Запит поверне Мері та Джон, якщо він буде виконаний у програмі Datalog, яка містить факти та правила, описані вище.
Детальніше про правила: правило має :- символ посередині: частина ліворуч від цього символу є головою правила, частина праворуч — тіло. Правило читається так: <head> вважається істиною, якщо <body> є істинним. Великі літери в правилах позначають змінні: у прикладі ми не знаємо, хто X або Y, але деякий X є предком деякого Y, якщо X є батьком Y. Впорядкування пунктів не має значення в Datalog, на відміну від Prolog, який залежить від впорядкованості виразів для обчислення результату виклику запиту.
Datalog розрізняє символи екстенсійних предикатів (визначених фактами) і інтенсійні предикатні символи (визначені правилами)[9]. У наведеному вище прикладі ancestor
є інтенсійним предикатним символом, а parent
— екстенсійним. Предикати також можуть бути визначені фактами та правилами, а тому не можуть бути чисто ні повністю екстенсенційними, ні інтенціональними, але будь-яку програму 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 |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.