Views and Queries: Determinacy and Rewriting

Summary: Introduces information-theoretic view determinacy (when a set of views V uniquely fixes the answer to a query Q) and studies rewritability of Q from V. Analyzes decidability across FO-to-CQ fragments and the minimal expressive power needed for complete rewriting languages, with implications for semantic caching and privacy. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hedf8196b72eea825
Venue: PODS
Year: 2005
Pagerank: 9.137464e-05
Overall Rank: 2,044 | 86.26%
DOI: 10.1145/1065167.1065174

Incoming Non-self Citations Over Time

Authors

1. Luc Segoufin (INRIA; University of Paris)
2. Victor Vianu (University of California San Diego)

BibTeX Citation

@inproceedings{segoufin_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{Views and Queries: Determinacy and Rewriting}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065174},
        doi = {10.1145/1065167.1065174},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Segoufin, Luc and Vianu, Victor},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,811	Supporting Executable Mappings in Model Management	2005	SIGMOD	9.5872249e-05
2,387	Query-Based Data Pricing	2012	PODS	8.5381364e-05
2,498	Compiling Mappings to Bridge Applications and Databases	2007	SIGMOD	8.3830999e-05
5,739	Capturing Missing Tuples and Missing Values	2010	PODS	6.011429e-05
5,740	Relative Information Completeness	2009	PODS	6.011429e-05
6,666	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.7157324e-05
6,744	Queries Determined by Views: Pack Your Views	2007	PODS	5.6908598e-05
11,678	Synthesizing Nested Relational Queries from Implicit Specifications	2023	PODS	4.9793485e-05
12,201	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS	4.9793485e-05
12,695	Completeness of Queries over Incomplete Databases	2011	VLDB	4.9793485e-05
12,889	Ontologies and Databases: myths and challenges	2008	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037549176
167	Query Transformation for PSJ-queries	1987	VLDB	0.00027190004
238	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023591683
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021682744
416	Semantic Data Caching and Replacement	1996	VLDB	0.00018658244
532	Answering Recursive Queries Using Views	1997	PODS	0.0001682881
2,041	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1421879e-05
2,226	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.8033052e-05
2,289	Querying Aggregate Data	1999	PODS	8.6891266e-05
3,155	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.5858519e-05
3,620	Describing and Using Query Capabilities of Heterogeneous Sources	1997	VLDB	7.1548155e-05
3,799	Lossless Regular Views	2002	PODS	7.015401e-05
4,232	On the Content of Materialized Aggregate Views	2000	PODS	6.7145949e-05
5,492	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.1086968e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,492	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS
2	532	Answering Recursive Queries Using Views	1997	PODS
3	880	Rewriting Aggregate Queries Using Views	1999	PODS
4	72	Answering Queries Using Views (Extended Abstract)	1995	PODS
5	4,514	View-Based Query Containment	2003	PODS
6	6,744	Queries Determined by Views: Pack Your Views	2007	PODS
7	5,226	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
8	2,574	Rewriting Queries Using Views in Description Logics	1997	PODS
9	12,057	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS
10	12,324	Bounded Query Rewriting Using Views	2016	PODS