Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data

Summary: Generalized tree pattern queries (GTPQs) for graph-structured data, enabling full propositional logic of structural constraints. Efficient evaluation with a compact graph representation, join pruning, and a 3-hop reachability index; experiments show speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h30fcafa7ec2d595a
Venue: VLDB
Year: 2012
Pagerank: 5.4532403e-05
Overall Rank: 7,777 | 47.73%
DOI: 10.14778/2212351.2212355

Incoming Non-self Citations Over Time

Authors

1. Qiang Zeng (Institute of Computing Technology, Chinese Academy of Sciences)
2. Xiaorui Jiang (Institute of Computing Technology, Chinese Academy of Sciences)
3. Hai Zhuge (Institute of Computing Technology, Chinese Academy of Sciences)

BibTeX Citation

@article{zeng_vldb12,
        title = {{Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data}},
        author = {Zeng, Qiang and Jiang, Xiaorui and Zhuge, Hai},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {8},
        pages = {728--739},
        doi = {10.14778/2212351.2212355},
        url = {https://doi.org/10.14778/2212351.2212355},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,756	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	5.4570169e-05
10,243	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS	5.0519762e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
86	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00035793969
179	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026617591
274	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022480767
289	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021960834
294	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00021917638
453	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00017963727
784	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014015324
1,096	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012044781
1,150	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011804185
1,902	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.3999798e-05
2,733	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.0780747e-05
3,235	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB	7.4998307e-05
4,156	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.7712336e-05
4,386	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.6230198e-05
5,425	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD	6.1332823e-05
6,135	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	5.8749061e-05
7,641	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB	5.475997e-05
12,649	Comments on "Stack-based Algorithms for Pattern Matching on DAGs"	2012	VLDB	4.9769913e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,567	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB
2	6,135	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD
3	4,189	Processing Queries on Tree-Structured Data Efficiently	2006	PODS
4	1,599	Conjunctive Queries over Trees	2004	PODS
5	3,531	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS
6	3,636	Static Analysis and Optimization of Semantic Web Queries	2012	PODS
7	4,639	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
8	3,031	Expressive and efficient pattern languages for tree-structured data (extended abstract)	2000	PODS
9	3,235	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB
10	10,243	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS