Введение
Декларативный язык логического программирования
Datalog — это декларативный язык логического программирования. Хотя синтаксически он является подмножеством Prolog, Datalog обычно использует модель вычислений снизу вверх, а не сверху вниз. Это различие приводит к значительно отличающемуся поведению и свойствам по сравнению с Prolog. Он часто используется как язык запросов для дедуктивных баз данных. Datalog находит применение в задачах интеграции данных, сетевого взаимодействия, анализа программ и других областях.
Семантика
Существует три широко используемых подхода к семантике программ Datalog: модель-теоретический, подход на основе фиксированной точки и доказательно-теоретический. Можно доказать, что эти три подхода эквивалентны. Атом называется *заземлённым* (ground), если ни один из его подтермов не является переменной. Интуитивно, каждая из семантик определяет смысл программы как множество всех заземлённых атомов, которые могут быть выведены из правил программы, исходя из фактов.
Теоретическая модель
Правило называется заземлённым, если все его атомы (голова и тело) заземлены. Заземлённое правило R1 является заземлённым экземпляром другого правила R2, если R1 является результатом подстановки констант вместо всех переменных в R2. База Гербранда программы Datalog – это множество всех заземлённых атомов, которые могут быть получены с использованием констант, встречающихся в программе. Наименьшее подмножество базы Гербранда программы Datalog, обладающее свойством, что для каждого заземлённого экземпляра каждого правила в программе, если атомы в теле правила находятся в этом подмножестве, то и голова также находится в нём. Семантика теории моделей определяет минимальную модель Гербранда как значение программы.
Фиксированная точка
Пусть I — степенное множество основания Гербранда программы P. Оператор немедленного следования для P — это отображение T из I в I, которое добавляет все новые атомарные факты, которые могут быть выведены из правил программы за один шаг. Семантика наименьшей неподвижной точки определяет наименьшую неподвижную точку T как значение программы; это совпадает с минимальной моделью Гербранда. Семантика неподвижных точек предлагает алгоритм для вычисления минимальной модели: начните с множества атомарных фактов в программе, затем многократно добавляйте следствия правил, пока не будет достигнута неподвижная точка. Этот алгоритм называется наивной оценкой.
Теоретическое доказательство
Семантика теории доказательств определяет смысл программы Datalog как множество фактов с соответствующими деревьями доказательств. Интуитивно, дерево доказательств показывает, как получить факт из фактов и правил программы. Может быть интересно узнать, содержится ли конкретный заземленный атом в минимальной модели Гербранда программы Datalog, возможно, не обращая особого внимания на остальную часть модели. Рассмотрение деревьев доказательств сверху вниз, описанных выше, позволяет предложить алгоритм для вычисления результатов таких запросов. Этот подход лежит в основе алгоритма SLD-разрешения, который является фундаментом для вычисления в Prolog.
Оценка
Существует множество различных способов оценки программы Datalog, каждый из которых обладает своими характеристиками производительности.
Стратегии оценки снизу вверх
Стратегии оценки снизу вверх начинаются с фактов в программе и многократно применяют правила, пока не будет достигнута какая-либо цель или запрос, либо пока не будет получена полная минимальная модель программы.
Наивная оценка
Наивная оценка отражает семантику неподвижной точки для программ Datalog. Наивная оценка использует множество "известных фактов", которое инициализируется фактами, содержащимися в программе. Она последовательно перебирает все заземлённые экземпляры каждого правила в программе. Если каждый атом в теле заземлённого экземпляра содержится в множестве известных фактов, то атом в голове добавляется в множество известных фактов. Этот процесс повторяется до достижения неподвижной точки, когда дальнейшие выводы невозможны. Наивная оценка вычисляет полную минимальную модель программы.
Полунавидная оценка
Полунаивная оценка — это стратегия вычисления снизу вверх, которая может быть асимптотически быстрее наивной оценки.
Стратегии оценки сверху вниз
Разрешение SLD является корректным и полным для программ Datalog.
Магические наборы
Стратегии оценки сверху вниз начинаются с запроса или цели. Стратегии оценки снизу вверх могут отвечать на запросы, вычисляя всю минимальную модель и сопоставляя запрос с ней, но это может быть неэффективно, если ответ зависит только от небольшого подмножества всей модели. Алгоритм "магических множеств" принимает программу на Datalog и запрос и генерирует более эффективную программу, вычисляющую тот же ответ на запрос, при этом используя оценку снизу вверх. Показано, что вариант алгоритма "магических множеств" генерирует программы, которые при полунаивной оценке оказываются столь же эффективными, как и оценка сверху вниз.
Расширения
Несколько расширений были внесены в Datalog, например, для поддержки отрицания, агрегатных функций, неравенств, объектно-ориентированного программирования или для разрешения дизъюнкций в качестве голов предложений. Эти расширения оказывают существенное влияние на семантику языка и на реализацию соответствующего интерпретатора. Datalog является синтаксическим подмножеством Prolog, дизъюнктивного Datalog, программирования на множествах ответов (answer set programming), DatalogZ и логического программирования с ограничениями. При оценке как программы на множествах ответов, программа Datalog выдает единственное множество ответов, которое точно соответствует ее минимальной модели. Многие реализации Datalog расширяют его дополнительными возможностями; подробности см. в соответствующей документации.
Выразительность
Datalog обобщает многие другие языки запросов. Например, конъюнктивные запросы и объединение конъюнктивных запросов могут быть выражены на Datalog. Datalog также может выражать запросы на поиск регулярных путей. Задача для Datalog заключается в следующем: для заданной программы Datalog, является ли она ограниченной по глубине рекурсии, то есть, может ли максимальная глубина рекурсии, достигаемая при вычислении программы на входной базе данных, быть ограничена некоторой константой. Иными словами, этот вопрос спрашивает, можно ли переписать программу Datalog в нерекурсивную программу Datalog или, что эквивалентно, как объединение конъюнктивных запросов. Решение задачи об ограниченности для произвольных программ Datalog неразрешимо, но становится разрешимым при ограничении рассмотрения некоторыми фрагментами Datalog.
Свободное программное обеспечение/открытый исходный код
Написано в названии Попробуйте онлайн Описание внешней базы данных Лицензия C XSB Логическое программирование и дедуктивная система баз данных для Unix и Microsoft Windows с таблированием, обеспечивающим завершение и эффективность, как в Datalog, включая инкрементальную оценку. C++ Coral Дедуктивная система баз данных, написанная на C++ с полунаивной оценкой Datalog. Разработана в 1988–1997 гг. DLV Расширение Datalog, поддерживающее дизъюнктивные головы предложений. Inter4QL – интерпретатор командной строки с открытым исходным кодом для языка запросов 4QL, похожего на Datalog, реализованный на C++ для Windows, Mac OS X и Linux. Отрицание разрешено в головах и телах правил, а также в рекурсии. v3 RDFox в памяти Высокопроизводительное хранилище RDF-троек с логическим выводом OWL и Datalog. Реализует алгоритм FBF для инкрементальной оценки, расширяя Datalog для включения стратифицированного отрицания и равенства. Способен работать в конфигурации высокой доступности. Soufflé Да файл, в памяти, sqlite3 Движок Datalog с открытым исходным кодом, имеющий компилятор, переводящий Datalog в высокопроизводительный, параллельный код C++, и высокопроизводительный интерпретатор; специально разработан для сложных запросов Datalog к большим наборам данных, встречающимся в контексте статического анализа программ. Clojure Cascalog Hadoop Библиотека Clojure для запроса данных, хранящихся в кластерах Hadoop. Clojure Datalog Библиотека, реализующая аспекты Datalog. XTDB (ранее Crux) Да Apache Kafka Универсальная база данных с "разъединенной" архитектурой, использующая потоковую передачу документов и транзакций для достижения значительной архитектурной гибкости и элегантного горизонтального масштабирования. Подключаемые компоненты включают Kafka, RocksDB и LMDB. Индексы по умолчанию являются битемпоральными для поддержки запросов Datalog в определенный момент времени. Предоставляются Java и HTTP API. Datascript в памяти Неизменяемая база данных и движок запросов Datalog, работающий в браузере. Datalevin LMDB Форк Datascript, оптимизированный для долговечного хранилища LMDB. Datahike файл, в памяти Форк Datascript с долговечным бэкендом, использующим дерево-автостоп. Naga/Asami файл, в памяти Комбинация графовой базы данных (Asami) и системы обработки правил (Naga), которая оценивает синтаксис Datalog и выполняет его с использованием базы данных. Работает в браузерах (в памяти), на JVM (в памяти/файлах) или нативно (в памяти/файлах). Erlang Datalog Библиотека предназначена для запроса и формализации отношений между n-арными потоками данных с использованием Datalog. Реализует ad-hoc движок запросов, использующий упрощенную версию парадигмы логического программирования. Библиотека облегчает разработку приложений для интеграции данных, обмена информацией и семантической сети. Go MangleMangle – язык программирования для дедуктивного программирования баз данных. Это расширение Datalog с различными расширениями, такими как агрегирование, вызовы функций и необязательная проверка типов. Haskell Dyna Dyna – декларативный язык программирования для статистического ИИ-программирования. Язык основан на Datalog, поддерживает как прямой, так и обратный вывод, а также инкрементальную оценку. Java AbcDatalog AbcDatalog – реализация с открытым исходным кодом логического языка программирования Datalog, написанная на Java. Он предоставляет готовые к использованию реализации общих алгоритмов оценки Datalog, а также некоторые экспериментальные многопоточные движки оценки. Он поддерживает языковые возможности, выходящие за рамки базового Datalog, такие как явная (дезунификация) термов и стратифицированное отрицание. Кроме того, AbcDatalog разработан для легкого расширения новыми движками оценки и новыми языковыми возможностями. IRIS IRIS расширяет Datalog символами функций, встроенными предикатами, локально стратифицированными или нестратифицированными логическими программами (с использованием хорошо обоснованной семантики), небезопасными правилами и типами данных XML-схемы. v2.1 Jena Semantic Web framework, включающий реализацию Datalog как часть своего универсального движка правил, обеспечивающего поддержку OWL и RDFS. SociaLite – вариант Datalog для анализа больших графов, разработанный в Стэнфорде. Graal Graal – инструментарий Java, предназначенный для запроса баз знаний в рамках экзистенциальных правил, также известных как Datalog+. Flix Да Функциональный и логический язык программирования, вдохновленный Datalog, расширенный пользовательскими решетками и монотонными фильтрами/функциями переноса. Lua Datalog – легковесная дедуктивная система баз данных. OCaml datalog Реализация Datalog для OCaml в памяти с алгоритмами прямого и обратного вывода. 2-предложный Prolog DES – реализация с открытым исходным кодом для обучения Datalog в курсах. Python pyDatalog 11 диалектов SQL добавляют логическое программирование в инструментарий Python. Он может выполнять логические запросы к базам данных или объектам Python и использовать логические предложения для определения поведения классов Python. Racket Datalog for Racket Datafun Обобщенный Datalog на полурешетках. Ruby bloom / bud Ruby DSL для программирования с конструкциями, ориентированными на данные, основанный на расширении Dedalus Datalog, которое добавляет временное измерение к логике. 3-предложный Rust Crepe Crepe – библиотека, позволяющая писать декларативные логические программы на Rust с синтаксисом, похожим на Datalog. Он предоставляет процедурный макрос, который генерирует эффективный и безопасный код и беспрепятственно взаимодействует с программами Rust. Он также поддерживает расширения, такие как стратифицированное отрицание, полунаивная оценка и вызов внешних функций в правилах Datalog. MIT License / Apache 2.0 Datafrog Datafrog – легковесный движок Datalog, предназначенный для встраивания в другие программы Rust. MIT License / Apache 2.0 TerminusDB в памяти TerminusDB – графовая база данных и хранилище документов с открытым исходным кодом. Предназначен для совместного создания приложений, интенсивно использующих данные, и графов знаний. DDlog DDlog – инкрементный, в памяти, типизированный движок Datalog. Он хорошо подходит для написания программ, которые инкрементно обновляют свой вывод в ответ на изменения входных данных. Программист DDlog определяет желаемое отображение вход-выход декларативным способом, используя диалект Datalog. Компилятор DDlog затем синтезирует эффективную инкрементную реализацию на Rust. DDlog основан на библиотеке дифференциального потока данных. Он предлагает привязки для Java, C и Go. Tcl tclbdd Реализация на основе диаграмм принятия решений. Создан для поддержки разработки оптимизирующего компилятора для Tcl. Другие или неизвестные языки bddbddb Реализация Datalog, выполненная в Стэнфордском университете. В основном используется для запроса байт-кода Java, включая анализ точек доступа в больших программах Java. Использует BDD внутренне. ConceptBase Дедуктивная и объектно-ориентированная система баз данных, основанная на оценщике запросов Datalog: Prolog для триггерных процедур и перезаписи, аксиоматизированный Datalog под названием «Telos» для (мета)моделирования. В основном используется для концептуального моделирования и метамоделирования. 2-предложный
Не свободное программное обеспечение
Datomic — это распределенная база данных, разработанная для создания масштабируемых, гибких и интеллектуальных приложений, работающих в новых облачных архитектурах. В качестве языка запросов используется Datalog. FoundationDB предоставляет бесплатную привязку к базе данных для pyDatalog с учебным пособием по ее использованию. Leapsight Semantic Dataspace (LSD) — это распределенная дедуктивная база данных, обеспечивающая высокую доступность, отказоустойчивость, простоту эксплуатации и масштабируемость. LSD использует Leaplog (реализацию Datalog) для запросов и логического вывода и была создана компанией Leapsight. LogicBlox — коммерческая реализация Datalog, используемая для веб-приложений в области планирования розничной торговли и страхования. Profium Sense — это графовая база данных, соответствующая стандарту RDF и написанная на Java. Она обеспечивает поддержку оценки Datalog для пользовательских правил. QL — коммерческий объектно-ориентированный вариант Datalog, разработанный Semmle для анализа исходного кода с целью выявления уязвимостей в системе безопасности. SecPAL — язык политик безопасности, разработанный Microsoft Research. Stardog — это графовая база данных, реализованная на Java. Она поддерживает RDF и все профили OWL 2, предоставляя широкие возможности логического вывода, включая оценку Datalog. StrixDB — коммерческое хранилище RDF-графов, совместимое со SPARQL, с Lua API и возможностями логического вывода Datalog. Может использоваться как модуль для httpd (Apache HTTP Server) или автономно (хотя бета-версии распространяются под лицензией Perl Artistic License 2.0).
Использование и влияние
Даталог достаточно ограничен в своей выразительности. Он не является машиной Тьюринга и не включает в себя базовые типы данных, такие как целые числа или строки. Эта лаконичность привлекательна с теоретической точки зрения, но это означает, что сам по себе Даталог редко используется в качестве языка программирования или языка представления знаний. Большинство движков Даталога реализуют существенные расширения Даталога. Однако Даталог оказывает сильное влияние на эти реализации, и многие авторы не считают нужным отличать их от Даталога, как он представлен в этой статье. Соответственно, в этом разделе обсуждаются приложения, использующие реалистичные реализации языков, основанных на Даталоге. Даталог находит применение в задачах интеграции данных, извлечения информации, сетевых технологий, безопасности, облачных вычислений и машинного обучения. Компания Google разработала расширение Даталога для обработки больших данных. Даталог применяется в статических программах анализа. Диалект Soufflé использовался для написания анализа указателей для Java и анализа потока управления для Scheme. Даталог был интегрирован с SMT-решателями, чтобы упростить написание определенных статических анализов. Диалект Flix также подходит для написания статических программных анализов. Некоторые широко используемые системы управления базами данных включают идеи и алгоритмы, разработанные для Даталога. Например, стандарт SQL:1999 включает рекурсивные запросы, а алгоритм Magic Sets (первоначально разработанный для более быстрой оценки запросов Даталога) реализован в IBM DB2.
История
Истоки Datalog уходят корнями в начало логического программирования, но он выделился в самостоятельную область примерно в 1977 году, когда Герве Галлер и Джек Минкер организовали семинар по логике и базам данных. Дэвиду Майеру приписывают создание термина Datalog.