65.9K
CodeProject 正在变化。 阅读更多。
Home

Jatalog：Java 中的 Datalog 演绎数据库

Werner Stoop
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.33/5 (3投票s)

2016年7月27日

Apache

10分钟阅读

viewsIcon

13468

downloadIcon

148

Java实现的Datalog，它是Prolog编程语言的一个子集，用作演绎数据库的查询语言

Screenshot of a REPL session

引言

Datalog是Prolog编程语言的一个子集，用作演绎数据库的查询语言[wiki]。

Jatalog是Java实现的Datalog。它提供了语言的解析器和一个执行查询的评估引擎，这些查询可以嵌入到更大的应用程序中。

简而言之

  • 引擎实现了半朴素的自底向上评估。
  • 它实现了分层否定；技术上，它实现了分层Datalog¬语言[ceri]。
  • 它可以解析和评估文件和字符串中的Datalog程序（实际上是任何实现了java.io.Reader的对象）。
  • 它具有流畅的API，可以通过该API将其嵌入Java应用程序中以运行查询。
  • 它实现了“=”，“<>”（或“!=”），“<”，“<=”，“>”和“>=”作为内置谓词。
  • 它避免了第三方依赖。
  • 支持带有“带引号字符串”的值。
  • 使用~运算符撤销事实，例如p(q,r)~。
  • Shell类实现了一个REPL命令行界面。

背景

Datalog程序由事实和规则组成。事实描述关于世界的知识。规则描述事实之间的关系，从中可以推导出新的事实。

下面的Datalog程序描述了Alice是Bob的父母，Bob是Carol的父母，然后提供了从事实中推导出祖先关系的规则：[wiki]

% Facts:
parent(alice, bob).
parent(bob, carol).

% Rules:
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- ancestor(X, Z), parent(Z, Y).

Datalog中的变量是大写的。在示例中，X、Y和Z是变量，而alice和bob是常量。事实不能包含变量——它们被称为已完成。

事实的集合称为外延数据库（EDB）。

在事实parent(alice, bob)中，parent称为谓词，而alice和bob是项。项的数量称为元数。parent的元数是2，有些文献会写成parent/2。期望所有具有相同谓词的事实都具有相同的元数。

在示例中，这两个事实

  • parent(alice, bob)读作“alice是bob的父母”
  • parent(bob, carol)读作“bob是carol的父母”

规则的集合称为内涵数据库（IDB）。规则由一个头和一个体组成，用:-符号分隔。规则的头描述了一个可以推导出的新事实，而规则的体描述了如何推导出该事实。

在规则ancestor(X, Y) :- parent(X, Y)中，ancestor(X, Y)是头，parent(X, Y)是体。它规定，如果事实“X是Y的父母”为真，则可以推导出“X是Y的祖先”的事实。

也说规则的体蕴含头，因此parent(X, Y)蕴含ancestor(X, Y)。

Datalog引擎将在执行查询时使用此规则来确定“alice是bob的祖先”和“bob是carol的祖先”。

第二个规则ancestor(X, Y) :- ancestor(X, Z), parent(Z, Y)表示，“X是Y的祖先”这一事实也可以通过存在一个Z使得“X是Z的祖先”并且“Z是Y的父母”来推导。

利用这个规则，Datalog引擎将在查询评估期间已推导出的所有其他事实中确定“alice是carol的祖先”。

一旦事实和规则被输入系统，就可以对数据库运行查询。

  • ancestor(X, carol)?查询“谁是carol的祖先？”
  • ancestor(alice, Y)?查询“alice是Y的祖先？”
  • ancestor(alice, carol)?询问“alice是carol的祖先吗？”

答案是以变量名到满足查询的值的映射集合的形式出现的。例如，查询ancestor(X, carol)?的结果将是{X: alice}和{X: bob}。

Jatalog实现了几个内置谓词，可以在规则和查询中使用：等于“=”，不等于“<>”，大于“>”，大于等于“>=”，小于“<”和小于等于“<=”。

您可以在查询中有多个子句，用逗号分隔。例如sibling(A, B), A <> alice?询问“A的兄弟姐妹是谁，其中A不是alice？”

此外，Jatalog的语法使用~符号从数据库中撤销事实。例如，语句planet(pluto)~将撤销pluto是planet的事实。该语法改编自[rack]，但尚不清楚其他Datalog实现是否使用它。

撤销查询可以包含变量和多个子句：语句thing(N, X), X > 5~将删除数据库中所有X大于5的thing。

Using the Code

如果您想使用Java API，只需将编译后的JAR添加到类路径中。

JAR清单中的Main-Class指向za.co.wstoop.jatalog.Shell，它实现了REPL接口。要启动解释器，只需使用Java的-jar命令行选项运行JAR文件，如下所示

java -jar target/jatalog-0.0.1-SNAPSHOT.jar [filename]

除了Datalog语言的解释器外，Jatalog还提供了一个API，通过该API可以在Java程序中直接访问和查询数据库。

以下是如何使用流畅API编写上面示例中的事实和规则的示例

Jatalog jatalog = new Jatalog();

jatalog.fact("parent", "alice", "bob")
    .fact("parent", "bob", "carol");

jatalog.rule(Expr.expr("ancestor", "X", "Y"), 
    Expr.expr("parent", "X", "Z"), Expr.expr("ancestor", "Z", "Y"))
    .rule(Expr.expr("ancestor", "X", "Y"), Expr.expr("parent", "X", "Y"));

然后可以如下执行查询

Collection<Map<String, String>> answers;
answers = jatalog.query(Expr.expr("ancestor", "X", "carol"));

answers集合将包含满足查询的所有变量映射的列表。

{X: alice}
{X: bob}

上一个示例中的查询也可以这样编写

answers = jatalog.executeAll("ancestor(X, carol)?");

Jatalog还提供了一个Jatalog.prepareStatement()方法，该方法会将字符串解析为Statement对象，这些对象可以稍后执行。Statement.execute()方法接受一个Map<String, String>作为变量绑定参数，以便用于批量插入或查询。例如

Statement statement = Jatalog.prepareStatement("sibling(Me, You)?");
Map<String, String> bindings = Jatalog.makeBindings("Me", "bob");
Collection<Map<String, String>> answers;
answers = statement.execute(jatalog, bindings);

在上面的示例中，变量Me被绑定到值bob，因此statement.execute(...)行等效于执行查询sibling(bob, You)?。

Javadoc文档包含更多信息，并且src/test目录中的单元测试包含更多示例。

使用Maven编译

构建Jatalog的首选方法是通过Maven。

# Compile like so:
mvn package

# Generate Javadocs
mvn javadoc:javadoc

# Run like so:
java -jar target/jatalog-0.0.1-SNAPSHOT.jar file.dl

其中file.dl是包含要执行的Datalog命令的文件名。如果省略，解释器将进入交互模式，从System.in读取命令。

使用Ant编译

还提供了一个Ant build.xml文件。

# Compile like so:
ant 

# Generate Javadocs
ant docs

# Run like so:
java -jar dist/jatalog-0.0.1.jar

关注点

Jatalog的评估引擎是自底向上、半朴素且带有分层否定的。更多细节请参阅[ceri]。

自底向上意味着评估器将从EDB中的所有已知事实开始，并使用规则推导出新事实。它将重复此过程，直到无法推导出更多新事实。然后，它将匹配所有事实与查询的目标，以确定答案。（另一种方法是自顶向下，评估器从一系列目标开始，并使用数据库中的规则和事实来证明这些目标。）

半朴素是Datalog引擎的一种优化，其中评估器只会考虑在上一轮迭代中推导出的事实可能受影响的规则子集，而不是IDB中的所有规则。

分层否定意味着规则的评估顺序安排得当，使得否定的目标能够推导出有意义的事实。

例如，考虑规则p(X) :- q(X), not r(X).，其中EDB中存在事实q(a)，但不存在r(a)，并且假设数据库中还有其他规则可以推导出p(X)和r(X)。如果引擎以朴素的方式评估这些规则，那么它将在初始迭代中推导出事实p(a)。随后，事实r(a)可能在后续迭代中被推导出来，导致事实p(a)和r(a)相互矛盾。

分层否定会以一种顺序评估规则，以便在可以推导出任何p(X)事实之前推导出所有r(X)事实，从而消除此类矛盾。

分层否定对Jatalog中否定表达式的使用施加了额外的约束，引擎会对此进行检查。

