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.0001331025
Overall Rank: 875 | 94.13%
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.0003753293
84	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035960573
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021673683
699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014680086
1,052	Answering Queries Using Limited External Query Processors	1996	PODS	0.00012269616
1,109	A Formal Analysis of Information Disclosure in Data Exchange	2004	SIGMOD	0.00011981617
1,521	Constraint Checking with Partial Information	1994	PODS	0.00010374735
1,549	Data Warehouse Configuration	1997	VLDB	0.00010287654
1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5674072e-05
2,116	View Maintenance Issues for the Chronicle Data Model (Extended Abstract)	1995	PODS	9.0115434e-05
2,158	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9413031e-05
2,305	Query Flocks: A Generalization of Association-Rule Mining	1998	SIGMOD	8.6680992e-05
2,647	Chasing Constrained Tuple-Generating Dependencies	1996	PODS	8.1726842e-05
2,924	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8481787e-05
3,097	Query Containment for Data Integration Systems	2000	PODS	7.649698e-05
5,016	User-Defined Aggregate Functions: Bridging Theory and Practice	2006	SIGMOD	6.311544e-05
5,202	An Algebraic Approach to Rule Analysis in Expert Database Systems	1994	VLDB	6.2294873e-05
5,238	Implementation Strategies for Views over Property Graphs	2024	SIGMOD	6.2147408e-05
5,245	View Invalidation for Dynamic Content Caching in Multitiered Architectures	2002	VLDB	6.2125756e-05
5,592	Destabilizers and Independence of XML Updates	2010	VLDB	6.0708266e-05
5,740	Capturing Missing Tuples and Missing Values	2010	PODS	6.0085833e-05
5,741	Relative Information Completeness	2009	PODS	6.0085833e-05
5,888	Multiple-View Self-Maintenance in Data Warehousing Environments	1997	VLDB	5.9548035e-05
5,923	Scalable Query Result Caching for Web Applications	2008	VLDB	5.943996e-05
6,212	Efficient Detection of Empty-Result Queries	2006	VLDB	5.8469404e-05
6,233	The Impact of Virtual Views on Containment	2010	VLDB	5.8412765e-05
6,323	Containment of Nested XML Queries	2004	VLDB	5.8126093e-05
7,612	On Scale Independence for Querying Big Data	2014	PODS	5.4829143e-05
8,311	Maintaining XPath Views in Loosely Coupled Systems	2006	VLDB	5.356418e-05
8,722	Satisfiability and Relevance for Queries over Active Documents	2009	PODS	5.2880532e-05
8,910	InvaliDB: Scalable Push-Based Real-Time Queries on Top of Pull-Based Databases (Extended)	2020	VLDB	5.2534908e-05
12,528	On the Expressive Power of Update Primitives	2013	PODS	4.9769913e-05
12,982	Simultaneous Scalability and Security for Data-Intensive Web Applications	2006	SIGMOD	4.9769913e-05
13,018	A Scalability Service for Dynamic Web Applications	2005	CIDR	4.9769913e-05
13,280	Further Improvement on Integrity Constraint Checking for Stratifiable Deductive Databases	1996	VLDB	4.9769913e-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.00026648806
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021210493
642	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015236058
1,346	Independence of Logic Database Queries and Updates	1990	PODS	0.00010946011
2,477	Local Verification of Global Integrity Constraints in Distributed Databases	1993	SIGMOD	8.4067256e-05
3,887	Constraints and Redundancy in Datalog	1992	PODS	6.9428919e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,158	Obtaining Complete Answers from Incomplete Databases	1996	VLDB
2	13,272	Static Analysis of Intensional Databases in U-Datalog	1996	PODS
3	8,456	Schema-Based Independence Analysis for XML Updates	2009	VLDB
4	1,661	On the Decidability of Query Containment under Constraints	1998	PODS
5	317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS
6	5,592	Destabilizers and Independence of XML Updates	2010	VLDB
7	2,924	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