Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)
Summary: Treats structured documents as CFG derivation trees and models query languages via attribute grammars: BAGS (Boolean/propositional rules) captures exactly unary MSO-definable queries. RAGS (relation-valued/FO rules) capture FO inductions of linear depth — equivalently linear-time parallel computable — and strictly exceed MSO for higher-arity queries. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Frank Neven (Limburgs Universitair Centrum)
- 2. Jan Van den Bussche (Limburgs Universitair Centrum)
BibTeX Citation
@inproceedings{neven_pods98,
address = {New York, NY, USA},
series = {{PODS} '98},
title = {{Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)}},
url = {https://dl.acm.org/doi/10.1145/275487.275489},
doi = {10.1145/275487.275489},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Neven, Frank and Van den Bussche, Jan},
year = {1998}
}
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,290 | DTD Inference for Views of XML Data | 2000 | PODS | 0.00011312135 |
| 4,178 | A Web Odyssey: from Codd to XML | 2001 | PODS | 6.849218e-05 |
| 6,318 | Query Automata (extended abstract) | 1999 | PODS | 5.9150511e-05 |
| 7,876 | Extended Path Expressions for XML | 2001 | PODS | 5.5249028e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 4 of 4 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,001 | Querying and Updating the File | 1993 | VLDB | 0.00012714843 |
| 1,289 | Mind Your Grammar: a New Approach to Modelling Text | 1987 | VLDB | 0.00011314 |
| 1,856 | Automata Theory for Database Theoreticians | 1989 | PODS | 9.6053834e-05 |
| 3,588 | A Database Interface for File Update | 1995 | SIGMOD | 7.281669e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,563 | Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract) | 1994 | PODS |
| 2 | 10,178 | On the Expressiveness of Languages for Querying Property Graphs in Relational Databases | 2026 | PODS |
| 3 | 1,575 | Expressive Languages for Path Queries over Graph-Structured Data | 2010 | PODS |
| 4 | 2,969 | Expressive and efficient pattern languages for tree-structured data (extended abstract) | 2000 | PODS |
| 5 | 13,078 | Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations | 1992 | PODS |
| 6 | 2,461 | Towards Tractable Algebras for Bags (Extended Abstract) | 1993 | PODS |
| 7 | 9,430 | A Theory of Regular Queries | 2016 | PODS |
| 8 | 6,184 | Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract) | 2000 | PODS |
| 9 | 6,318 | Query Automata (extended abstract) | 1999 | PODS |
| 10 | 7,849 | New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions | 1994 | PODS |