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: h94d90f6ad1b187e4
Venue: PODS
Year: 1990
Pagerank: 0.00010946011
Overall Rank: 1,346 | 90.96%
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
875	Queries Independent of Updates	1993	VLDB	0.0001331025
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
2,158	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9413031e-05
2,477	Local Verification of Global Integrity Constraints in Distributed Databases	1993	SIGMOD	8.4067256e-05
2,647	Chasing Constrained Tuple-Generating Dependencies	1996	PODS	8.1726842e-05
5,245	View Invalidation for Dynamic Content Caching in Multitiered Architectures	2002	VLDB	6.2125756e-05
5,740	Capturing Missing Tuples and Missing Values	2010	PODS	6.0085833e-05
5,741	Relative Information Completeness	2009	PODS	6.0085833e-05
8,910	InvaliDB: Scalable Push-Based Real-Time Queries on Top of Pull-Based Databases (Extended)	2020	VLDB	5.2534908e-05
12,701	Completeness of Queries over Incomplete Databases	2011	VLDB	4.9769913e-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.00046583225
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00026648806
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021210493
1,393	Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates	1986	VLDB	0.00010801562
1,910	Automata Theory for Database Theoreticians	1989	PODS	9.3895837e-05
2,064	A Decidable Class of Bounded Recursions	1987	PODS	9.0931389e-05
2,079	A Procedural Semantics for Well Founded Negation in Logic Programs	1989	PODS	9.0743477e-05
2,631	Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract)	1989	PODS	8.2007667e-05
3,818	Safety and Correct Translation of Relational Calculus Formulas	1987	PODS	7.0037477e-05
4,812	Solving the Phantom Problem by Predicative Optimistic Concurrency Control	1983	VLDB	6.4030883e-05
6,868	A Decision Procedure for Conjunctive Query Disjointness	1989	PODS	5.6580483e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,227	On the Equivalence of Logical Databases	1984	PODS
2	2,158	Obtaining Complete Answers from Incomplete Databases	1996	VLDB
3	13,288	Applying an update method to a set of receivers (extended abstract)	1995	PODS
4	6,284	Independent and Separable Database Schemes	1983	PODS
5	897	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,201	Data Independent Recursion in Deductive Databases	1986	PODS
8	8,456	Schema-Based Independence Analysis for XML Updates	2009	VLDB
9	13,480	Independent Database Schemes Under Functional and Inclusion Dependencies	1987	VLDB
10	875	Queries Independent of Updates	1993	VLDB