Designing a Query Language for RDF: Marrying Open and Closed Worlds

Summary: Proves that well-designed SPARQL ⊂ weakly-monotone but not conversely (even with disjunction), showing well-designedness cannot fully capture open-world-compatible queries. Introduces a new interpolation-based SPARQL operator yielding a larger syntactic weakly-monotone fragment (finite/infinite RDFs), gives a simple characterization of monotone CONSTRUCT queries, and settles evaluation complexity. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1692
Venue: PODS
Year: 2016
Pagerank: 5.4874656e-05
Overall Rank: 8,098 | 44.45%
DOI: 10.1145/2902251.2902298

Incoming Non-self Citations Over Time

Authors

1. Marcelo Arenas (Center for Semantic Web Research; Pontifical Catholic University of Chile)
2. Martín Ugarte (Free University of Brussels)

BibTeX Citation

@inproceedings{arenas_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Designing a Query Language for RDF: Marrying Open and Closed Worlds}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902298},
        doi = {10.1145/2902251.2902298},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Arenas, Marcelo and Ugarte, Martín},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,245	Certain Answers Meet Zero-One Laws	2018	PODS	6.3012734e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,176	Outerjoins as Disjunctions	1994	SIGMOD	0.00011809075
2,446	Querying Semantic Web Data with SPARQL	2011	PODS	8.5728114e-05
3,452	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	7.4007472e-05
3,463	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS	7.3921264e-05
3,556	Static Analysis and Optimization of Semantic Web Queries	2012	PODS	7.3113256e-05
5,832	Containment and Equivalence of Well-Designed SPARQL	2014	PODS	6.0733071e-05
7,565	Generating Low-cost Plans From Proofs	2014	PODS	5.5957787e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,682	Graph Data Models, Query Languages and Programming Paradigms	2018	VLDB
2	11,895	The Tractability Frontier of Well-designed SPARQL Queries	2018	PODS
3	1,575	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS
4	4,139	Foundations of Semantic Web Databases	2004	PODS
5	11,787	SPARQL Rewriting: Towards Desired Results	2020	SIGMOD
6	747	Querying Graph Databases	2013	PODS
7	5,832	Containment and Equivalence of Well-Designed SPARQL	2014	PODS
8	2,446	Querying Semantic Web Data with SPARQL	2011	PODS
9	3,556	Static Analysis and Optimization of Semantic Web Queries	2012	PODS
10	9,181	Expressive Languages for Querying the Semantic Web	2014	PODS