Static Analysis of Structural Recursion in Semistructured Databases and Its Consequences
Static Analysis of Structural Recursion in Semistructured Databases and Its Consequences
复制标题
半结构化数据库中结构递归的静态分析及其后果
DOI：
10.1007/978-3-540-30204-9_13
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Balázs Kósa
中科院分区：
文献类型：
--
作者：
A. Benczúr;Balázs Kósa
结构递归是UnQL中的一种图遍历和重构操作[7]，[8]，一种半结构化数据的查询语言。在本文中，我们主要考虑在模式图存在的情况下的可满足性问题[2]，[9]，模式图用于描述半结构化数据的结构。我们引入了一种新的模式图之间的模拟，与关系可以表示在更微妙的方式。借助于运算图，我们还发展了一种定义结构递归语义的新方法。我们的研究结果给我们的算法检查是否一个给定的查询将满足所施加的限制模式图和技术，这些可以参与查询。查询优化方法也被开发。
Structural recursion is a graph traversing and restructuring operation in UnQL [7], [8], a query language for semistructured data. In this paper we consider satisfiability questions mainly in the presence of schema graphs [2], [9], which are used for describing the structure of semistructured data. We introduce a new kind of simulation between schema graphs, with which the relationships can be represented in more subtle ways. By means of operational graphs we also develop a new way for defining the semantics of structural recursions. Our results give us algorithms for checking whether a given query will satisfy the restrictions imposed by schema graphs and techniques with which these can be involved in queries. Query optimizing methods are also developed.