Minimization of tree pattern queries
Minimization of tree pattern queries
复制标题
DOI：
10.1145/375663.375730
复制
发表时间：
2001-05
期刊：
影响因子：
--
通讯作者：
S. Amer-Yahia;SungRan Cho;L. Lakshmanan;D. Srivastava
中科院分区：
文献类型：
--
作者：
S. Amer-Yahia;SungRan Cho;L. Lakshmanan;D. Srivastava
树模式形成了查询树形结构数据的自然基础，例如XML和LDAP。由于树结构数据库中树模式匹配的效率取决于模式的大小，因此识别和消除模式中的冗余节点并尽快完成是至关重要的。在这篇文章中，我们研究了树结构数据库上不存在和存在完整性约束(ICs)的树模式最小化问题。当不考虑集成电路时，我们将最小化树模式的过程称为约束无关最小化。为此，我们开发了一种称为CIM的多项式时间算法。CIM的效率源于两个关键性质：(I)一个节点不能是冗余的，除非它的子节点是冗余的；(Ii)冗余节点的消除顺序是无关紧要的。当考虑集成电路的最小化时，我们将其称为约束相关最小化。对于树形结构的数据库，所需的子代/子代和类型共现IC是非常自然的。在这样的IC下，我们证明了最小等价查询是唯一的。我们证明了一个令人惊讶的结果，该算法首先使用ICS来扩充树模式，然后应用CIM，总是找到唯一的最小等价查询，我们称之为ACIM。虽然ACIM也是多项式时间，但由于其固有的非局部性，它在实践中可能会很昂贵。然后，我们提出了一种快速算法CDM，该算法基于沿树模式向上传播“信息标签”来识别和消除由于IC引起的局部冗余。为了提高极小化效率，可以在ACIM之前应用CDM。我们用一项实验研究来补充我们的分析结果，该实验研究表明了我们的树模式最小化技术的有效性。
Tree patterns forms a natural basis to query tree-structured data such as XML and LDAP. Since the efficiency of tree pattern matching against a tree-structured database depends on the size of the pattern, it is essential to identify and eliminate redundant nodes in the pattern and do so as quickly as possible. In this paper, we study tree pattern minimization both in the absence and in the presence of integrity constraints (ICs) on the underlying tree-structured database. When no ICs are considered, we call the process of minimizing a tree pattern, constraint-independent minimization. We develop a polynomial time algorithm called CIM for this purpose. CIM's efficiency stems from two key properties: (i) a node cannot be redundant unless its children are, and (ii) the order of elimination of redundant nodes is immaterial. When ICs are considered for minimization, we refer to it as constraint-dependent minimization. For tree-structured databases, required child/descendant and type co-occurrence ICs are very natural. Under such ICs, we show that the minimal equivalent query is unique. We show the surprising result that the algorithm obtained by first augmenting the tree pattern using ICS, and then applying CIM, always finds the unique minimal equivalent query; we refer to this algorithm as ACIM. While ACIM is also polynomial time, it can be expensive in practice because of its inherent non-locality. We then present a fast algorithm, CDM, that identifies and eliminates local redundancies due to ICs, based on propagating “information labels” up the tree pattern. CDM can be applied prior to ACIM for improving the minimization efficiency. We complement our analytical results with an experimental study that shows the effectiveness of our tree pattern minimization techniques.