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.2743507e-05
Overall Rank: 5,096 | 65.74%
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.00014529156
2,235	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.7779518e-05
4,466	Schemaless and Structureless Graph Querying	2014	VLDB	6.5872459e-05
5,109	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	6.2695208e-05
9,840	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.1230858e-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.00055043581
136	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00029740459
297	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00021840374
305	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.0002159111
1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011809728
1,468	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010566509
1,599	Conjunctive Queries over Trees	2004	PODS	0.00010117703
2,773	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.0351713e-05
4,222	Foundations of Semantic Web Databases	2004	PODS	6.7237398e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,811	The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs	2022	PODS
2	12,391	Defining Relations on Graphs: How Hard is it in the Presence of Node Partitions?	2015	PODS
3	5,109	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS
4	4,551	Querying Big Graphs within Bounded Resources	2014	SIGMOD
5	11,891	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,597	Finding Regular Simple Paths in Graph Databases	1989	VLDB
8	11,561	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB
9	1,468	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS
10	719	Querying Graph Databases	2013	PODS