联合正则路径查询

• 通过结合$CQ$和$RPQ$得到$CRPQ$，形式如$(2)$

比较并返回路径

• 在某些场景下（例如找出web上联通的数据），需要指定路径间的关系同时得到实际的路径作为查询结果
• $ECRPQ$提供以上两种特性，$ECRPQ$在两个层面上扩展了$CRPQ$
  
  • 允许查询的头部存在自由路径变量
  • 允许校验查询体中路径间的关系而不是简单的令路径和正则语言相匹配
• 我们首先基于$Σ$定义正则关系的规范。设$\bot$为一个独立于$Σ$的符号，利用$\bot$扩展$Σ$得到 Σ⊥@H_502_387@ $Σ_{\bot}$
• 设 x¯=(s1@H_502_387@,s2@H_502_387@,...sn) $\bar x = (s_1,s_2,...s_n)$为一个基于$Σ$的字符串的$n$元组。构造一个基于 (Σ⊥@H_502_387@)n $(Σ_{\bot})^n$字符串$[\bar s]$，其长度是 @H_404_673@sj $s_j$的最大值，且第$i$个符号是一个元组 (c1@H_502_387@,...,cn) $(c_1,...,c_n)$（当$s_k$的长度至少是$i$时，每个$c_k$等于 @H_403_890@sk $s_k$的第$i$个符号，否则等于$\bot$）。也就是说我们用$\bot$填补短字符串，从而把$n$个字符串视作一个字符串。对于任何 Σ∗@H_502_387@ $Σ^*$中的$n$元关系$S$，当基于 (Σ⊥@H_502_387@)n $(Σ_{\bot})^n$的字符串集合${[\bar s]|\bar s \in S}$能被基于 (Σ⊥@H_502_387@)n $(Σ_{\bot})^n$的正则自动机接受或者能用基于 (Σ⊥@H_502_387@)n $(Σ_{\bot})^n$正则表达式表示,则被认为是正则的。我们也应当利用相同的字母来表示基于 (Σ⊥@H_502_387@)n $(Σ_{\bot})^n$的正则表达式和基于 Σ∗@H_502_387@ $Σ^*$的关系
• 除了$CRPQ$中的节点变量，我们还确定了一个可数路径变量集合（用 @H_152_1502@π,ω,χ $π,ω,χ$来表示）。一条基于$Σ$的扩展联合正则路径请求$ECRPQ$的表达式为：
  ans(z@H_404_1628@¯,χ¯)←⋀1≤i≤m@H_502_387@(xi,πi,@H_404_673@yi),⋀1≤j≤t@H_502_387@Rj(ω¯j)
  $$ans(\bar z,\bar χ)← \bigwedge_{1≤i≤m} (x_i,π_i,y_i),\bigwedge_{1≤j≤t} R_j(\bar ω_j)$$
  
  1. $m>0,t≥0$
  2. 每个$R_j$是一个定义了正则关系的正则表达式
  3. x¯=(x1@H_502_387@,...,xm) $\bar x = (x_1,x_m)$和 y¯=(y1@H_502_387@,...,ym) $\bar y = (y_1,y_m)$都是节点变量元组
  4. π¯=(π1@H_502_387@,...,πm) $\bar π = (π_1,π_m)$是路径变量元组
  5. {w¯1@H_502_387@,...,w¯@H_241_2301@t} $\{\bar w_1,\bar w_t \}$是不同的路径变量元组，例如 w¯@H_241_2301@j $\bar w_j$是一个$\bar π$中变量的元组，变量数目等于$R_j$
  6. $\bar z$是一个$\bar x,\bar y$中节点变量的元组
  7. $\bar \chi$是一个${\bar π}$中路径变量的元组
• $ECRPQ$的语义是$CRPQ$的延伸。对于一个$ECRPQ$的查询，从节点变量到节点的映射关系为$σ$，从路径变量到路径的映射关系为$μ$，当满足以下两个条件时，则可认为$(G,σ,μ) |= Q$：
  
  • $μ(π_i)$是$G$中的一条从 σ(xi) @H_301_2986@σ(x_i)到 σ(@H_404_673@@H_404_3007@y@H_537_3015@i) $σ(y_i)$的路径，$1 ≤ i ≤ m$
  • 对于每个 w¯@H_241_2301@j=(πj1,...,πjk) $\bar w_j = (π_{j_1},π_{j_k})$，由 μ(πj1),...μ(π@H_571_3301@jk) $μ(π_{j_1}),...μ(π_{j_k})$中标签组成的字符串元组属于关系$R_j$
