XML查询模式

　　在XML数据库中，现有的XML关联规则挖掘方法利用统计出的规则前、后件所属的同一子树在XML数据库中出现次数，来作为度量规则兴趣度的基础。对于多子树的关联规则而言，由于不存在这样的一个基础，因此需要研究新的度量方法。

　　由XML查询表达式的定义可知，给定XML文档上的一个查询的查询结果是该文档中由路径表达式定位的、并且满足过滤条件的文档子树。令XQm(obj): con表示XML文档的一种查询模式，其中查询对象obj是路径表达式p1, p2, …, pn的集合，查询条件con是选择运算r(aθb)的非空有限集合，对于查询条件中的任一选择运算r(aθb)，r对应于某路径表达式pi，a对应于pi的某一子表达式，b对应于相应的节点变量或常量。同一文档子树上的选择运算是逻辑上的“与”关系，不同子树必须能够通过各自的某个节点对应的同一变量或常量等值连接。

　　例1：建立在图1所示文档上的符合要求的XML查询模式。

　　XQm1(p1): p1(//Location = SB);XQm2(p1): p1(//Item = Fuel);

　　XQm3(p1): p1(//Location = x), p1(//Item = Fuel);

　　XQm4(p2): p2(//Location = x), p2(//Aircraft = SSA);

　　XQm5(p1, p2): p1(//Location = x), p1(//Item = Fuel), p2(//Location = x), p2(//Aircraft = SSA)。

　　其中，p1和p2分别对应于路径表达式/AirForce/order和/AirForce/garrison。

　　在查询模式的连接上，关系查询模式涉及的关系实例之间只能通过属性实现等值连接，而对于XML查询模式，子树间的连接更加灵活，可以通过更低一层的子树或者叶节点来实现。

　　例2：例1中的XML查询模式XQm3和XQm4可以通过相同的子树//Location实现连接，XQm5即为该连接处理的结果。

　　给定XML文档t上查询模式XQm的支持度的计算可以表示为Sup(XQm) = |XQmA| / N，其中N的计算如下：|obj| = 1时，令p表示定位待查询子树的路径表达式，N = |{p(t)}|，其中{p(t)}表示文档t中所有以路径表达式p定位的文档子树的集合;|obj| > 1时，令p1, p2, …, pn表示对应的路径表达式，则N = Max(|{p1(t)}|, …, |{pn(t)}|)。

　　例3：例1中的XML查询模式XQm1-XQm5的支持度分别为Sup(XQm1) = 0.25，Sup(XQm2) = 0.75，Sup(XQm3) = 0.75，Sup(XQm4) = 0.8，Sup(XQm5) = 0.75。

　　同频繁项集相似，支持度不低于最小支持度阈值smin的查询模式称为频繁查询模式，简称为频繁模式。

　　扩展XML关联规则

　　扩展关联规则由上述查询模式构成。若给定查询模式XQm和XQm'可以连接，则存在形如XQm=>XQm'的扩展关联规则。

　　支持度与置信度同样也是扩展关联规则的两个重要度量指标。对于规则XQm=>XQm'，其支持度s = Sup(XQm∪XQm')，置信度c = Sup(XQm∪XQm')/Sup(XQm)。同样，称该扩展关联规则是有意义的，当其支持度和置信度分别不低于指定的最小支持度阈值和最小置信度阈值，即s≥smin并且c≥cmin。

　　上述定义要求构成规则的两个查询模式可以连接的原因在于实现多子树情况下XAR的支持度Sup(XQm1∪XQm2)的计算。显然，如果XQm1和XQm2涉及有相同的子树，则通过该子树上的与操作可以实现查询模式的连接;如果XQm1和XQm2涉及不同的子树，而两个子树中存在可以连接的变量，则查询模式亦可以通过该变量实现连接。

　　反映在实际的XML文档中，上述连接的结果是可以明确界定的公共子树，即为计算Sup(XQm1∪XQm2)的基础。除此之外，该支持度是无法计算的，这样的规则即便是得到了，由于其兴趣度的无法度量、缺乏基本的理论依据，因而也就是不可信的。

　　以此为基础，通过查询模式就可以方便的刻画各种形式的XML关联规则，拓展关联规则的刻画范围。下面结合1给出相应的示例。

　　例4：从图1可以得到以下部分的扩展关联规则：

　　①同一子树中的关联规则

　　XQm(/AirForce/order): /AirForce/order(//Location = SB) => XQm(/AirForce/order): /AirForce/order(//Item = Fuel) (s = 0.25, c = 1)

　　②不同子树中的关联规则

　　XQm(/AirForce/garrison): /AirForce/garrison(//Location = x), /AirForce/garrison (//Aircraft = SSA) => XQm(/AirForce/order): /AirForce/order (//Location = x), /AirForce /order (//Item = Fuel) (s = 0.75, c = 0.94)。

　　除了子树这一级别的粒度外，通过查询模式还可以进一步对规则的前、后件进行扩展，如森林。

　　从上述示例可以清晰看到扩展关联规则能够涵盖对经典关联规则的刻画，并且极大的对其进行了扩展，使得通过查询模式刻画的关联规则能够更加灵活的反映XML数据库中信息之间潜在的联系。