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: 1339
Venue: PODS
Year: 2005
Pagerank: 9.344653e-05
Overall Rank: 1,991 | 86.35%
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,770	Supporting Executable Mappings in Model Management	2005	SIGMOD	9.7967596e-05
2,342	Query-Based Data Pricing	2012	PODS	8.7217471e-05
2,464	Compiling Mappings to Bridge Applications and Databases	2007	SIGMOD	8.5480977e-05
5,616	Capturing Missing Tuples and Missing Values	2010	PODS	6.1493013e-05
5,617	Relative Information Completeness	2009	PODS	6.1493013e-05
6,542	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.8466322e-05
6,624	Queries Determined by Views: Pack Your Views	2007	PODS	5.8204482e-05
11,362	Synthesizing Nested Relational Queries from Implicit Specifications	2023	PODS	5.093636e-05
11,901	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS	5.093636e-05
12,404	Completeness of Queries over Incomplete Databases	2011	VLDB	5.093636e-05
12,599	Ontologies and Databases: myths and challenges	2008	VLDB	5.093636e-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
69	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00038090878
166	Query Transformation for PSJ-queries	1987	VLDB	0.00027676268
225	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00024101949
298	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00022138018
409	Semantic Data Caching and Replacement	1996	VLDB	0.00018985783
515	Answering Recursive Queries Using Views	1997	PODS	0.00017177428
2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.2348082e-05
2,189	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.9856333e-05
2,305	Querying Aggregate Data	1999	PODS	8.7766218e-05
3,103	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.7562264e-05
3,563	Describing and Using Query Capabilities of Heterogeneous Sources	1997	VLDB	7.3076984e-05
3,717	Lossless Regular Views	2002	PODS	7.1752078e-05
4,155	On the Content of Materialized Aggregate Views	2000	PODS	6.866935e-05
5,361	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.2484907e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,361	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS
2	515	Answering Recursive Queries Using Views	1997	PODS
3	869	Rewriting Aggregate Queries Using Views	1999	PODS
4	69	Answering Queries Using Views (Extended Abstract)	1995	PODS
5	4,445	View-Based Query Containment	2003	PODS
6	6,624	Queries Determined by Views: Pack Your Views	2007	PODS
7	5,146	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
8	2,527	Rewriting Queries Using Views in Description Logics	1997	PODS
9	11,754	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS
10	12,029	Bounded Query Rewriting Using Views	2016	PODS