View Selection over Knowledge Graphs in Triple Stores

Summary: Scalable view selection for billion-triple stores and million-query workloads via subgraph-pattern mining and workload summarization. Casting selection as monotone submodular knapsack maximization yields a (1−1/e)-approximation; DbPedia rewrites accelerate 67.68% of queries to 2.19% of baseline time. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hc101553969a3b469
Venue: VLDB
Year: 2021
Pagerank: 5.2880532e-05
Overall Rank: 8,704 | 41.50%
DOI: 10.14778/3484224.3484227
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Theofilos Mailis (Athena Research Center; National & Kapodistrian University of Athens)
2. Yannis Kotidis (Athens University of Economics and Business)
3. Stamatis Christoforidis (National & Kapodistrian University of Athens)
4. Evgeny Kharlamov (Bosch Center for AI; University of Oslo)
5. Yannis Ioannidis (Athena Research Center; National & Kapodistrian University of Athens)

BibTeX Citation

@article{mailis_vldb21,
        title = {{View Selection over Knowledge Graphs in Triple Stores}},
        author = {Mailis, Theofilos and Kotidis, Yannis and Christoforidis, Stamatis and Kharlamov, Evgeny and Ioannidis, Yannis},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {13},
        pages = {3281--3294},
        doi = {10.14778/3484224.3484227},
        url = {https://doi.org/10.14778/3484224.3484227},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,741	Love-at-First-Sight: First Answers Without the Awkward Silence in Big Knowledge Graphs	2026	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 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.00071056708
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.0003753293
88	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00035340164
129	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.00030395767
512	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017053842
540	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.0001671863
557	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00016489266
923	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD	0.00013059066
1,132	Efficient Exploitation of Similar Subexpressions for Query Processing	2007	SIGMOD	0.00011893781
1,549	Data Warehouse Configuration	1997	VLDB	0.00010287654
1,598	Column-Store Support for RDF Data Management: not all swans are white	2008	VLDB	0.00010116183
1,747	Selecting Subexpressions to Materialize at Datacenter Scale	2018	VLDB	9.7303647e-05
2,343	TriAD: A Distributed Shared-Nothing RDF Engine based on Asynchronous Message Passing	2014	SIGMOD	8.6030486e-05
2,722	x-RDF-3X: Fast Querying, High Update Rates, and Consistency for RDF Databases	2010	VLDB	8.0926355e-05
3,215	Efficient and Provable Multi-Query Optimization	2017	PODS	7.5233633e-05
3,392	A Formal Perspective on the View Selection Problem	2001	VLDB	7.3448437e-05
3,544	Computation Reuse in Analytics Job Service at Microsoft	2018	SIGMOD	7.2108612e-05
5,847	Graph-Aware, Workload-Adaptive SPARQL Query Caching	2015	SIGMOD	5.9701747e-05
6,124	Approximate Distinct Counts for Billions of Datasets	2019	SIGMOD	5.8769926e-05
8,026	Obi-Wan: Ontology-Based RDF Integration of Heterogeneous Data	2020	VLDB	5.4030109e-05
8,319	View Selection in Semantic Web Databases	2012	VLDB	5.3546235e-05
12,158	An Efficient Index for RDF Query Containment	2019	SIGMOD	4.9769913e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,277	G-View: View Management for Graph Databases	2025	VLDB
2	3,260	On the Complexity of the View-Selection Problem	1999	PODS
3	8,568	Materialized View Selection for XQuery Workloads	2012	SIGMOD
4	9,593	Materializing Views with Minimal Size To Answer Queries	2003	PODS
5	3,392	A Formal Perspective on the View Selection Problem	2001	VLDB
6	923	Materialized View Selection and Maintenance Using Multi-Query Optimization	2001	SIGMOD
7	6,227	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD
8	2,561	Answering Top-k Queries Using Views	2006	VLDB
9	9,149	Materialized View Selection & View-Based Query Planning for Regular Path Queries	2024	SIGMOD
10	8,319	View Selection in Semantic Web Databases	2012	VLDB