Constraint Checking with Partial Information

Summary: Techniques for assuring integrity constraints without full evaluation, exploiting three information regimes: constraints alone; constraints+updates; constraints+updates+local data. Characterizes cost vs. soundness/precision tradeoffs to enable incremental, distributed, lightweight checking. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h2931ec8897ae6bb2
Venue: PODS
Year: 1994
Pagerank: 0.00010341308
Overall Rank: 1,522 | 89.80%
DOI: 10.1145/182591.182597

Incoming Non-self Citations Over Time

Authors

1. Ashish Gupta (Stanford University)
2. Yehoshua Sagiv (Hebrew University; Stanford University)
3. Jeffrey D. Ullman (Stanford University)
4. Jennifer Widom (Stanford University)

BibTeX Citation

@inproceedings{gupta_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{Constraint Checking with Partial Information}},
        url = {https://dl.acm.org/doi/10.1145/182591.182597},
        doi = {10.1145/182591.182597},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gupta, Ashish and Sagiv, Yehoshua and Ullman, Jeffrey D. and Widom, Jennifer},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
917	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013054852
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,667	On the Decidability of Query Containment under Constraints	1998	PODS	9.922321e-05
1,827	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5417632e-05
1,833	Adapting Materialized Views after Redefinitions	1995	SIGMOD	9.532574e-05
3,103	Query Containment for Data Integration Systems	2000	PODS	7.6298414e-05
5,266	View Invalidation for Dynamic Content Caching in Multitiered Architectures	2002	VLDB	6.1920335e-05
5,480	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	6.0991082e-05
5,516	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.0859896e-05
5,902	Multiple-View Self-Maintenance in Data Warehousing Environments	1997	VLDB	5.9359247e-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,871	Interactive Source Registration in Community-oriented Information Integration	2008	VLDB	5.4199943e-05
9,166	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.2031263e-05
13,321	Further Improvement on Integrity Constraint Checking for Stratifiable Deductive Databases	1996	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
246	Deriving Production Rules for Incremental View Maintenance	1991	VLDB	0.00023146423
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
878	Queries Independent of Updates	1993	VLDB	0.0001326705
1,355	Independence of Logic Database Queries and Updates	1990	PODS	0.00010910619
1,377	Deriving Production Rules for Constraint Maintenance	1990	VLDB	0.00010857402
2,487	Local Verification of Global Integrity Constraints in Distributed Databases	1993	SIGMOD	8.3794349e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	87	Implementation of Integrity Constraints and Views by Query Modification	1975	SIGMOD
2	6,282	Integrity Constraint Reformulation for Efficient Validation	1987	VLDB
3	33	Consistent Query Answers in Inconsistent Databases	1999	PODS
4	13,321	Further Improvement on Integrity Constraint Checking for Stratifiable Deductive Databases	1996	VLDB
5	2,487	Local Verification of Global Integrity Constraints in Distributed Databases	1993	SIGMOD
6	9,456	The Role of Integrity Constraints in Database Interoperation	1996	VLDB
7	4,194	Formal Limits on the Automatic Generation and Maintenance of Integrity Constraints	1987	PODS
8	13,331	Enhancing Database Correctness: A Statistical Approach	1995	SIGMOD
9	2,651	Knowledge-based Integrity Constraint Validation	1986	VLDB
10	8,702	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB