Datalog是一种基于Prolog的逻辑编程语言，近年来人们对Prolog的兴趣有所回升。特别是，最近的几种授权方法（确定谁可以做什么）使用数据日志作为访问控制决策的逻辑基础。从表面上看，这似乎是一个完美的适合，有很多建议。自从2003年我开始攻读博士学位时第一次接触到Datalog以来，我本人就是Datalog的粉丝，甚至写过倡导Datalog的论文。然而，尽管我认为它有很多好处，但我认为它的一些复杂结果令人困惑，这意味着它并不总是像你可能会相信的那样适合。
Datalog是Prolog的一个清理版本，由数据库社区创建，试图将逻辑编程技术与关系数据库结合起来，创建演绎数据库。我非常尊重数据库社区，当他们对某个主题感兴趣时，他们提出的解决方案几乎总是值得关注的。（另请参见对SQL的注入攻击，他们通过参数化查询巧妙地解决了这一问题——web浏览器仍然未能令人信服地解决这一问题）。在本例中，Datalog以几种方式改进了Prolog，使其成为一种有用的数据库查询语言：
删除所有非逻辑运算符，例如可怕的“cut”和I/O“谓词”，它们破坏了Prolog的逻辑纯度。
放弃Prolog自上而下的回溯执行策略，即程序中规则的顺序（或规则中的条件）可以极大地改变查询的正确性、性能甚至终止。在数据日志中，无论规则以何种顺序出现，程序的意义和效率都是相同的。
Datalog允许您编写良好的逻辑规则，例如以下经典的祖先定义，即父关系的传递闭包：
如果您不熟悉Prolog语法，那么这意味着如果某人是他们的父母（第一条规则），或者如果某人是他们祖先的其他人的父母，那么某人就是他们的祖先。这是一个非常基本（而且枯燥）的例子，没有多少人需要祖传的访问控制，但它有望让您了解数据日志在简洁地表达对象之间关系方面的强大功能。
基于规则的声明式授权方法很有吸引力，因为它们允许您将此类规则与应用程序的业务逻辑巧妙地分开（至少人们希望如此）。数据日志是实现这一点的一种特别好的方法，因为规则非常具有表现力和简洁性，还因为它提供了一些有用的功能。例如，假设我们定义了一组规则来确定特定用户是否应该访问特定资源：
允许（操作、资源、用户）如果…%示例-允许用户更新他们拥有的任何资源：允许（更新、资源、用户）如果所有者（资源、用户）。
我们可以调用它来检查是否应该允许特定的请求-allow（update，“/users/alice”，bob）？-但我们也可以询问更一般的查询，例如：哪个用户可以更新Alice的个人资料：允许（update，“/users/Alice”，user）？在这里，带大写字母的用户是一个变量，解释器将告诉我们该变量（所有用户）的所有可能实例化，即谁可以更新该资源。同样，我们可以查询相同的规则，以查看Bob可以访问的所有资源，以及他可以对这些资源执行的所有操作。当你想查看谁有权访问什么时，这些是授权系统中非常有用的功能。
数据日志中最容易被误解的部分之一是它的时间复杂性：随着查询“大小”的增长，回答查询需要多长时间。您经常会看到数据日志查询保证在“多项式时间”（而不是指数时间）内终止的语句。这是真的，但只有在狭义上才能理解。
首先，我们要问“多项式在什么变量中？”当我们谈论具有多项式时间复杂性的数据日志时，我们指的是它的数据复杂性。也就是说，如果我们修复了一个给定的程序（一组规则），那么随着事实数据库的增加，回答查询所需的时间会发生怎样的变化？在SQL术语中，考虑程序是我们的SQL查询（或视图），并且我们询问查询在我们的表变大时运行多长时间。这是大多数人在谈论数据库时关心的主要复杂性度量，实际上，在这种情况下，数据日志具有多项式时间复杂性。
但这是授权复杂性的适当衡量标准吗？在这种情况下，我认为情况几乎完全相反。在典型的授权场景中，数据的大小基本上是固定的：被访问的特定资源是已知的，用户已经通过身份验证被识别，因此我们不需要查看整个数据表。另一方面，在做出决策时，可能需要考虑大量授权规则。因此，数据的大小是固定的，但规则的数量是可变的。在这种情况下，适当的复杂性度量称为程序复杂性，坏消息是D atalog具有指数级的程序复杂性！
我们需要考虑的另一个因素是DATALOG的多项式数据复杂度是基于最基本的形式，它不具有函数符号（如列表之类的数据类型）或算术。一旦你开始添加这样的特性（几乎所有现实世界的数据日志都会这样做），数据的复杂性不可避免地会增加。
数据日志的指数级程序复杂性是众所周知的，它并没有逃脱学术界对数据日志的授权处理。这方面的一篇有影响力的论文是“DATACORE与约束：信任管理语言的基础”，这已经被饼干开发者所引用。本文展示了如何通过扩展数据日志来构建强大的授权逻辑。但他们在那篇论文中构建的实际授权系统是基于一个名为RT的系统，它比数据日志更接近描述逻辑。然后，他们将这种更受限制的语言（具有多项式程序复杂性）转换为他们的数据日志变体，这也是一些描述逻辑推理者所做的。
描述逻辑共享数据日志的一些良好特性，并且对具有一系列时间复杂性的描述逻辑变体进行了大量研究。如果你对授权的逻辑方法感兴趣的话，这当然是另一种形式主义。
在另一个极端，我们现在看到了谷歌桑给巴尔（Google Zanzibar）这样的方法，它显然可以扩展到数万亿个ACL条目，并使用一种非常简单的语言来定义角色之间的关系（例如，文档的所有编辑也都是查看者）。同样，在我看来，这看起来像是一个（非常有限的）描述逻辑，尽管它有一个非常大规模的实现！
另一方面，描述逻辑（can）比数据日志具有更好的最坏情况时间复杂度这一同样的推理促使我将我的博士论文建立在它们之上，这是我经常后悔的决定。对于那些更严格的复杂度界限，取舍是一种表达能力要低得多的语言，我经常遇到一些概念，这些概念在描述逻辑中很难或不可能表达，但在数据日志中很简单。（也有更具表现力的描述逻辑，但我仍然发现它们很难使用）。
最终，我认为基于逻辑的方法来定义授权策略是一个很好的想法。作为这种方法的一个例子，数据日志仍然是一个很好的选择。但我不会说它在这方面是唯一有效的。在实践中，应用于数据日志的一些扩展将其推向了一个完整的Prolog，如果其中一些扩展意外地图灵完成，我也不会感到惊讶。这并不是一件坏事：纯Prolog（不带粗枝大叶）也是一种优秀的语言，如果你不接受用户定义的策略，那么你可以避免病态的性能案例。
另一方面，如果你想用非常简单的规则扩展到大量的实体，那么在我看来，一些轻量级的描述逻辑方言非常适合。只是要注意表达能力的权衡。那里有一棵巨大的逻辑树，不需要只挂在一个分支上。