XML查询处理：扩展树模式匹配的理论与算法

“扩展的XML树模式匹配：理论和算法探讨了在XML数据处理中的查询优化问题，特别是针对XML树模式匹配。文章提出了扩展XML树模式的概念，这些模式可能包含父子（PC）、祖先后代（AD）关系、否定函数、通配符以及顺序限制。作者建立了一个名为“匹配叉”的理论框架，揭示了整体算法最优性的内在原理，并在此基础上设计了一组新的算法，用于高效处理这类扩展的XML树模式查询。通过实证和合成数据集的实验，证明了提出的理论和算法的有效性和高效性。” 在XML数据处理领域，查询性能是至关重要的，尤其是随着XML数据的广泛应用。传统的树模式匹配方法主要关注PC和AD关系，但实际的XML查询语言如XPath和XQuery提供了更为丰富的功能，包括否定函数（如not()）、基于顺序的轴（如following-sibling）和通配符（如*）。这些特性使得查询表达能力增强，但同时也增加了处理复杂性的挑战。 本文的核心贡献在于对“扩展XML树模式”的深入研究。这一概念扩大了树模式匹配的范围，允许匹配更为复杂的查询结构。作者提出的“匹配叉”理论框架是对整体算法优化性的理论解释，它揭示了控制中间结果大小以优化查询处理的关键因素。这个框架有助于理解如何设计出更为高效的匹配算法。 基于这个理论，作者开发了一套新颖的算法，专门用于处理包含PC、AD关系、否定、通配符以及顺序限制的扩展XML树模式。这些算法的目标是减少查询执行过程中的计算开销，提高查询效率。实验结果表明，这些算法在处理真实世界和合成数据集时表现出优秀的性能，验证了理论的有效性和算法的实用性。 这篇文章对XML查询处理领域做出了重要贡献，不仅丰富了理论基础，还提供了实用的算法解决方案，有助于提升XML数据库的查询效率，满足日益增长的XML数据处理需求。对于XML查询语言的设计者、数据库开发者以及需要处理大量XML数据的应用程序开发者来说，这篇研究具有很高的参考价值。