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,326 | DTD Inference for Views of XML Data | 2000 | PODS | 0.0001101664 |
| 4,281 | A Web Odyssey: from Codd to XML | 2001 | PODS | 6.6721591e-05 |
| 6,460 | Query Automata (extended abstract) | 1999 | PODS | 5.7605327e-05 |
| 8,069 | Extended Path Expressions for XML | 2001 | PODS | 5.3807682e-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,026 | Querying and Updating the File | 1993 | VLDB | 0.00012393891 |
| 1,321 | Mind Your Grammar: a New Approach to Modelling Text | 1987 | VLDB | 0.0001102163 |
| 1,920 | Automata Theory for Database Theoreticians | 1989 | PODS | 9.3586444e-05 |
| 3,673 | A Database Interface for File Update | 1995 | SIGMOD | 7.0922969e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,708 | Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract) | 1994 | PODS |
| 2 | 8,094 | On the Expressiveness of Languages for Querying Property Graphs in Relational Databases | 2026 | PODS |
| 3 | 1,474 | Expressive Languages for Path Queries over Graph-Structured Data | 2010 | PODS |
| 4 | 3,039 | Expressive and efficient pattern languages for tree-structured data (extended abstract) | 2000 | PODS |
| 5 | 13,415 | Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations | 1992 | PODS |
| 6 | 2,522 | Towards Tractable Algebras for Bags (Extended Abstract) | 1993 | PODS |
| 7 | 9,647 | A Theory of Regular Queries | 2016 | PODS |
| 8 | 6,334 | Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract) | 2000 | PODS |
| 9 | 6,460 | Query Automata (extended abstract) | 1999 | PODS |
| 10 | 8,027 | New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions | 1994 | PODS |