Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/627
Title: Extensions of Attribute Grammars for Structured Document Queries
Authors: NEVEN, Frank 
Issue Date: 1999
Publisher: Springer-Verlag GmbH
Source: 7th International Workshop on Database Programming Languages: Research Issues in Structured and Semistructured Database Programming. p. 99-116
Series/Report: Lecture Notes in Computer Science
Series/Report no.: 1949
Abstract: Document specification languages like XML, model documents using extended context-free grammars. These differ from standard context-free grammars in that they allow arbitrary regular expressions on the right-hand side of productions. To query such documents, we introduce a new form of attribute grammars (extended AGs) that work directly over extended context-free grammars rather than over standard context-free grammars. Viewed as a query language, extended AGs are particularly relevant as they can take into account the inherent order of the children of a node in a document. We show that two key properties of standard attribute grammars carry over to extended AGs: efficiency of evaluation and decidability of well-definedness. We further characterize the expressiveness of extended AGs in terms of monadic second-order logic and establish the complexity of their non-emptiness and equivalence problem to be complete for EXPTIME. As an application we show that the Region Algebra expressions can be efficiently translated into extended AGs. This translation drastically improves the known upper bound on the complexity of the emptiness and equivalence test for Region Algebra expressions.
Document URI: http://hdl.handle.net/1942/627
ISBN: 3-540-41481-9
Type: Journal Contribution
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
09 extagfull.pdf518.59 kBAdobe PDFView/Open
Show full item record

Page view(s)

64
checked on May 15, 2022

Download(s)

172
checked on May 15, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.