摘要： 树模式是查询树型结构数据如XML 和LDAP 的天然模型。在一个给定的数据库上进行查询，查询的效率很大程度上依赖于查询的大小。因此，在查询前删除查询中的冗余分支，使查询最小化是非常重要的。在树型结构数据库中，存在孩子必需、后代必需和子类3种完整性约束是十分普遍的。针对存在这3 种完整性约束的情况，基于扩展的模拟概念提出了一种复杂度为O(n2)的最小化树模式查询算法(n 为树模式查询的节点数)。分析结果表明这个算法的效率要远高于同类算法。

关键词: XML 查询；树模式查询；完整性约束；查询最小化；模拟

Abstract: Tree pattern is the natural model to query tree-structured data such as XML and LDAP-style network directories. The efficiency of finding the result of a query on a given input database depends on the size of the query. So, it's important to minimize the query before attempting to compute the result of the query. Required-child, required-descendant and subtype integrity constrains all prevail in tree-structured databases. An O(n2) algorithm called MinTPQ for minimizing tree pattern queries on the tree-structured database is introduced in the presence of the three kinds of integrity constraints; n is the number of the nodes of the tree pattern queries. The algorithm is based on the concept of extended simulation.Analytical result shows the effectiveness of the tree pattern minimization technique.

Key words: XML queries; Tree pattern queries; Integrity constraints; Query minimization; Simulation