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.1029941e-05
Overall Rank: 2,055 | 86.23%
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,820	Supporting Executable Mappings in Model Management	2005	SIGMOD	9.5518912e-05
2,399	Query-Based Data Pricing	2012	PODS	8.5059294e-05
2,508	Compiling Mappings to Bridge Applications and Databases	2007	SIGMOD	8.3515858e-05
5,753	Capturing Missing Tuples and Missing Values	2010	PODS	5.9887721e-05
5,754	Relative Information Completeness	2009	PODS	5.9887721e-05
6,683	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.6941358e-05
6,769	Queries Determined by Views: Pack Your Views	2007	PODS	5.6693617e-05
11,730	Synthesizing Nested Relational Queries from Implicit Specifications	2023	PODS	4.9605343e-05
12,250	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS	4.9605343e-05
12,744	Completeness of Queries over Incomplete Databases	2011	VLDB	4.9605343e-05
12,937	Ontologies and Databases: myths and challenges	2008	VLDB	4.9605343e-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.00037421163
168	Query Transformation for PSJ-queries	1987	VLDB	0.00027117709
239	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023510465
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021612162
410	Semantic Data Caching and Replacement	1996	VLDB	0.00018751654
534	Answering Recursive Queries Using Views	1997	PODS	0.0001677412
2,043	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1266211e-05
2,241	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.7710222e-05
2,301	Querying Aggregate Data	1999	PODS	8.6620636e-05
3,169	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.557345e-05
3,630	Describing and Using Query Capabilities of Heterogeneous Sources	1997	VLDB	7.1283222e-05
3,811	Lossless Regular Views	2002	PODS	6.9889033e-05
4,246	On the Content of Materialized Aggregate Views	2000	PODS	6.694623e-05
5,516	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.0859896e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,516	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS
2	534	Answering Recursive Queries Using Views	1997	PODS
3	882	Rewriting Aggregate Queries Using Views	1999	PODS
4	72	Answering Queries Using Views (Extended Abstract)	1995	PODS
5	4,533	View-Based Query Containment	2003	PODS
6	6,769	Queries Determined by Views: Pack Your Views	2007	PODS
7	5,249	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
8	2,579	Rewriting Queries Using Views in Description Logics	1997	PODS
9	12,107	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS
10	12,373	Bounded Query Rewriting Using Views	2016	PODS