论文公式解析：知识图谱构建的代数基础

1. 引言

本文提出了一种用于知识图谱（KG）构建的声明式映射语言的代数基础。当前映射语言（如RML）缺乏形式化定义，导致实现不一致且无法进行正确性证明的优化。本文贡献包括：

• 一种语言无关的代数，用于捕获映射定义。
• 将RML转换为该代数的算法（从而提供RML的形式语义）。
• 代数重写规则，用于优化映射计划。

2. 数据模型（Data Model）

核心思想

数据模型基于关系模型，但专门设计用于处理RDF术语（IRI、空白节点、字面量）和错误值（ϵ）。中间结果称为“映射关系”（mapping relations），最终转换为RDF数据集。

符号解释

• $S$：无限字符串集合。
• $I\subset S$：有效IRI集合。
• $L$：字面量集合，每个字面量是二元组 $(\text{lex},\text{dt})\in S\times I$，其中lex是词法形式，dt是数据类型IRI。
• $B$：空白节点集合，与$S$和$L$互斥。
• $T=I\cup B\cup L$：所有RDF术语的集合。
• $\bar{T}$：$T$中元素的序列集合。
• RDF三元组：$(s,p,o)\in (I\cup B)\times I\times T$。
• RDF数据集：{Gdflt,(n1,G1),…,(nm,Gm)}\{G_{\text{dflt}}, (n_1, G_1), \dots, (n_m, G_m)\}{Gdflt​,(n1​,G1​),…,(nm​,Gm​)}，其中$G_i$是RDF图，$n_i\in I\cup B$。
• $A$：无限属性集合。
• $ϵ$：错误值（非RDF术语）。

映射元组（Mapping Tuple）

定义1：映射元组是部分函数 t:A→T∪{ϵ}t: A \to T \cup \{\epsilon\}t:A→T∪{ϵ}。

• 两个元组$t$和$t^{\prime }$兼容：当且仅当对于所有$a\in \text{dom}(t)\cap \text{dom}(t^{\prime })$，有$t(a)=t^{\prime }(a)$。
• 合并：$t\cup t^{\prime }$ 是合并后的元组，定义域为$\text{dom}(t)\cup \text{dom}(t^{\prime })$。

映射关系（Mapping Relation）

定义2：映射关系$r$是二元组$(A,I)$，其中：

• $A\subset A$：有限非空属性集（模式）。
• $I$：映射元组集合，且每个元组$t\in I$满足$\text{dom}(t)=A$。

转换为RDF数据集

定义3：假设四个特殊属性：$a_s$（主语）、$a_p$（谓语）、$a_o$（宾语）、$a_g$（图）。映射关系$r=(A,I)$转换为RDF数据集：

• Ivalid={t∈I∣(t(as),t(ap),t(ao))是有效RDF三元组且t(ag)∈I∪B}I_{\text{valid}} = \{ t \in I \mid (t(a_s), t(a_p), t(a_o)) \text{是有效RDF三元组且} t(a_g) \in I \cup B \}Ivalid​={t∈I∣(t(as​),t(ap​),t(ao​))是有效RDF三元组且t(ag​)∈I∪B}。
• N={t(ag)∣t∈Ivalid且t(ag)≠rr:defaultGraph}N = \{ t(a_g) \mid t \in I_{\text{valid}} \text{且} t(a_g) \neq \text{rr:defaultGraph} \}N={t(ag​)∣t∈Ivalid​且t(ag​)=rr:defaultGraph}。
• 默认图$G_{\text{dflt}}$包含所有$t(a_g)=\text{rr:defaultGraph}$的三元组。
• 命名图$(n,G_n)$包含所有$t(a_g)=n$的三元组。

示例（表1）：

• $t(a_x)=("12",\text{xsd:integer})$（字面量），$t^{\prime }(a_x)=\text{ex:alice}$（IRI），$t^{\prime \prime }(a_x)=ϵ$（错误）。
• Ivalid={t,t′′}I_{\text{valid}} = \{t, t''\}Ivalid​={t,t′′}（因为$t^{\prime }$的谓语是字面量，无效）。
• 结果RDF数据集：默认图包含$(\text{ex:alice},\text{foaf:knows},\text{ex:bob})$，命名图$\text{ex:g2}$包含$(\text{ex:bob},\text{foaf:name},("Bob",\text{xsd:string}))$。

3. 映射代数（Mapping Algebra）

代数包含五类运算符，可组合成复杂表达式，定义从异构数据源到RDF数据集的映射。

4.1 源运算符（Source Operator）

目的：从数据源（如CSV、JSON）提取数据并转换为映射关系。

符号解释：

