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: 5676
Venue: SIGMOD
Year: 2019
Pagerank: 4.1945683e-05
Overall Rank: 11,657 | 18.91%
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,295	View Selection over Knowledge Graphs in Triple Stores	2021	VLDB	4.5435639e-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.0011708144
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054402763
158	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00040071492
335	Optimization of Real Conjunctive Queries	1993	PODS	0.00027036073
442	Semantic Data Caching and Replacement	1996	VLDB	0.000230437
536	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00020722862
582	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00019723083
624	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00018988711
690	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018099792
1,112	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD	0.00013917776
1,706	Column-Store Support for RDF Data Management: not all swans are white	2008	VLDB	0.00010823026
2,803	TriAD: A Distributed Shared-Nothing RDF Engine based on Asynchronous Message Passing	2014	SIGMOD	8.0940362e-05
2,917	x-RDF-3X: Fast Querying, High Update Rates, and Consistency for RDF Databases	2010	VLDB	7.9063089e-05
4,251	Static Analysis and Optimization of Semantic Web Queries	2012	PODS	6.3235328e-05
5,771	Graph-Aware, Workload-Adaptive SPARQL Query Caching	2015	SIGMOD	5.3325981e-05
7,758	Containment and Equivalence of Well-Designed SPARQL	2014	PODS	4.6598957e-05
8,251	View Selection in Semantic Web Databases	2012	VLDB	4.5497619e-05
8,398	GC: A Graph Caching System for Subgraph/Supergraph Queries	2018	VLDB	4.5258186e-05
11,836	Ontology-Based Integration of Streaming and Static Relational Data with Optique	2016	SIGMOD	4.1945683e-05
12,129	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,553	View-Based Query Containment	2003	PODS	6.091702e-05
2,410	Scalable Join Processing on Very Large RDF Graphs	2009	SIGMOD	8.8773796e-05
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054402763
2,196	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB	9.3089621e-05
9,556	Materialized View Selection & View-Based Query Planning for Regular Path Queries	2024	SIGMOD	4.3254416e-05
872	An Efficient SQL-based RDF Querying Scheme	2005	VLDB	0.00015759968
8,765	Efficient Query Answering in Probabilistic RDF Graphs	2011	SIGMOD	4.456315e-05
2,438	Towards Graph Containment Search and Indexing	2007	VLDB	8.8214248e-05
5,771	Graph-Aware, Workload-Adaptive SPARQL Query Caching	2015	SIGMOD	5.3325981e-05
350	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026365067