An Efficient Index for RDF Query Containment

Summary: Proposes f-graph queries for polynomial RDF CQ containment. Introduces mv-index for fast containment of a query vs many stored queries; uses f-graph witnesses to extend to general CQs, enabling microsecond-scale containment across thousands of queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5677
Venue: SIGMOD
Year: 2019
Pagerank: 4.1905499e-05
Overall Rank: 11,662 | 18.95%
DOI: 10.1145/3299869.3319864

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,288	View Selection over Knowledge Graphs in Triple Stores	2021	VLDB	4.5392079e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
11	Implementing Data Cubes Efficiently	1996	SIGMOD	0.0011695087
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054430106
160	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00040053897
335	Optimization of Real Conjunctive Queries	1993	PODS	0.00027012705
444	Semantic Data Caching and Replacement	1996	VLDB	0.0002303513
530	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00020823189
587	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00019623493
625	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00018963452
657	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018581389
1,110	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD	0.00013902997
1,705	Column-Store Support for RDF Data Management: not all swans are white	2008	VLDB	0.00010809258
2,812	TriAD: A Distributed Shared-Nothing RDF Engine based on Asynchronous Message Passing	2014	SIGMOD	8.0825994e-05
2,920	x-RDF-3X: Fast Querying, High Update Rates, and Consistency for RDF Databases	2010	VLDB	7.8999781e-05
4,201	Static Analysis and Optimization of Semantic Web Queries	2012	PODS	6.3588034e-05
5,778	Graph-Aware, Workload-Adaptive SPARQL Query Caching	2015	SIGMOD	5.3274776e-05
7,758	Containment and Equivalence of Well-Designed SPARQL	2014	PODS	4.6554272e-05
8,248	View Selection in Semantic Web Databases	2012	VLDB	4.5453997e-05
8,395	GC: A Graph Caching System for Subgraph/Supergraph Queries	2018	VLDB	4.5214792e-05
11,844	Ontology-Based Integration of Streaming and Static Relational Data with Optique	2016	SIGMOD	4.1905499e-05
12,137	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
895	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00015498104
2,407	Scalable Join Processing on Very Large RDF Graphs	2009	SIGMOD	8.8702781e-05
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054430106
9,556	Materialized View Selection & View-Based Query Planning for Regular Path Queries	2024	SIGMOD	4.3212967e-05
2,199	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB	9.3082437e-05
869	An Efficient SQL-based RDF Querying Scheme	2005	VLDB	0.00015734541
8,762	Efficient Query Answering in Probabilistic RDF Graphs	2011	SIGMOD	4.4520434e-05
2,432	Towards Graph Containment Search and Indexing	2007	VLDB	8.8247178e-05
5,778	Graph-Aware, Workload-Adaptive SPARQL Query Caching	2015	SIGMOD	5.3274776e-05
351	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026351742