• $D$：数据对象集合（如CSV文件、JSON文档）。
• $Q$：查询语言集合（如JSONPath、CSV列名）。
• 源类型（Definition 4）：元组$(D_{\text{ds}},D_{c1},D_{c2},L,L^{\prime },\text{eval},{\text{eval}}^{\prime },\text{cast})$，其中：
  • $D_{\text{ds}}$：数据源类型（如所有CSV文件）。
  • $D_{c1},D_{c2}$：上下文对象和值对象的集合。
  • $L,L^{\prime }$：查询语言（$L$用于选择上下文，$L^{\prime }$用于提取值）。
  • $\text{eval}:D_{\text{ds}}\times L\to D_{c1}$：从数据源选择上下文对象。
  • ${\text{eval}}^{\prime }:D_{\text{ds}}\times D_{c1}\times L^{\prime }\to D_{c2}$：从上下文对象提取值。
  • $\text{cast}:D_{c2}\to L$：将值转换为RDF字面量。
• 数据源（Definition 5）：$s=(\text{type},D)$，其中$D\in D_{\text{ds}}$。

源运算符（Definition 6）：

• 输入：数据源$s$，查询$q\in L$，部分函数$P:A\to L^{\prime }$（属性到查询的映射）。

• 输出：映射关系$r=(A,I)$，其中$A=\text{dom}(P)$，且：
  I={{a1→cast(v1),…,an→cast(vn)}∣d∈eval(D,q), ∀ai∈dom(P):vi∈eval′(D,d,P(ai))} I = \left\{ \{a_1 \to \text{cast}(v_1), \dots, a_n \to \text{cast}(v_n)\} \mid d \in \text{eval}(D, q),\, \forall a_i \in \text{dom}(P): v_i \in \text{eval}'(D, d, P(a_i)) \right\} I={{a1​→cast(v1​),…,an​→cast(vn​)}∣d∈eval(D,q),∀ai​∈dom(P):vi​∈eval′(D,d,P(ai​))}

  即：对每个上下文对象$d$，生成一个元组，其属性值通过$P$中的查询提取并转换。

示例（CSV源）：

• $s_{\text{ex}}=({\text{type}}_{\text{csv}},D_{\text{ex}})$，其中$D_{\text{ex}}$是CSV文件。
• $q=ϵ$（选择所有行）。
• P={a1→id,a2→firstname,a3→age}P = \{a_1 \to \text{id}, a_2 \to \text{firstname}, a_3 \to \text{age}\}P={a1​→id,a2​→firstname,a3​→age}。
• 结果：两个元组，如t1={a1→("1",xsd:string),a2→("Alice",xsd:string),a3→("23",xsd:string)}t_1 = \{a_1 \to ("1", \text{xsd:string}), a_2 \to ("Alice", \text{xsd:string}), a_3 \to ("23", \text{xsd:string})\}t1​={a1​→("1",xsd:string),a2​→("Alice",xsd:string),a3​→("23",xsd:string)}。

4.2 扩展运算符（Extend Operator）

目的：向映射关系添加新属性，值由扩展表达式计算。

符号解释：

• 扩展函数（Definition 7）：函数f:(T∪{ϵ})n→(T∪{ϵ})f: (T \cup \{\epsilon\})^n \to (T \cup \{\epsilon\})f:(T∪{ϵ})n→(T∪{ϵ})。
  • 示例：$\text{toInt}(v)$将字符串字面量转换为整数字面量（若可能），否则返回$ϵ$。
• 扩展表达式（Definition 8）：
  1. RDF术语（如$\text{ex:alice}$）。
  2. 属性（如$a_1$）。
  3. 函数应用：$(f,{\varphi }_1,\dots ,{\varphi }_n)$，其中${\varphi }_i$是扩展表达式。
• $\text{attrs}(\varphi )$：表达式$\varphi$中提到的属性集合。
• 评估（Definition 9）：$\text{eval}(\varphi ,t)$在元组$t$上计算$\varphi$的值。

扩展运算符（Definition 10）：

• 输入：映射关系$r=(A,I)$，属性$a\notin A$，扩展表达式$\varphi$。
• 输出：r′=(A∪{a},I′)r' = (A \cup \{a\}, I')r′=(A∪{a},I′)，其中I′={t∪{a→eval(ϕ,t)}∣t∈I}I' = \{ t \cup \{a \to \text{eval}(\phi, t)\} \mid t \in I \}I′={t∪{a→eval(ϕ,t)}∣t∈I}。

示例：

• $\varphi =(\text{toInt},a_3)$：将$a_3$的值转换为整数。
• 应用${\text{Extend}}_{a_4}^{\varphi }(r)$：新属性$a_4$包含转换后的值（无效值则为$ϵ$）。

4.3 关系代数运算符

投影（Projection, Definition 11）：

• ${\text{Project}}_P(r)$：保留属性集$P$，删除其他属性。

等值连接（Equijoin, Definition 12）：

• ${\text{EqJoin}}_J(r_1,r_2)$：基于属性对集合$J\subseteq A_1\times A_2$连接两个关系（要求$A_1\cap A_2=\varnothing$）。

并集（Union, Definition 13）：

• $\text{Union}(r_1,r_2)$：要求$r_1$和$r_2$模式相同。

4. RML到代数的转换（Algorithm 1）

核心思想：将RML映射（RDF图描述）转换为代数表达式，从而形式化RML语义。

步骤：

