存在完整性约束时最小化树模式查询的算法  

An Efficient Algorithm for Minimizing Tree Pattern Queries in the Presence of Integrity Constrains

作　　者：张凡[1] 熊志平 胡运发[1] 

机构地区：[1]复旦大学计算机与信息技术系,上海200433 [2]赛贝斯软件(中国)有限公司,上海200001

出　　处：《计算机工程》2006年第10期66-67,70,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60173027)

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

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

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]