联合正则路径查询
- 通过结合
CQ 和RPQ 得到CRPQ ，形式如(2)
比较并返回路径
- 在某些场景下（例如找出web上联通的数据），需要指定路径间的关系同时得到实际的路径作为查询结果
-
ECRPQ 提供以上两种特性，ECRPQ 在两个层面上扩展了CRPQ
- 我们首先基于
Σ 定义正则关系的规范。设⊥ 为一个独立于Σ 的符号，利用⊥ 扩展Σ 得到Σ⊥ - 设
x¯=(s1,s2,...sn) 为一个基于Σ 的字符串的n 元组。构造一个基于(Σ⊥)n 字符串[s¯] ，其长度是sj 的最大值，且第i 个符号是一个元组(c1,...,cn) （当sk 的长度至少是i 时，每个ck 等于sk 的第i 个符号，否则等于⊥ ）。也就是说我们用⊥ 填补短字符串，从而把n 个字符串视作一个字符串。对于任何Σ∗ 中的n 元关系S ，当基于(Σ⊥)n 的字符串集合[s¯]|s¯∈S 能被基于(Σ⊥)n 的正则自动机接受或者能用基于(Σ⊥)n 正则表达式表示,则被认为是正则的。我们也应当利用相同的字母来表示基于(Σ⊥)n 的正则表达式和基于Σ∗ 的关系 - 除了
CRPQ 中的节点变量，我们还确定了一个可数路径变量集合（用@H_73_1502@π,ω,@H_301_1519@χ 来表示）。一条基于Σ 的扩展联合正则路径请求ECRPQ 的表达式为：ans(z¯,χ¯)←⋀1≤i≤m(xi,πi,yi),⋀1≤j≤tRj(ω¯j)
-
ECRPQ 的语义是CRPQ 的延伸。对于一个ECRPQ 的查询，从节点变量到节点的映射关系为σ ，从路径变量到路径的映射关系为μ ，当满足以下两个条件时，则可认为(G,σ,μ)|=Q ：
- 查询结果可定义为：
Q(G)={(@H_238_3403@σ(z¯),μ(χ¯))|(G,σ,μ)|=Q} - 举例说明：
- 在
RDF 的查询语句中，路径可以被基于特定的语义关联比较。边相当于RDF 属性路径相当于属性序列。定义属性a 是b 的子属性a≺b 。两个属性序列u 和v 被称作ρ−isomorphic （路径同构）当且仅当u=u1,...,un 和v=v1,...,vn 且@H_502_3881@ui≺vi 或vi≺ui ，1≤i≤n 。节点x @H_739_4037@x和@H_349_4041@@H_285_4043@@H_2_4046@@H_505_4047@y 被称作ρ−isoAssociated （路径关联）当且仅当x 和y 是两条同构路径属性序列的起点。 - 找出路径关联的节点无法使用
CRPQ 表示，因为这需要保证两条路径长度相同。然而，路径同构的属性对能用基于表达式(⋃a,b∈σ:(a≺b⋁b≺a)(a,b))∗ 的正则关系@H_176_4301@R 来表示。一个ECRPQ 返回路径关联的点对x 和y 可以被写成以下形式：@H_606_4404@ans(x,y)←(x,π1,z1),(y,π2,z2),R(π1,π2) ECRPQ 中的路径变量也可以被用来返回找出的实际路径。例如我们需要找出RDF 资源r 和s 间的每条路径，且路径包含资源e ，可以用以下形式表示：ans(π1,π2)←(r,π1,e),(e,π2,s) π1 和π2 为实际路径 - 包含回溯引用的正则表达式
(REBR) ，正如egrep 和Perl @H_244_5029@Perl中所提供的。举个例子，(r)%X ，r 是正则表达式，X 是变量（绑定字符串w∈L(r) 到X ）。然后用表达式中的X 去匹配w 。ECRPQ 不能表示所有的REBR ，但另一方面，ECRPQ 能匹配模式，例如@H_404_5318@anbncn ans(x,y)←(x,π1,z1),(z1,π2,z2),(z2,π3,y),a∗(π1),b∗(π2),c∗(π3),el(π1,π2),el(π2,π3)
el(π,π′) 是的简写(⋃a,b∈σ(a,b))∗(π,π′)
- 在
