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.0001326705
Overall Rank: 878 | 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.00037421163
85	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035848027
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021612162
703	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014638214
1,057	Answering Queries Using Limited External Query Processors	1996	PODS	0.00012235875
1,113	A Formal Analysis of Information Disclosure in Data Exchange	2004	SIGMOD	0.00011942006
1,522	Constraint Checking with Partial Information	1994	PODS	0.00010341308
1,550	Data Warehouse Configuration	1997	VLDB	0.00010257652
1,827	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5417632e-05
2,133	View Maintenance Issues for the Chronicle Data Model (Extended Abstract)	1995	PODS	8.9830012e-05
2,166	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9171951e-05
2,317	Query Flocks: A Generalization of Association-Rule Mining	1998	SIGMOD	8.6398664e-05
2,652	Chasing Constrained Tuple-Generating Dependencies	1996	PODS	8.1495688e-05
2,937	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8226419e-05
3,103	Query Containment for Data Integration Systems	2000	PODS	7.6298414e-05
5,028	User-Defined Aggregate Functions: Bridging Theory and Practice	2006	SIGMOD	6.2956973e-05
5,226	An Algebraic Approach to Rule Analysis in Expert Database Systems	1994	VLDB	6.2089519e-05
5,259	Implementation Strategies for Views over Property Graphs	2024	SIGMOD	6.194191e-05
5,266	View Invalidation for Dynamic Content Caching in Multitiered Architectures	2002	VLDB	6.1920335e-05
5,607	Destabilizers and Independence of XML Updates	2010	VLDB	6.0507527e-05
5,753	Capturing Missing Tuples and Missing Values	2010	PODS	5.9887721e-05
5,754	Relative Information Completeness	2009	PODS	5.9887721e-05
5,902	Multiple-View Self-Maintenance in Data Warehousing Environments	1997	VLDB	5.9359247e-05
5,936	Scalable Query Result Caching for Web Applications	2008	VLDB	5.9248452e-05
6,224	Efficient Detection of Empty-Result Queries	2006	VLDB	5.828372e-05
6,244	The Impact of Virtual Views on Containment	2010	VLDB	5.8219706e-05
6,333	Containment of Nested XML Queries	2004	VLDB	5.7933985e-05
7,628	On Scale Independence for Querying Big Data	2014	PODS	5.4649494e-05
8,325	Maintaining XPath Views in Loosely Coupled Systems	2006	VLDB	5.3387063e-05
8,742	Satisfiability and Relevance for Queries over Active Documents	2009	PODS	5.2705676e-05
8,930	InvaliDB: Scalable Push-Based Real-Time Queries on Top of Pull-Based Databases (Extended)	2020	VLDB	5.2361195e-05
12,571	On the Expressive Power of Update Primitives	2013	PODS	4.9605343e-05
13,024	Simultaneous Scalability and Security for Data-Intensive Web Applications	2006	SIGMOD	4.9605343e-05
13,060	A Scalability Service for Dynamic Web Applications	2005	CIDR	4.9605343e-05
13,321	Further Improvement on Integrity Constraint Checking for Stratifiable Deductive Databases	1996	VLDB	4.9605343e-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
179	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00026563438
319	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021142713
645	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015188342
1,355	Independence of Logic Database Queries and Updates	1990	PODS	0.00010910619
2,487	Local Verification of Global Integrity Constraints in Distributed Databases	1993	SIGMOD	8.3794349e-05
3,898	Constraints and Redundancy in Datalog	1992	PODS	6.9199453e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,166	Obtaining Complete Answers from Incomplete Databases	1996	VLDB
2	13,313	Static Analysis of Intensional Databases in U-Datalog	1996	PODS
3	8,471	Schema-Based Independence Analysis for XML Updates	2009	VLDB
4	1,667	On the Decidability of Query Containment under Constraints	1998	PODS
5	319	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS
6	5,607	Destabilizers and Independence of XML Updates	2010	VLDB
7	2,937	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS
8	179	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS
9	2,727	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS
10	1,355	Independence of Logic Database Queries and Updates	1990	PODS