Queries Independent of Updates

Summary: Recasts query–update independence for recursive Datalog, under insertions and deletions, as program equivalence, clarifying its undecidability. Extends query-reachability and uniform-equivalence tests to order constraints and stratified negation. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hcdbd17be512c0f33
Venue: VLDB
Year: 1993
Pagerank: 0.00013316445
Overall Rank: 875 | 94.12%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Alon Y. Levy (Stanford University)
2. Yehoshua Sagiv (Hebrew University)

BibTeX Citation

@article{levy_vldb93,
        title = {{Queries Independent of Updates}},
        author = {Levy, Alon Y. and Sagiv, Yehoshua},
        journal = {PVLDB},
        series = {{VLDB} '93},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 35 of 35 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037549176
84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035963861
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021682744
699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014686953
1,052	Answering Queries Using Limited External Query Processors	1996	PODS	0.00012275281
1,109	A Formal Analysis of Information Disclosure in Data Exchange	2004	SIGMOD	0.00011987291
1,521	Constraint Checking with Partial Information	1994	PODS	0.00010379636
1,547	Data Warehouse Configuration	1997	VLDB	0.00010292395
1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5718481e-05
2,115	View Maintenance Issues for the Chronicle Data Model (Extended Abstract)	1995	PODS	9.0155433e-05
2,156	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9455055e-05
2,301	Query Flocks: A Generalization of Association-Rule Mining	1998	SIGMOD	8.6716957e-05
2,647	Chasing Constrained Tuple-Generating Dependencies	1996	PODS	8.1764914e-05
2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8518874e-05
3,095	Query Containment for Data Integration Systems	2000	PODS	7.6532922e-05
5,012	User-Defined Aggregate Functions: Bridging Theory and Practice	2006	SIGMOD	6.3145331e-05
5,201	An Algebraic Approach to Rule Analysis in Expert Database Systems	1994	VLDB	6.2324243e-05
5,233	Implementation Strategies for Views over Property Graphs	2024	SIGMOD	6.2176841e-05
5,240	View Invalidation for Dynamic Content Caching in Multitiered Architectures	2002	VLDB	6.215518e-05
5,591	Destabilizers and Independence of XML Updates	2010	VLDB	6.0737018e-05
5,739	Capturing Missing Tuples and Missing Values	2010	PODS	6.011429e-05
5,740	Relative Information Completeness	2009	PODS	6.011429e-05
5,888	Multiple-View Self-Maintenance in Data Warehousing Environments	1997	VLDB	5.9576002e-05
5,923	Scalable Query Result Caching for Web Applications	2008	VLDB	5.9468112e-05
6,208	Efficient Detection of Empty-Result Queries	2006	VLDB	5.8497045e-05
6,230	The Impact of Virtual Views on Containment	2010	VLDB	5.844043e-05
6,319	Containment of Nested XML Queries	2004	VLDB	5.8153622e-05
7,610	On Scale Independence for Querying Big Data	2014	PODS	5.4844912e-05
8,304	Maintaining XPath Views in Loosely Coupled Systems	2006	VLDB	5.3589548e-05
8,714	Satisfiability and Relevance for Queries over Active Documents	2009	PODS	5.2905577e-05
8,902	InvaliDB: Scalable Push-Based Real-Time Queries on Top of Pull-Based Databases (Extended)	2020	VLDB	5.2559789e-05
12,522	On the Expressive Power of Update Primitives	2013	PODS	4.9793485e-05
12,976	Simultaneous Scalability and Security for Data-Intensive Web Applications	2006	SIGMOD	4.9793485e-05
13,012	A Scalability Service for Dynamic Web Applications	2005	CIDR	4.9793485e-05
13,274	Further Improvement on Integrity Constraint Checking for Stratifiable Deductive Databases	1996	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.000266613
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021220438
642	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015243164
1,346	Independence of Logic Database Queries and Updates	1990	PODS	0.00010951176
2,474	Local Verification of Global Integrity Constraints in Distributed Databases	1993	SIGMOD	8.4106815e-05
3,886	Constraints and Redundancy in Datalog	1992	PODS	6.9461797e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,095	Query Containment for Data Integration Systems	2000	PODS
2	13,266	Static Analysis of Intensional Databases in U-Datalog	1996	PODS
3	8,447	Schema-Based Independence Analysis for XML Updates	2009	VLDB
4	1,660	On the Decidability of Query Containment under Constraints	1998	PODS
5	317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS
6	5,591	Destabilizers and Independence of XML Updates	2010	VLDB
7	2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS
8	177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS
9	2,716	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS
10	1,346	Independence of Logic Database Queries and Updates	1990	PODS