Datalog

# Datalog 源代码：https://www.philipzucker.com/notes/Languages/datalog/ - 什么是 Datalog？（https://www.philipzucker.com/notes/Languages/datalog/#what-is-datalog） - 能用 Datalog 做什么？（https://www.philipzucker.com/notes/Languages/datalog/#what-can-you-do-with-datalog） - 入门指南（https://www.philipzucker.com/notes/Languages/datalog/#getting-started） - 路径可达性（https://www.philipzucker.com/notes/Languages/datalog/#path-reachability） - Python（https://www.philipzucker.com/notes/Languages/datalog/#python） - 朴素方法（https://www.philipzucker.com/notes/Languages/datalog/#naive） - 半朴素方法（https://www.philipzucker.com/notes/Languages/datalog/#semi-naive） - 索引（https://www.philipzucker.com/notes/Languages/datalog/#indexing） - 格（https://www.philipzucker.com/notes/Languages/datalog/#lattice） - SQL 递归公用表子表达式（https://www.philipzucker.com/notes/Languages/datalog/#sql-recursive-common-table-subexpressions） - 朴素 SQL 翻译（https://www.philipzucker.com/notes/Languages/datalog/#naive-sql-translation） - 半朴素（https://www.philipzucker.com/notes/Languages/datalog/#seminaive） - 格（https://www.philipzucker.com/notes/Languages/datalog/#lattices） - Ocaml（https://www.philipzucker.com/notes/Languages/datalog/#ocaml） - 朴素方法（https://www.philipzucker.com/notes/Languages/datalog/#naive-1） - Rust（https://www.philipzucker.com/notes/Languages/datalog/#rust） - Magic Set（https://www.philipzucker.com/notes/Languages/datalog/#magic-set） - 程序分析（https://www.philipzucker.com/notes/Languages/datalog/#program-analysis） - 评估（https://www.philipzucker.com/notes/Languages/datalog/#evaluation） - 常量传播（https://www.philipzucker.com/notes/Languages/datalog/#constant-propagation） - 符号求值（https://www.philipzucker.com/notes/Languages/datalog/#symbolic-evaluation） - 到达定义（https://www.philipzucker.com/notes/Languages/datalog/#reaching-definitions） - 活跃性（https://www.philipzucker.com/notes/Languages/datalog/#liveness） - 指向分析（https://www.philipzucker.com/notes/Languages/datalog/#points-to） - 可用表达式（https://www.philipzucker.com/notes/Languages/datalog/#available-expressions） - 交集（https://www.philipzucker.com/notes/Languages/datalog/#intersection） - 非常繁忙表达式（https://www.philipzucker.com/notes/Languages/datalog/#very-busy-expressions） - 程序点的 Zippers（https://www.philipzucker.com/notes/Languages/datalog/#zippers-for-program-points） - 支配者（https://www.philipzucker.com/notes/Languages/datalog/#dominators） - Forall 模拟（https://www.philipzucker.com/notes/Languages/datalog/#forall-emulation） - Doop（https://www.philipzucker.com/notes/Languages/datalog/#doop） - Datalog 反汇编/反编译器（https://www.philipzucker.com/notes/Languages/datalog/#datalog-diassembly--decompilers） - Bap（https://www.philipzucker.com/notes/Languages/datalog/#bap） - 资源（https://www.philipzucker.com/notes/Languages/datalog/#resources） - 一流集合与反射（https://www.philipzucker.com/notes/Languages/datalog/#first-class-sets--reflection） - 位集合（https://www.philipzucker.com/notes/Languages/datalog/#bitsets） - 位集合反射（https://www.philipzucker.com/notes/Languages/datalog/#bitset-reflection） - 排序列表（https://www.philipzucker.com/notes/Languages/datalog/#sort-lists） - Patricia Trie（https://www.philipzucker.com/notes/Languages/datalog/#patricia-tries） - BDD（https://www.philipzucker.com/notes/Languages/datalog/#bdds） - 调用（https://www.philipzucker.com/notes/Languages/datalog/#call） - 元循环解释器（https://www.philipzucker.com/notes/Languages/datalog/#meta-circular-interpreter） - BogoSort（https://www.philipzucker.com/notes/Languages/datalog/#bogosort） - 翻译函数式程序（https://www.philipzucker.com/notes/Languages/datalog/#translating-functional-programs） - 列表（https://www.philipzucker.com/notes/Languages/datalog/#lists） - 动态规划（https://www.philipzucker.com/notes/Languages/datalog/#dynamic-programming） - Q 学习（https://www.philipzucker.com/notes/Languages/datalog/#q-learning） - Mandelbrot（https://www.philipzucker.com/notes/Languages/datalog/#mandelbrot） - 球与弹簧（https://www.philipzucker.com/notes/Languages/datalog/#ball-and-springs） - 数独（https://www.philipzucker.com/notes/Languages/datalog/#sudoku） - 约束处理规则 (CHR)（https://www.philipzucker.com/notes/Languages/datalog/#constraint-handling-rules-chr） - 反向传播（https://www.philipzucker.com/notes/Languages/datalog/#backprop） - Lambda 表示（https://www.philipzucker.com/notes/Languages/datalog/#lambda-representation） - 解析（https://www.philipzucker.com/notes/Languages/datalog/#parsing） - Hilog（https://www.philipzucker.com/notes/Languages/datalog/#hilog） - 相等饱和（https://www.philipzucker.com/notes/Languages/datalog/#equality-saturation） - 项重写（https://www.philipzucker.com/notes/Languages/datalog/#term-rewriting） - Datalog modulo 项重写（https://www.philipzucker.com/notes/Languages/datalog/#datalog-modulo-term-rewriting） - 图重写（https://www.philipzucker.com/notes/Languages/datalog/#graph-rewriting） - 图算法（https://www.philipzucker.com/notes/Languages/datalog/#graph-algorithms） - 可达性（https://www.philipzucker.com/notes/Languages/datalog/#reachability） - 最短路径（https://www.philipzucker.com/notes/Languages/datalog/#shortest-path） - 生成树（https://www.philipzucker.com/notes/Languages/datalog/#spanning-tree） - 团（https://www.philipzucker.com/notes/Languages/datalog/#clique） - 环（https://www.philipzucker.com/notes/Languages/datalog/#cycle） - 子图匹配（https://www.philipzucker.com/notes/Languages/datalog/#subgraph-matching） - 着色（https://www.philipzucker.com/notes/Languages/datalog/#coloring） - 传播器（https://www.philipzucker.com/notes/Languages/datalog/#propagators） - 布尔约束传播（https://www.philipzucker.com/notes/Languages/datalog/#boolean-constraint-propagation） - 差分逻辑（https://www.philipzucker.com/notes/Languages/datalog/#difference-logic） - 有限域（https://www.philipzucker.com/notes/Languages/datalog/#finite-domain） - 宏（https://www.philipzucker.com/notes/Languages/datalog/#macros） - define ORBODY(h,b1,b2) CLAUSE(h, b1) CLAUSE(h, b2)（https://www.philipzucker.com/notes/Languages/datalog/#define-orbodyhb1b2-clauseh-b1-clauseh-b2） - define ORHEAD(h1,h2,b) CLAUSE(h1,b) CLAUSE(h2,b)（https://www.philipzucker.com/notes/Languages/datalog/#define-orheadh1h2b-clauseh1b-clauseh2b） - define IMPLBODY(h, b1, b1) CLAUSE( h, (b1, b2) )（https://www.philipzucker.com/notes/Languages/datalog/#define-implbodyh-b1-b1-clause-h-b1-b2-） - define IMPLHEAD()（https://www.philipzucker.com/notes/Languages/datalog/#define-implhead） - 模拟 Prolog（https://www.philipzucker.com/notes/Languages/datalog/#emulating-prolog） - 需要集合（https://www.philipzucker.com/notes/Languages/datalog/#need-sets） - Magic Set（https://www.philipzucker.com/notes/Languages/datalog/#magic-set-1） - 一流并查集（https://www.philipzucker.com/notes/Languages/datalog/#first-class-union-find） - 翻译命令式程序（https://www.philipzucker.com/notes/Languages/datalog/#translating-imperative-programs） - 迭代（https://www.philipzucker.com/notes/Languages/datalog/#iteration） - 模型检查（https://www.philipzucker.com/notes/Languages/datalog/#model-checking） - 时间戳（https://www.philipzucker.com/notes/Languages/datalog/#timestamping） - 定理证明（https://www.philipzucker.com/notes/Languages/datalog/#theorem-proving） - 存在量词头的 Skolem 化（https://www.philipzucker.com/notes/Languages/datalog/#skolemization-for-existential-heads） - 目标/查询（https://www.philipzucker.com/notes/Languages/datalog/#goals--queries） - 去柯里化（https://www.philipzucker.com/notes/Languages/datalog/#uncurrying） - 上下文 Datalog / 假设 Datalog（https://www.philipzucker.com/notes/Languages/datalog/#contextual-datalog--hypothetical-datalog） - 高阶子句 (Harrop)（https://www.philipzucker.com/notes/Languages/datalog/#higher-order-clauses-harrop） - 栈数据库 / Harrop Datalog / 试探性 Datalog（https://www.philipzucker.com/notes/Languages/datalog/#stack-database--harrop-datalog--tentative-datalog） - 存在查询（https://www.philipzucker.com/notes/Languages/datalog/#existenial-queries） - 全称量词（https://www.philipzucker.com/notes/Languages/datalog/#universal-quantifier） - 几何（https://www.philipzucker.com/notes/Languages/datalog/#geometry） - 范畴示例（https://www.philipzucker.com/notes/Languages/datalog/#categorical-example） - 类型类解析（https://www.philipzucker.com/notes/Languages/datalog/#typeclass-resolution） - 借用检查器（https://www.philipzucker.com/notes/Languages/datalog/#borrow-checker） - 类型检查（https://www.philipzucker.com/notes/Languages/datalog/#type-checking） - 余归纳或最大不动点 Datalog（https://www.philipzucker.com/notes/Languages/datalog/#coinductive-or-greatest-fixed-point-datalog） - DFA 最小化（https://www.philipzucker.com/notes/Languages/datalog/#dfa-minimization） - CRDT（https://www.philipzucker.com/notes/Languages/datalog/#crdts） - 多重集语义（https://www.philipzucker.com/notes/Languages/datalog/#multiset-semantics） - 访问控制策略（https://www.philipzucker.com/notes/Languages/datalog/#access-control-policies） - 网络（https://www.philipzucker.com/notes/Languages/datalog/#networks） - Make（https://www.philipzucker.com/notes/Languages/datalog/#make） - 主题（https://www.philipzucker.com/notes/Languages/datalog/#topics） - 回答集编程（https://www.philipzucker.com/notes/Languages/datalog/#answer-set-programmng） - 溯源（https://www.philipzucker.com/notes/Languages/datalog/#provenance） - 半朴素求值（https://www.philipzucker.com/notes/Languages/datalog/#semi-naive-evaluation） - 代数数据类型（https://www.philipzucker.com/notes/Languages/datalog/#algebraic-data-types） - 格（https://www.philipzucker.com/notes/Languages/datalog/#lattices-1） - 包含（https://www.philipzucker.com/notes/Languages/datalog/#subsumption） - 包含作为主特性（https://www.philipzucker.com/notes/Languages/datalog/#subsumption-as-a-master-feature） - 溯源（https://www.philipzucker.com/notes/Languages/datalog/#provenance-1） - max min（https://www.philipzucker.com/notes/Languages/datalog/#max-min） - 递归求和与计数（https://www.philipzucker.com/notes/Languages/datalog/#recurusive-sum-and-count） - 格（https://www.philipzucker.com/notes/Languages/datalog/#lattices-2） - 最小/最大格（https://www.philipzucker.com/notes/Languages/datalog/#minmax-lattice） - Maybe/Option 格（https://www.philipzucker.com/notes/Languages/datalog/#maybeoption-lattice） - 区间（https://www.philipzucker.com/notes/Languages/datalog/#intervals） - 加宽（https://www.philipzucker.com/notes/Languages/datalog/#widening） - 二元格（https://www.philipzucker.com/notes/Languages/datalog/#dyadic-lattice） - 等价关系（https://www.philipzucker.com/notes/Languages/datalog/#equivalence-relations） - 否定（https://www.philipzucker.com/notes/Languages/datalog/#negation） - 选择域（https://www.philipzucker.com/notes/Languages/datalog/#choice-domain） - 半环语义（https://www.philipzucker.com/notes/Languages/datalog/#semiring-semantics） - 概率（https://www.philipzucker.com/notes/Languages/datalog/#probability） - Datalog\+\- 与 chase（https://www.philipzucker.com/notes/Languages/datalog/#datalog--and-the-chase） - 制表（https://www.philipzucker.com/notes/Languages/datalog/#tabling） - 描述复杂度与最小不动点逻辑（https://www.philipzucker.com/notes/Languages/datalog/#descriptive-complexity-and-least-fixed-point-logic） - 推送式 Datalog（https://www.philipzucker.com/notes/Languages/datalog/#push-based-datalog） - 增量/差分 Datalog（https://www.philipzucker.com/notes/Languages/datalog/#incremental--differential-datalog） - Datalog 的回溯（https://www.philipzucker.com/notes/Languages/datalog/#backtracking-a-datalog） - 实现（https://www.philipzucker.com/notes/Languages/datalog/#implementations） - Rel（https://www.philipzucker.com/notes/Languages/datalog/#rel） - DDlog（https://www.philipzucker.com/notes/Languages/datalog/#ddlog） - IncA（https://www.philipzucker.com/notes/Languages/datalog/#inca） - Formulog（https://www.philipzucker.com/notes/Languages/datalog/#formulog） - Datafrog（https://www.philipzucker.com/notes/Languages/datalog/#datafrog） - Ascent（https://www.philipzucker.com/notes/Languages/datalog/#ascent） - Flix（https://www.philipzucker.com/notes/Languages/datalog/#flix） - dr lojekyl（https://www.philipzucker.com/notes/Languages/datalog/#dr-lojekyl） - Datafun（https://www.philipzucker.com/notes/Languages/datalog/#datafun） - QL（https://www.philipzucker.com/notes/Languages/datalog/#ql） - Souffle（https://www.philipzucker.com/notes/Languages/datalog/#souffle） - 内置函子（https://www.philipzucker.com/notes/Languages/datalog/#intrinsic-functors） - 浮点数（https://www.philipzucker.com/notes/Languages/datalog/#floats） - Souffle 证明（https://www.philipzucker.com/notes/Languages/datalog/#souffle-proofs） - 聚合（https://www.philipzucker.com/notes/Languages/datalog/#aggregates） - 用户定义函子（https://www.philipzucker.com/notes/Languages/datalog/#user-defined-functors） - ADT（https://www.philipzucker.com/notes/Languages/datalog/#adts） - 上下文为王（https://www.philipzucker.com/notes/Languages/datalog/#contexts-are-king） - 字段访问器（https://www.philipzucker.com/notes/Languages/datalog/#field-accessors） - 向量（https://www.philipzucker.com/notes/Languages/datalog/#vectors） - 使用 ADT 替代 autoinc()（https://www.philipzucker.com/notes/Languages/datalog/#use-adt-instead-of-autoinc） - 记录打包（https://www.philipzucker.com/notes/Languages/datalog/#record-packing） - 宏（https://www.philipzucker.com/notes/Languages/datalog/#macros-1） - 组件（https://www.philipzucker.com/notes/Languages/datalog/#components） - 选择域（https://www.philipzucker.com/notes/Languages/datalog/#choice-domain-1） - 否定（https://www.philipzucker.com/notes/Languages/datalog/#negation-1） - Souffle 源代码（https://www.philipzucker.com/notes/Languages/datalog/#souffle-source） - EPR datalog（https://www.philipzucker.com/notes/Languages/datalog/#epr-datalog） - 资源（https://www.philipzucker.com/notes/Languages/datalog/#resources-1） - include prelude.ml（https://www.philipzucker.com/notes/Languages/datalog/#include-preludeml） - class(slotname : f(x,y) , ) :-（https://www.philipzucker.com/notes/Languages/datalog/#classslotname--fxy----） - 构建 Souffle emscripten（https://www.philipzucker.com/notes/Languages/datalog/#building-souffle-emscripten） 另请参阅关于以下主题的笔记： - Prolog - 回答集编程 ## 什么是 Datalog？ Datalog 是多面的，这正是它如此酷的部分原因。从一个角度来看，它是一种数据库语言，是 SQL 的一种更简洁的竞品。它具有递归特性，使得表达图和网络查询变得容易，而在 SQL 中你可能需要借助递归公用表子表达式和/或触发器才能解决这类问题。与 SQL 相比，它也在某些方面受到限制。SQL 允许一些命令式命令（如 `DELETE` 或 `UPDATE`），而 Datalog 通常设计成永久保留信息（单调性）。从另一个角度来看，它是逻辑编程语言 Prolog 的亲属，采用自底向上搜索而非自顶向下搜索。它从这一逻辑编程传统中继承了语言在操作语义和逻辑解读上的迷人二元性。