Expressive and efficient pattern languages for tree-structured data (extended abstract)

Summary: Propose a SQL-like pattern language for trees that selects vertices by combining path-to-root regexes with expressive subtree predicates, and prove path-only languages cannot capture full MSO. Allowing a guarded fragment of MSO for subtree conditions yields MSO-equivalence while retaining efficient evaluability and practical usability. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1203
Venue: PODS
Year: 2000
Pagerank: 7.9147299e-05
Overall Rank: 2,969 | 79.64%
DOI: 10.1145/335168.335217

Incoming Non-self Citations Over Time

Authors

1. Frank Neven (Limburgs Universitair Centrum)
2. Thomas Schwentick (Johannes Gutenberg University Mainz)

BibTeX Citation

@inproceedings{neven_pods00,
        address = {New York, NY, USA},
        series = {{PODS} '00},
        title = {{Expressive and efficient pattern languages for tree-structured data (extended abstract)}},
        url = {https://dl.acm.org/doi/10.1145/335168.335217},
        doi = {10.1145/335168.335217},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Neven, Frank and Schwentick, Thomas},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.4878711e-05
2,180	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	9.0110009e-05
3,711	The Expressivity of XPath with Transitive Closure*	2006	PODS	7.1778094e-05
4,178	A Web Odyssey: from Codd to XML	2001	PODS	6.849218e-05
5,346	Running Tree Automata on Probabilistic XML	2009	PODS	6.257995e-05
7,876	Extended Path Expressions for XML	2001	PODS	5.5249028e-05
8,550	Conditional XPath, the first order complete XPath dialect*	2004	PODS	5.4119882e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,682	Graph Data Models, Query Languages and Programming Paradigms	2018	VLDB
2	3,463	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS
3	12,857	String Operations in Query Languages	2001	PODS
4	6,319	Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)	1998	PODS
5	1,575	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS
6	312	A Graphical Query Language Supporting Recursion	1987	SIGMOD
7	13,785	Monadic Datalog over Finite Structures with Bounded Treewidth	2007	PODS
8	6,184	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS
9	4,107	Processing Queries on Tree-Structured Data Efficiently	2006	PODS
10	7,622	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB