Querying Graph Patterns

Summary: Classifies graph patterns by features (node/label variables, regex edges) and gives tight data/combined complexity for standard graph queries, pinpointing features driving intractability and syntactic restrictions for tractability. Introduces a novel two-mode automata model (node-accepting vs path-accepting) for answering pattern queries, analyzes its algorithmic properties, and shows many hard cases can be cast as CSPs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hbebf24f096692f54
Venue: PODS
Year: 2011
Pagerank: 6.2506877e-05
Overall Rank: 5,122 | 65.67%
DOI: 10.1145/1989284.1989307

Incoming Non-self Citations Over Time

Authors

1. Pablo Barcelo (University of Chile)
2. Leonid Libkin (University of Edinburgh)
3. Juan Reutter (University of Edinburgh)

BibTeX Citation

@inproceedings{barcelo_pods11,
        address = {New York, NY, USA},
        series = {{PODS} '11},
        title = {{Querying Graph Patterns}},
        url = {https://dl.acm.org/doi/10.1145/1989284.1989307},
        doi = {10.1145/1989284.1989307},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Barcelo, Pablo and Libkin, Leonid and Reutter, Juan},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
719	Querying Graph Databases	2013	PODS	0.00014493767
2,251	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.7460227e-05
4,488	Schemaless and Structureless Graph Querying	2014	VLDB	6.5623564e-05
5,133	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	6.2458323e-05
9,884	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.1037285e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055201845
136	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00029636761
299	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00021766741
306	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00021533151
1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011777466
1,474	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010526746
1,606	Conjunctive Queries over Trees	2004	PODS	0.00010079487
2,782	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.0054142e-05
4,242	Foundations of Semantic Web Databases	2004	PODS	6.6984096e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,835	The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs	2022	PODS
2	12,440	Defining Relations on Graphs: How Hard is it in the Presence of Node Partitions?	2015	PODS
3	5,133	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS
4	4,568	Querying Big Graphs within Bounded Resources	2014	SIGMOD
5	11,941	Answering Regular Path Queries through Exemplars	2022	VLDB
6	288	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD
7	1,592	Finding Regular Simple Paths in Graph Databases	1989	VLDB
8	11,616	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB
9	1,474	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS
10	719	Querying Graph Databases	2013	PODS