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: hffe992f3cff5fb1c
Venue: PODS
Year: 2000
Pagerank: 7.7374426e-05
Overall Rank: 3,030 | 79.63%
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,976	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.2797174e-05
2,223	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	8.8092332e-05
3,795	The Expressivity of XPath with Transitive Closure*	2006	PODS	7.0167646e-05
4,266	A Web Odyssey: from Codd to XML	2001	PODS	6.6972871e-05
5,474	Running Tree Automata on Probabilistic XML	2009	PODS	6.1176063e-05
8,043	Extended Path Expressions for XML	2001	PODS	5.4011538e-05
8,717	Conditional XPath, the first order complete XPath dialect*	2004	PODS	5.2905577e-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	8,831	Graph Data Models, Query Languages and Programming Paradigms	2018	VLDB
2	3,531	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS
3	13,147	String Operations in Query Languages	2001	PODS
4	6,446	Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)	1998	PODS
5	1,468	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS
6	305	A Graphical Query Language Supporting Recursion	1987	SIGMOD
7	14,096	Monadic Datalog over Finite Structures with Bounded Treewidth	2007	PODS
8	6,318	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS
9	4,189	Processing Queries on Tree-Structured Data Efficiently	2006	PODS
10	7,768	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB