DBScholar

Back to papers

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)

Paper ID
h8a4d29c58a395a59
Venue
PODS
Year
1998
Pagerank
5.7823766e-05
Overall Rank
6,446 | 56.67%
DOI
10.1145/275487.275489

Incoming Non-self Citations Over Time

Authors

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,315 DTD Inference for Views of XML Data 2000 PODS 0.00011058412
4,266 A Web Odyssey: from Codd to XML 2001 PODS 6.6972871e-05
6,445 Query Automata (extended abstract) 1999 PODS 5.7823766e-05
8,043 Extended Path Expressions for XML 2001 PODS 5.4011538e-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,021 Querying and Updating the File 1993 VLDB 0.0001243944
1,312 Mind Your Grammar: a New Approach to Modelling Text 1987 VLDB 0.0001106293
1,908 Automata Theory for Database Theoreticians 1989 PODS 9.3940283e-05
3,662 A Database Interface for File Update 1995 SIGMOD 7.1191086e-05
Previous Page 1 / 1 Next

Semantically Similar Papers