Chasing Constrained Tuple-Generating Dependencies

Summary: Studies implication for constrained TGDs (CTGDs), introducing two chases: cautious (only justified tuples/constraints) and speculative (conditional tuples/constraints). Shows equivalence on domains with Independence of Negative Constraints, gives termination criteria, and adds magic-sets goal-directed optimization. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hb8316e95e05c9dbb
Venue: PODS
Year: 1996
Pagerank: 8.1764914e-05
Overall Rank: 2,647 | 82.21%
DOI: 10.1145/237661.237693

Incoming Non-self Citations Over Time

Authors

1. Michael J. Maher (Griffith University)
2. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{maher_pods96,
        address = {New York, NY, USA},
        series = {{PODS} '96},
        title = {{Chasing Constrained Tuple-Generating Dependencies}},
        url = {https://dl.acm.org/doi/10.1145/237661.237693},
        doi = {10.1145/237661.237693},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Maher, Michael J. and Srivastava, Divesh},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
500	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017280722
526	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.00016886621
1,291	Extending Dependencies with Conditions	2007	VLDB	0.00011156154
6,761	Propagating Functional Dependencies with Conditions	2008	VLDB	5.68869e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021220438
875	Queries Independent of Updates	1993	VLDB	0.00013316445
1,346	Independence of Logic Database Queries and Updates	1990	PODS	0.00010951176
6,864	A Decision Procedure for Conjunctive Query Disjointness	1989	PODS	5.6607227e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	41	Testing Implications Of Data Dependencies	1979	SIGMOD
2	11,477	Chase Termination Beyond Polynomial Time	2024	PODS
3	4,459	Semantic Query Optimization in the Presence of Types	2010	PODS
4	9,376	Non-Uniformly Terminating Chase: Size and Complexity	2022	PODS
5	10,115	Semantic Acyclicity Under Constraints	2016	PODS
6	4,445	Chase Termination for Guarded Existential Rules	2015	PODS
7	8,943	Chase Termination: A Constraints Rewriting Approach	2010	VLDB
8	3,322	On Chase Termination Beyond Stratification	2009	VLDB
9	11,892	Rewriting the Infinite Chase	2022	VLDB
10	12,053	All-Instances Restricted Chase Termination	2020	PODS