• 查询结果可定义为：
  Q(G)={(@H_292_3403@σ(z¯),μ(χ¯))|(G,σ,μ)|@H_301_3505@=Q}
  $$Q(G) = \{(σ(\bar z),μ(\bar χ)) | (G,μ) |= Q\}$$
• 举例说明：
  
  • 在$RDF$的查询语句中，路径可以被基于特定的语义关联比较。边相当于$RDF$属性路径相当于属性序列。定义属性$a$是$b$的子属性$a \prec b$。两个属性序列$u$和$v$被称作$ρ-isomorphic$（路径同构）当且仅当 u=u1@H_502_387@,...,un $u=u_1,u_n$和 v=v1@H_502_387@,...,vn $v=v_1,v_n$且 ui≺@H_404_673@vi $u_i \prec v_i$或 @H_404_673@vi≺ui $v_i \prec u_i$，$1 \le i \le n$。节点 x @H_327_4037@x和@H_117_4041@ @H_222_4043@@H_945_4046@@H_80_4047@y $y$被称作$ρ-isoAssociated$（路径关联）当且仅当$x$和$y$是两条同构路径属性序列的起点。
  • 找出路径关联的节点无法使用$CRPQ$表示，因为这需要保证两条路径长度相同。然而，路径同构的属性对能用基于表达式 (⋃a,b∈σ:(a≺b⋁b≺a)@H_502_387@(a,b)@H_404_673@)∗@H_502_387@ @H_404_4295@(\bigcup_{a,b \in \sigma : (a \prec b \bigvee b \prec a )} (a,b))^*的正则关系 @H_169_4301@R $R$来表示。一个$ECRPQ$返回路径关联的点对$x$和$y$可以被写成以下形式：
    @H_126_4404@ ans(x,y)←(x,π1@H_502_387@,z1@H_502_387@),(y,π2@H_502_387@,z2@H_502_387@),R(π1@H_502_387@,π2@H_502_387@)
    $$ans(x,y) \leftarrow (x,π_1,z_1),(y,π_2,z_2),R(π_1,π_2)$$ $ECRPQ$中的路径变量也可以被用来返回找出的实际路径。例如我们需要找出$RDF$资源$r$和$s$间的每条路径，且路径包含资源$e$，可以用以下形式表示：
    ans(π1@H_502_387@,π2@H_502_387@)←(r,π1@H_502_387@,e),(e,π2@H_502_387@,s)
    $$ans(\pi_1,\pi_2) \leftarrow (r,\pi_1,e),(e,\pi_2,s)$$ π1@H_502_387@ $\pi_1$和 π2@H_502_387@ $\pi_2$为实际路径
  • 包含回溯引用的正则表达式$(REBR)$，正如$egrep$和 Perl @H_127_5029@Perl中所提供的。举个例子，$(r) \% X$，$r$是正则表达式，$X$是变量（绑定字符串$w \in L(r)$ 到 $X$）。然后用表达式中的$X$去匹配$w$。$ECRPQ$不能表示所有的$REBR$，但另一方面，$ECRPQ$能匹配模式，例如$a^n b^n c^n$
    ans(x,y)←(x,π1@H_502_387@,z1@H_502_387@),(z1@H_502_387@,π2@H_502_387@,z2@H_502_387@),(z2@H_502_387@,π3@H_502_387@,y),a∗@H_502_387@(π1@H_502_387@),b∗@H_502_387@(π2@H_502_387@),c∗@H_502_387@(π3@H_502_387@),el(π1@H_502_387@,π2@H_502_387@),el(π2@H_502_387@,π3@H_502_387@)
    $$ans(x,(z_1,(z_2,\pi_3,y),a^*(\pi_1),b^*(\pi_2),c^*(\pi_3),el(\pi_1,\pi_2),el(\pi_2,\pi_3)$$
    $el(\pi,\pi^{'})$是的简写 (⋃a,b∈σ@H_502_387@(a,b)@H_404_673@)∗@H_502_387@(π,π′)