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: 1547
Venue: PODS
Year: 2011
Pagerank: 6.4120976e-05
Overall Rank: 4,986 | 65.80%
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
747	Querying Graph Databases	2013	PODS	0.00014400452
2,285	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.8052998e-05
4,372	Schemaless and Structureless Graph Querying	2014	VLDB	6.7384384e-05
4,981	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	6.4127882e-05
9,665	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.2406724e-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
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
134	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00030343737
300	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00022046803
312	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00021733819
1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.0001206219
1,564	Conjunctive Queries over Trees	2004	PODS	0.00010349456
1,575	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010318258
2,718	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.209788e-05
4,139	Foundations of Semantic Web Databases	2004	PODS	6.8776612e-05

Semantically Similar Papers

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