Expressiveness of structured document query languages based on attribute grammars

Expressiveness of structured document query languages based on attribute grammars
复制标题

基于属性语法的结构化文档查询语言的表达能力

DOI：
--
复制
发表时间：
1998
期刊：
JACM
影响因子：
--
通讯作者：
J. V. D. Bussche
J. V. D. Bussche
中科院分区：
--
文献类型：
--
作者：
F. Neven;J. V. D. Bussche

文献摘要

被引文献

相似文献

结构化文档数据库可以被自然地看作是上下文无关文法的派生树。在这种观点下，属性文法的经典形式主义成为结构化文档查询语言的形式主义。从这个角度出发，我们研究了BAGs：以命题逻辑公式为语义规则的布尔值属性文法和RAGs：以一阶逻辑公式为语义规则的关系值属性文法的表达能力。BAG只能表示一元查询，RAG可以表示任意元的查询。我们首先表明，（一元）查询表示的BAGs正是那些定义在一元二阶逻辑。然后，我们表明，RAGs表达的查询正是那些可定义的一阶诱导的线性深度，或等价地，那些可计算的线性时间上的并行机与多项式多处理器。此外，我们表明，RAG只使用合成属性是严格弱于RAG使用合成和继承的属性。我们表明，RAGs是更有表现力的一元二阶逻辑查询的任何arity。最后，我们讨论了BAGs和RAGs的上下文中的关系属性文法。我们表明，在BAGs的情况下，这并没有增加的表达能力，而不同的语义关系RAGs捕获的复杂性类NP，CONP和UP的COUP。
Structured document databases can be naturally viewed as derivation trees of a context-free grammar. Under this view, the classical formalism of attribute grammars becomes a formalism for structured document query languages. From this perspective, we study the expressive power of BAGs: Boolean-valued attribute grammars with propositional logic formulas as semantic rules, and RAGs: relation-valued attribute grammars with first-order logic formulas as semantic rules. BAGs can express only unary queries; RAGs can express queries of any arity. We first show that the (unary) queries expressible by BAGs are precisely those definable in monadic second-order logic. We then show that the queries expressible by RAGs are precisely those definable by first-order inductions of linear depth, or, equivalently, those computable in linear time on a parallel machine with polynomially many processors. Further, we show that RAGs that only use synthesized attributes are strictly weaker than RAGs that use both synthesized and inherited attributes. We show that RAGs are more expressive than monadic second-order logic for queries of any arity. Finally, we discuss relational attribute grammars in the context of BAGs and RAGs. We show that in the case of BAGs this does not increase the expressive power, while different semantics for relational RAGs capture the complexity classes NP, coNP and UP ∩ coUP.