1. 规范化：应用SPARQL更新查询（附录A），将RML映射转换为标准形式（如扩展快捷属性、确保每个三元组映射只有一个谓语-对象映射等）。
2. 迭代每个三元组映射：
   • 源运算符：使用$\text{SrcAndRootQuery}$（Definition 14）获取数据源和根查询，使用$\text{ExtractQueries}$（Algorithm 2）从术语映射中提取查询表达式（生成属性-查询映射$P$）。
   • 扩展主语和谓语：使用$\text{CreateExtExpr}$（Algorithm 3）创建扩展表达式，生成$a_s$和$a_p$。
   • 处理对象映射：
     • 如果是引用对象映射（join），创建另一个源运算符并执行等值连接。
     • 否则，直接扩展生成$a_o$。
   • 处理图映射：扩展生成$a_g$（若未指定，使用默认图IRI）。
3. 合并：所有三元组映射的结果通过并集合并。

Algorithm 2（ExtractQueries）：从术语映射中提取查询表达式（包括引用、模板中的占位符、join条件中的子查询）。
Algorithm 3（CreateExtExpr）：根据术语映射类型（常量、引用、模板）创建扩展表达式，使用扩展函数（如$\text{toIRI}$、$\text{toLiteral}$、$\text{concat}$）。

5. 代数等价规则（用于优化）

6.1 投影下推（Projection Pushing）

• Proposition 1：如果$\text{attrs}(\varphi )\cap A\subseteq P$，则：
  ProjectP∪{a}(Extendaϕ(r))=Extendaϕ(ProjectP(r)) \text{Project}_{P \cup \{a\}} \left( \text{Extend}_a^{\phi}(r) \right) = \text{Extend}_a^{\phi} \left( \text{Project}_P(r) \right) ProjectP∪{a}​(Extendaϕ​(r))=Extendaϕ​(ProjectP​(r))

  即：投影可下推到扩展之前，减少中间结果大小。

• Proposition 3：源运算符上的投影可消除（直接调整$P$）：
  $${\text{Project}}_P\left(\text{Source}(s,q,P)\right)=\text{Source}(s,q,P^{\prime })$$

  其中$P^{\prime }$是$P$到$P$的限制。

6.2 扩展运算符的推拉（Pushing/Pulling Extend）

• Proposition 5：如果$\text{attrs}(\varphi )\cap A_2=\varnothing$，则：
  $${\text{Extend}}_a^{\varphi }\left({\text{EqJoin}}_J(r_1,r_2)\right)={\text{EqJoin}}_J\left({\text{Extend}}_a^{\varphi }(r_1),r_2\right)$$

  即：扩展可下推到连接之前（若依赖关系允许），减少连接后处理的数据量。

• Proposition 6：两个扩展运算符可交换（如果互不依赖）。

6. 直观解释与应用场景

• 直观解释：代数类似于关系代数，但专门针对RDF生成，处理异构数据源和R术语转换。源运算符像“扫描”，扩展运算符像“计算列”，连接和投影用于整合和筛选数据。
• 应用场景：
  • 优化映射计划：通过代数等价规则重写计划，减少内存使用和执行时间（例如提前投影）。
  • 形式化语义：为RML等语言提供精确语义，确保实现一致性。
  • 语言无关基础：可支持多种映射语言（如R2RML、SPARQL-Generate）。

7. 示例说明

假设CSV数据：

id,firstname,age
1,Alice,23
2,Bob,unknown

RML映射片段：

ex:tm rml:logicalSource [ rml:source "data.csv"; rml:referenceFormulation ql:CSV ];
  rr:subjectMap [ rr:template "http://example.org/{id}"; rr:termType rr:IRI ];
  rr:predicateObjectMap [ rr:predicate rdfs:label;
    rr:objectMap [ rml:reference "firstname" ] ].

代数转换：

1. 源运算符：$\text{Source}(s,ϵ,P)$，其中P={a1→id,a2→firstname}P = \{a_1 \to \text{id}, a_2 \to \text{firstname}\}P={a1​→id,a2​→firstname}。
2. 扩展主语：${\text{Extend}}_{a_s}^{{\varphi }_s}$，其中${\varphi }_s=\text{toIRI}(\text{concat}("http://example.org/",a_1),\text{base})$。
3. 扩展谓语：${\text{Extend}}_{a_p}^{{\varphi }_p}$，其中${\varphi }_p=\text{rdfs:label}$（常量）。
4. 扩展宾语：${\text{Extend}}_{a_o}^{{\varphi }_o}$，其中${\varphi }_o=\text{toLiteral}(a_2,\text{xsd:string})$。
5. 扩展图：${\text{Extend}}_{a_g}^{{\varphi }_g}$，其中${\varphi }_g=\text{rr:defaultGraph}$。
6. 投影：保留{as,ap,ao,ag}\{a_s, a_p, a_o, a_g\}{as​,ap​,ao​,ag​}。

最终生成RDF三元组：

• $(\text{http://example.org/1},\text{rdfs:label},"Alice")$
• $(\text{http://example.org/2},\text{rdfs:label},"Bob")$