Datalog — це декларативна логічна мова програмування, яка синтаксично є підмножиною мови Prolog. Вона часто використовується як мова запитів для дедуктивних баз даних. В останні роки Datalog знайшла нове застосування в , добуванні даних, мережах, , безпеці та хмарних обчисленнях..
Її походження сходить до початку логічного програмування, але вона стала відомою, як окрема область, близько 1977 року, коли Херве Галлер і організували семінар з логіки і баз даних.. Термін Datalog приписується ..
Особливості, обмеження та розширення На відміну від Прологу, твердження програми Datalog можна вказати в будь-якому порядку. Крім того, Datalog-запити на скінченних множинах гарантовано припиняються, тому Datalog не має оператора cut. Це робить Datalog повністю декларативною мовою.
На відміну від Prolog, Datalog: забороняє складні вирази, як аргументи предикатів, наприклад, p (1, 2) допустимо, але не p (f (1), 2), накладає певні обмеження на використання заперечення та рекурсії, вимагає, щоб кожна змінна, що з'являється в заголовку речення, також з'являлася в неарифметичному позитивному (тобто не запереченому) літералі в тілі речення, вимагає, щоб кожна змінна, що з'являється в негативному літералі в тілі речення, також з'являлася в деякому позитивному літералі в тілі речення.Datalog
Оцінка запитів за допомогою Datalog базується на логіці першого порядку і, таким чином є правильною і повною. Однак, Datalog не є повною за Тюрингом, і тому використовується як доменна мова, яка має переваги ефективних алгоритмів, розроблених для вирішення запитів. Дійсно, були запропоновані різні методи для ефективного виконання запитів, наприклад, алгоритму Magic Sets, табличного логічного програмування або SLG тверджень.
Деякі широко використовувані системи баз даних включають ідеї та алгоритми, розроблені для Datalog. Наприклад, стандарт SQL:1999 включає рекурсивні запити, а алгоритм Magic Sets (спочатку розроблений для більш швидкої оцінки запитів Datalog) реалізований в DB2 IBM. Крім того, програми Datalog знаходяться за спеціалізованими системами баз даних, такими як база даних Intellidimension для семантичної мережі.
Кілька розширень були зроблені для Datalog, наприклад, для підтримки агрегатних функцій, для забезпечення об'єктно-орієнтованого програмування, або для забезпечення можливих роз'єднань як керівників речень. Ці розширення суттєво впливають на визначення семантики Datalog і на реалізацію відповідного інтерпретатора Datalog.
Приклад Ці два рядки визначають два факти, тобто речі, які завжди виконуються:
Це означає, що вони мають на увазі: Білл є батьком Мері, а Мері є батьком відносно Джона. Імена записуються малими літерами, оскільки рядки, що починаються з великої літери, позначають змінні.
Ці два рядки визначають правила, які визначають, як нові факти можуть бути виведені з відомих фактів.
meaning:
X предок Y, якщо X є батьком для Y. X предок Y, якщо X батько деякого Z, і Z предок Y.
Цей рядок є запитом:
Цей запит означає: знайти всіх таких Х, для яких Білл є предком? Запит поверне Мері та Джон, якщо він буде виконаний у програмі Datalog, яка містить факти та правила, описані вище.
Детальніше про правила: правило має :- символ посередині: частина ліворуч від цього символу є головою правила, частина праворуч — тіло. Правило читається так: <head> вважається істиною, якщо <body> є істинним. Великі літери в правилах позначають змінні: у прикладі ми не знаємо, хто X або Y, але деякий X є предком деякого Y, якщо X є батьком Y. Впорядкування пунктів не має значення в Datalog, на відміну від Prolog, який залежить від впорядкованості виразів для обчислення результату виклику запиту.
Datalog розрізняє символи екстенсійних предикатів (визначених фактами) і інтенсійні предикатні символи (визначені правилами). У наведеному вище прикладі є інтенсійним предикатним символом, а — екстенсійним. Предикати також можуть бути визначені фактами та правилами, а тому не можуть бути чисто ні повністю екстенсенційними, ні інтенціональними, але будь-яку програму Datalog можна переписати в еквівалентну програму без таких предикатних символів з ролями, що дублюються.
Системи, що реалізують Datalog Ось короткий перелік систем, які базуються на Datalog або надають інтерпретатор Datalog:
Вільне програмне забезпечення або програми з відкритим вихідним кодом Написана мовою Ім'я Спробувати онлайн Зовнішні бази даних Опис ЛіцензіяCXSBСистема логічного програмування та дедуктивних баз даних для Unix та MS Windows із табуляцією, що дає Datalog-подібне завершення та ефективність, включаючи інкрементальну оцінкуThe XSB System, Version 3.7.x, . C++Coral.Система дедуктивних баз даних, написана на С++ з напівнаївною оцінкою даних. Розроблена в 1988—1997 роках. DLV.Розширення Datalog, яке підтримує диз'юнктивні твердження у заголовку. Inter4QL.Інтерпретатор командного рядка з відкритим кодом Datalog-подібної мови запитів 4QL, реалізованої в C ++ для Windows, Mac OS X і Linux. Заперечення допускається як в заголовках, так і в тілах, а також у рекурсіїRDFox.RDF потрійне сховище з Datalog міркуванням. Реалізує алгоритм FBF для додаткової оцінки. Souffle.Компілятор Datalog у C++ з відкритим вихідним кодом, що перетворює Datalog у високопродуктивний, паралельний C ++ код, спеціально розроблений для складних запитів Datalog над великими наборами даних, наприклад, тих, що зустрічаються в контексті статичного аналізу програми. ClojureCascalog HadoopБібліотека Clojure для запиту даних, що зберігаються на кластерах Hadoop. Clojure Datalog Бібліотека, що реалізує аспекти Datalog Datascript в пам'ятіНезмінна база даних і рушій запитів Datalog, який працює в браузері HaskellDyna.Dyna є декларативною мовою програмування для статистичного програмування штучного інтелекту. Мова базується на Datalog, підтримує як пряме, так і зворотне зв'язування, а також інкрементну оцінку. JavaAbcDatalog.AbcDatalog є реалізацією мови логічного програмування Datalog з відкритим кодом, написаної на Java. Вона надає готові до використання реалізації загальних алгоритмів оцінки Datalog, а також деяких експериментальних багатопотокових двигунів оцінки. Вона підтримує мовні особливості поза ядром Datalog, такі як явна (дис-)уніфікація виразів і стратифіковане заперечення. Крім того, AbcDatalog розроблений, щоб бути легко розширюваним з новими двигунами оцінки та новими функціями мови.IRIS.IRIS розширює Datalog функціональними символами, вбудованими предикатами, локально стратифікованими або нестратифікованими логічними програмами (з використанням обґрунтованої семантики), небезпечними правилами та типами XML-схем. v2.1Фреймворк Semantic Web, який включає в себе реалізацію Datalog як частину свого механізму загального призначення, що забезпечує підтримку OWL і . SociaLite .SociaLite — це варіант Datalog для великомасштабного аналізу графів, розробленого в Стенфорді Graal.Graal — це інструментарій Java, присвячений запитам баз знань у рамках екзистенціальних правил, тобто Datalog +/-. Flix .Функціональна та логічна мова програмування, натхненна Datalog, розширена за допомогою визначених користувачем решіток та монотонних фільтрів / функцій передачі. LuaDatalog . , (compiled to JavaScript).Легка система дедуктивної бази даних.PrologDES .Реалізація з відкритим вихідним кодом для навчання Datalog у курсах.PythonpyDatalog 11 діалектів SQLДодає логічне програмування до інструментів Python. Може виконувати логічні запити щодо баз даних або об'єктів Python, а також використовувати логічні пропозиції для визначення поведінки класів Python.RacketDatalog for Racket.Datafun.Узагальнений Datalog на SemilatticesRubybloom / budRuby DSL для програмування з конструктами, орієнтованими на дані, на основі розширення Dedalus Datalog, який додає до логіки часовий вимір. 3-ClauseRustDatafrog Datafrog — це легкий рушій Datalog, призначений для вбудовування в інші програми Rust.MIT License / Apache 2.0TcltclbddРеалізація на основі бінарних діаграм прийняття рішень. Створений для підтримки розробки оптимізувального компілятора для Tcl. Інші або невідомі мови програмуванняbddbddb.Реалізація Datalog виконана у Стенфордському університеті. В основному він використовується для запиту байт-коду Java, включаючи аналіз точок на великі програми JavaConceptBase.Дедуктивна та об'єктно-орієнтована система баз даних, заснована на оцінювачі запитів Datalog. В основному він використовується для концептуального моделювання та метамоделювання 2-Clause
Невільне програмне забезпечення — це розподілена база даних, розроблена для забезпечення масштабованої, гнучкої та інтелектуальної програми, що працює на нових хмарних архітектурах. Він використовує Datalog як мову запитів. надає безкоштовну прив'язку бази даних для pyDatalog, з підручником з його використання. . Leapsight Semantic Dataspace (LSD) — це розподілена дедуктивна база даних, яка пропонує високу доступність, відмовостійкість, простоту роботи та масштабованість. LSD використовує Leaplog (реалізацію Datalog) для запитів і міркувань. Була створена компанією Leapsight. LogicBlox, комерційна реалізація Datalog, використовується для роздрібного вебпланування та страхування. , комерційний об'єктно-орієнтований варіант Datalog, створений компанією Semmle. — мова політики безпеки, розроблена компанією Microsoft Research . Stardog — це база даних графів, реалізована в Java. Вона забезпечує підтримку RDF і всіх профілів OWL 2, забезпечуючи широкі можливості роздумів, включаючи оцінку даних.
Див. також Програмування наборами відповідей
Посилання