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: hd3bdd55d62b29e61
Venue: VLDB
Year: 2024
Pagerank: 4.9793485e-05
Overall Rank: 11,558 | 22.30%
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
9,951	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.1038322e-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
550	Synthesizing Independent Database Schemas	1979	SIGMOD	0.00016559635
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015699254
628	Database Relations with Null Values (Extended Abstract)	1982	PODS	0.0001544126
727	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014443394
1,971	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.2873596e-05
2,125	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB	9.0033119e-05
3,026	Functional Dependencies for Graphs	2016	SIGMOD	7.7387829e-05
3,475	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB	7.2707661e-05
4,067	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.8216078e-05
4,465	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	6.5873563e-05
4,843	Pattern Functional Dependencies for Data Cleaning	2020	VLDB	6.3839159e-05
5,130	Distributed implementations of dependency discovery algorithms	2019	VLDB	6.2603084e-05
5,798	Normalizing Property Graphs	2023	VLDB	5.9905343e-05
5,869	Leveraging Application Data Constraints to Optimize Database-Backed Web Applications	2023	VLDB	5.9648445e-05
6,910	Efficient Discovery of XML Data Redundancies	2006	VLDB	5.6486607e-05
9,016	Faster Plan Generation through Consideration of Functional Dependencies and Keys	2016	VLDB	5.2370694e-05
9,965	Composite Object Normal Forms: Parameterizing Boyce-Codd Normal Form by the Number of Minimal Keys	2023	SIGMOD	5.1038322e-05
9,967	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	5.1038322e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,480	Constant Time Maintenance or The Triumph of the fd.	1986	PODS
2	3,475	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB
3	10,377	Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations	2026	PODS
4	6,761	Propagating Functional Dependencies with Conditions	2008	VLDB
5	8,465	Independence-reducible Database Schemes	1988	PODS
6	10,028	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS
7	9,951	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,386	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD
9	9,958	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD
10	1,361	Computing Optimal Repairs for Functional Dependencies	2018	PODS