Independence of Logic Database Queries and Updates

Summary: Defines a model-theoretic notion of query–update independence and proves basic properties under integrity constraints. Provides proof-theoretic conditions for conjunctive queries and an induction scheme to establish independence for recursive queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 896
Venue: PODS
Year: 1990
Pagerank: 0.00011182427
Overall Rank: 1,314 | 90.99%
DOI: 10.1145/298514.298557

Incoming Non-self Citations Over Time

Authors

1. Charles Elkan (University of Toronto)

BibTeX Citation

@inproceedings{elkan_pods90,
        address = {New York, NY, USA},
        series = {{PODS} '90},
        title = {{Independence of Logic Database Queries and Updates}},
        url = {https://dl.acm.org/doi/10.1145/298514.298557},
        doi = {10.1145/298514.298557},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Elkan, Charles},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
853	Queries Independent of Updates	1993	VLDB	0.00013587101
1,088	A Formal Analysis of Information Disclosure in Data Exchange	2004	SIGMOD	0.00012248135
1,489	Constraint Checking with Partial Information	1994	PODS	0.00010612225
2,117	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.1434045e-05
2,442	Local Verification of Global Integrity Constraints in Distributed Databases	1993	SIGMOD	8.5767117e-05
2,617	Chasing Constrained Tuple-Generating Dependencies	1996	PODS	8.3391085e-05
5,117	View Invalidation for Dynamic Content Caching in Multitiered Architectures	2002	VLDB	6.3581741e-05
5,616	Capturing Missing Tuples and Missing Values	2010	PODS	6.1493013e-05
5,617	Relative Information Completeness	2009	PODS	6.1493013e-05
11,820	InvaliDB: Scalable Push-Based Real-Time Queries on Top of Pull-Based Databases (Extended)	2020	VLDB	5.093636e-05
12,404	Completeness of Queries over Incomplete Databases	2011	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
39	Efficiently Updating Materialized Views	1986	SIGMOD	0.00047309646
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
1,361	Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates	1986	VLDB	0.00011037801
1,856	Automata Theory for Database Theoreticians	1989	PODS	9.6053834e-05
2,015	A Decidable Class of Bounded Recursions	1987	PODS	9.3047297e-05
2,028	A Procedural Semantics for Well Founded Negation in Logic Programs	1989	PODS	9.285972e-05
2,579	Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract)	1989	PODS	8.3906191e-05
3,730	Safety and Correct Translation of Relational Calculus Formulas	1987	PODS	7.1668598e-05
4,718	Solving the Phantom Problem by Predicative Optimistic Concurrency Control	1983	VLDB	6.5468872e-05
6,731	A Decision Procedure for Conjunctive Query Disjointness	1989	PODS	5.7885617e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,161	On the Equivalence of Logical Databases	1984	PODS
2	2,117	Obtaining Complete Answers from Incomplete Databases	1996	VLDB
3	12,992	Applying an update method to a set of receivers (extended abstract)	1995	PODS
4	6,153	Independent and Separable Database Schemes	1983	PODS
5	874	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
6	33	Consistent Query Answers in Inconsistent Databases	1999	PODS
7	1,173	Data Independent Recursion in Deductive Databases	1986	PODS
8	8,279	Schema-Based Independence Analysis for XML Updates	2009	VLDB
9	13,184	Independent Database Schemes Under Functional and Inclusion Dependencies	1987	VLDB
10	853	Queries Independent of Updates	1993	VLDB