Serde Datalog

Serde Datalog 提供了一个从 Serde 中实现的 Serializer 特性，用于从任何实现了 serde::Serializable 特性的数据结构中提取事实。在 Datalog 术语中，Serde Datalog 将数据结构序列化为 EDB。

Serde Datalog 有两个主要组件：一个用于生成数据结构事实的 提取器，以及一个将事实实体化为显式表示的 后端。您可以替换不同的后端实现来更改事实的表示。

示例

考虑以下实现了 Serialize 特性的枚举类型

#[derive(Serialize)]
enum Foo {
    A(Box<Foo>),
    B(i64)
}

然后考虑枚举实例 Foo::A(Foo::B(10))。提取器生成以下事实来表示此数据结构

• 元素 1 是一个新类型变体
• 元素 1 的类型是 Foo，变体名为 A
• 元素 1 的第一个字段引用元素 2
• 元素 2 是一个新类型变体
• 元素 2 的类型是 Foo，变体名为 B
• 元素 2 的第一个字段引用元素 3
• 元素 3 是一个 i64
• 元素 3 的值是 10

提取器通过展平数据结构来生成事实：它为数据结构中的每个元素生成唯一标识符，并将元素之间的引用转换为标识符。

对于这些事实中的每一个，提取器将调用提取器后端进行以下操作。

对于每个事实，提取器将调用提取器后端来具体化事实。例如，我们可以使用向量后端将这些提取的事实具体化为元组向量。然后，您可以使用这些向量作为Rust中嵌入的Datalog引擎查询的输入，例如Ascent或Crepe。

let input = Foo::A(Box::new(Foo::B(10)));
let mut extractor = DatalogExtractor::new(backend::vector::Backend::default());
input.serialize(&mut extractor);

// Now we can inspect the tables in the backend to see what facts got
// extracted from the input.

let data: backend::vector::BackendData<ElemId> = extractor.get_backend().get_data();

// there are 3 total elements
assert!(data.type_table.len() == 3);

// there are 2 enum variant elements
assert!(data.variant_type_table.len() == 2);

// there is 1 number element
assert!(data.number_table.len() == 1);

或者，您可以将生成的数据存储在带有Souffle SQLite后端的SQLite文件中。然后，您可以使用此文件作为由Souffle执行的Datalog查询的输入EDB。

let input = Foo::A(Box::new(Foo::B(10)));
let mut backend = backend::souffle_sqlite::Backend::default();
let mut extractor = DatalogExtractor::new(&mut backend);
input.serialize(&mut extractor);
backend.dump_to_db("input.db");

命令行工具

Serde Datalog还提供了名为serde_datalog的命令行工具，可以将数据从JSON或YAML等多种输入格式转换为SQLite文件，使用Souffle SQLite后端。这使得您可以将Souffle Datalog用作数据格式的查询语言，就像jq或yq一样。

示例

考虑以下JSON文件，其中包含2020年纽约市人口普查的borough级人口数据census.json

{
	"boroughs": [
		{ "name": "Bronx", "population": 1472654 },
		{ "name": "Brooklyn", "population": 2736074 },
		{ "name": "Manhattan", "population": 1694251 },
		{ "name": "Queens", "population": 2405464 },
		{ "name": "Staten Island", "population": 495747 }
	]
}

我们可以编写一个Souffle Datalog查询来计算纽约市的总人口。首先，使用以下serde_datalog调用从JSON文件中提取事实数据库

> serde_datalog census.json -o census.db

接下来，我们在Souffle Datalog文件中编写实际的查询，文件名为census.dl

#include "schemas/serde_string_key.dl"

.decl boroPopulation(boro: ElemId, population: number)
boroPopulation(boro, population) :-
    rootElem(_, root),
    map(root, "boroughs", boroList),
    seq(boroList, _, boro),
    map(boro, "population", popId),
    number(popId, population).

.decl totalPopulation(total: number)
totalPopulation(sum pop : { boroPopulation(_, pop) }).

.input type, bool, number, string, map, struct, seq, tuple, structType, variantType(IO=sqlite, dbname="census.db")
.output totalPopulation(IO=stdout)

请注意，定义在schemas/serde_string_key.dl中的模式假定映射只能有字符串键。这对于JSON或TOML等格式是正确的。文件schemas/serde.dl定义了一个更通用的模式，没有这个假设，因此可以表示由Serde序列化的任何值。当适用时（即处理JSON或TOML格式的输入时），serde_datalog工具将在前一个模式下生成事实，但将生成符合后一个模式的事实。

递归示例

Datalog在涉及递归的查询中表现出色。例如，考虑以下包含软件包依赖信息的JSON文件

{
    "packages": [
        { "package": "A", "dependencies": ["B"] },
        { "package": "B", "dependencies": ["C", "D"] }
    ]
}

我们可以编写一个查询来计算软件包A的传递依赖项，如下所示

#include "schemas/serde_string_key.dl"

.decl dependsOn(package1: symbol, package2: symbol)
dependsOn(package1, package2) :-
    rootElem(_, root),
    map(root, "packages", plist),
    seq(plist, _, p),
    map(p, "package", pname),
    string(pname, package1),
    map(p, "dependencies", pdeps),
    seq(pdeps, _, dep),
    string(dep, package2).

dependsOn(package1, package3) :-
    dependsOn(package1, package2),
    dependsOn(package2, package3).

.decl depsA(dep: symbol)
depsA(dep) :- dependsOn("A", dep).

.input rootElem, type, bool, number, string, map, struct, seq, tuple, structType, variantType(IO=sqlite, dbname="test3_json.db")
.output depsA(IO=stdout)

此查询将返回以下输出

---------------
depsA
===============
B
C
D
===============