Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates

Summary: Presents the mixed cover: minimal keys plus a cover for non-key FDs to exploit native key support and minimize trigger/application enforcement. Provides sequential and parallel algorithms and demonstrates orders-of-magnitude lower integrity-maintenance overhead and TPC-H update/query gains. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13587
Venue: VLDB
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,221 | 23.02%
DOI: 10.14778/3654621.3654626

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Zhuoxing Zhang (University of Auckland)
2. Sebastian Link (University of Auckland)

BibTeX Citation

@article{zhang_vldb24,
        title = {{Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates}},
        author = {Zhang, Zhuoxing and Link, Sebastian},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {7},
        pages = {1578--1590},
        doi = {10.14778/3654621.3654626},
        url = {https://doi.org/10.14778/3654621.3654626},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,781	Synthesizing Third Normal Form Schemata that Minimize Integrity Maintenance and Update Overheads: Parameterizing 3NF by the Numbers of Minimal Keys and Functional Dependencies	2025	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
540	Synthesizing Independent Database Schemas	1979	SIGMOD	0.0001686137
613	Database Relations with Null Values (Extended Abstract)	1982	PODS	0.00015723523
618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015711835
729	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014539421
1,955	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.4166032e-05
2,123	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB	9.1372798e-05
2,973	Functional Dependencies for Graphs	2016	SIGMOD	7.9083516e-05
3,609	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB	7.2602055e-05
4,454	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	6.6929626e-05
4,757	Pattern Functional Dependencies for Data Cleaning	2020	VLDB	6.5220005e-05
5,052	Distributed implementations of dependency discovery algorithms	2019	VLDB	6.3846183e-05
5,611	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.1504635e-05
5,690	Normalizing Property Graphs	2023	VLDB	6.1205402e-05
6,771	Efficient Discovery of XML Data Redundancies	2006	VLDB	5.7783105e-05
8,856	Faster Plan Generation through Consideration of Functional Dependencies and Keys	2016	VLDB	5.3572468e-05
9,561	Leveraging Application Data Constraints to Optimize Database-Backed Web Applications	2023	VLDB	5.2528121e-05
11,379	Composite Object Normal Forms: Parameterizing Boyce-Codd Normal Form by the Number of Minimal Keys	2023	SIGMOD	5.093636e-05
11,688	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,351	Constant Time Maintenance or The Triumph of the fd.	1986	PODS
2	3,609	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB
3	10,160	Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations	2026	PODS
4	6,639	Propagating Functional Dependencies with Conditions	2008	VLDB
5	8,297	Independence-reducible Database Schemes	1988	PODS
6	9,845	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS
7	10,781	Synthesizing Third Normal Form Schemata that Minimize Integrity Maintenance and Update Overheads: Parameterizing 3NF by the Numbers of Minimal Keys and Functional Dependencies	2025	SIGMOD
8	6,332	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD
9	9,780	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD
10	1,399	Computing Optimal Repairs for Functional Dependencies	2018	PODS