以上是文献中描述的众所周知的优化和评估技术。有关良好概述，请参阅[ceri]。Jatalog还在可行的地方实现了一些其他次要优化。

  • StackMap类提供了一个Map实现，该实现具有对父Map的引用。Jatalog的大部分内部实现都围绕在Engine.matchGoals()方法中查找递归调用中的变量绑定。拥有StackMap消除了在每次递归调用matchGoals()时将现有变量绑定复制到新Map的需要。
  • IndexedSet类是一个Set实现，其中存储的元素可以根据某个键进行索引以快速查找。Jatalog实现使用它按谓词对事实进行分组，并快速找到这些事实。当它已经知道正在查找的谓词时，它会避免遍历整个EDB。
  • Jatalog还会在开始自底向上扩展数据库之前过滤掉不相关的事实。例如，如果查询是关于ancestor谓词，那么自底向上扩展就不需要扩展与employed相关的规则。这是通过Engine类中的getRelevantPredicates()方法中类似于半朴素评估的机制完成的。

有一些机会可以使用Java 8 Streams API并行运行某些方法（我特别考虑的是expandDatabase()中的expandStrata()调用以及expandStrata()中的matchRule()调用）。这比我想象的要复杂一些，所以目前我不太担心实现它。

我目前决定不使用算术内置谓词，例如plus(X,Y,Z) => X + Y = Z，因为它们并不那么简单。一旦输入变量（在此示例中为X和Y）可用，就应立即评估它们，以便可以计算Z并将其绑定给剩余的目标。这将需要一个更复杂的解析器，并且Expr对象需要表示抽象语法树。

概念上可以将Expr的List<String> terms改为List<Object>，这样就可以在数据库中存储复杂的Java对象（作为POJO）。如果您只使用解释器，那么这个功能用处不大，但如果您使用流畅API，它可能是一个附加功能。不过，我目前不打算实现它。

参考文献

  1. [wiki] Wikipedia话题，http://en.wikipedia.org/wiki/Datalog
  2. [elma] 数据库系统基础（第3版）；Ramez Elmasri，Shamkant Navathe
  3. [ceri] 你想知道的关于Datalog的一切（而不敢问）；Stefano Ceri，Georg Gottlob，Letizia Tanca
  4. [bra1] 演绎数据库和逻辑编程；Stefan Brass，Halle大学，2009 http://dbs.informatik.uni-halle.de/Lehre/LP09/c6_botup.pdf
  5. [banc] 递归查询处理策略的业余介绍；Francois Bancilhon，Raghu Ramakrishnan
  6. [mixu] mixu/datalog.js；Mikito Takada，https://github.com/mixu/datalog.js
  7. [kett] bottom-up-datalog-js；Frederic Kettelhoit http://fkettelhoit.github.io/bottom-up-datalog-js/docs/dl.html
  8. [davi] Datalog中的推理；Ernest Davis，http://cs.nyu.edu/faculty/davise/ai/datalog.html
  9. [gree] Datalog和递归查询处理；Todd J. Green，Shan Shan Huang，Boon Thau Loo和Wenchao Zhou，数据库基础与趋势，第5卷，第2期（2012）105-195，2013 http://blogs.evergreen.edu/sosw/files/2014/04/Green-Vol5-DBS-017.pdf
  10. [bra2] 扩展演绎数据库中的自底向上查询评估，Stefan Brass，1996 https://www.deutsche-digitale-bibliothek.de/binary/4ENXEC32EMXHKP7IRB6OKPBWSGJV5JMJ/full/1.pdf
  11. [sund] Datalog评估算法，Raj Sunderraman博士，1998 http://tinman.cs.gsu.edu/~raj/8710/f98/alg.html
  12. [ull1] 讲义：Datalog规则程序否定；Jeffrey D. Ullman；http://infolab.stanford.edu/~ullman/cs345notes/cs345-1.ppt
  13. [ull2] 讲义：Datalog逻辑规则递归；Jeffrey D. Ullman；http://infolab.stanford.edu/~ullman/dscb/pslides/dlog.ppt
  14. [meye] Python中的Prolog，Chris Meyers，http://www.openbookproject.net/py4fun/prolog/intro.html
  15. [alec] G53RDB关系数据库理论讲座14；Natasha Alechina；http://www.cs.nott.ac.uk/~psznza/G53RDB07/rdb14.pdf
  16. [rack] Datalog：演绎数据库编程，Jay McCarthy，https://docs.racket-lang.org/datalog/（Racket语言的Datalog库）

历史

版本 0.9

  • 这是公开发布的初始版本。

为方便起见，源代码也存储在https://github.com/wernsey/Jatalog。

Jatalog：Java中的Datalog演绎数据库 - CodeProject - 代码之家
© . All rights reserved.