论文部分内容阅读
随着计算机应用技术和电子商务的快速发展,企业可获取的信息数量和类型有了极大的增长。由于XML的可扩展性、结构性以及平台无关性的优点,XML已经成为Intemet数据交换事实上的标准,在Web中得到广泛应用。如通过Web搜索引擎找到XML是自然而然的事情。在搜索引擎查找符合特定条件的XML文档时,即针对于XML数据库的进行查询。因此XML的查询优化具有巨大的商业意义,成为目前研究的热点。XML是专为Web设计的,把XML看作Web世界中的数据模型,目前流行的XML数据模式有多种,如DTD,XML Schema,RELAX NG等。定义XML数据的模式时,常遇到这样的情况,如定义的XML出现了某种形式的结构时,必然有另一种形式的结构同时出现,这便是一类基于XML结构的完整性约束。DTD是一种基于语法的XML规范形式化定义,在考虑结构完整性约束时,一种基于pattern的XML规范形式化定义XSCs模式可以与其联合使用,使得生成的DTD具有更为丰富的语义。模式树是对像XML和LDAP等树形结构数据进行查询的基础。在树形结构数据库上进行树模式匹配的效率取决于模式树的大小,因而尽快发现和删除模式中的冗余节点就显得十分的重要。模式树查询最小化问题,经证明是NP-Hard问题。在本文中,我们研究引入XML结构性约束时的XML模式树查询最小化问题。具体来说,我们将在XSCs模式下,基于几种路径的结构性约束,实现模式树查询最小化。解决该问题的关键技术由Chase技术和删除冗余节点算法两部分组成。首先,我们使用Chase技术对给定查询对应的模式树进行扩展,利用已知的结构性约束,在不改变查询结果的前提下在模式树中增加节点,得到与原模式树查询等价的一棵新的模式树;然后,利用约束独立情况下模式树查询最小化算法,删除Chase阶段生成的模式树中的冗余节点以及在Chase过程中产生的新节点,得到最终的模式树,此模式树对应的模式树查询即为原查询等价的最小化查询。本文中我们提出的XSCM算法就是基于以上思路。经分析,该算法的时间复杂度为多项式时间。实验结果表明,与XML查询的一般方法相比,XSCM在查询的数据量较小的情况下差别不大,但是查询数据量越大,查询效率越高,优势越明显。XSCs模式是针对XML数据模型定义了一些常见的基于结构的完整性约束,然而,还存在一类基于值的约束,基于值的约束在现实生活也是很常见的,所以未来的工作我们将致力于基于XML值的完整性约束下的模式树查询最小化,从而将XML模式树查询最小化问题扩展到更加广泛的应用范围。