Mixed covers: optimizing updates and queries using minimal keys and functional dependencies
Open Access
- 17 March 2025
- journal article
- research article
- Published by Springer Nature in The VLDB Journal
- Vol. 34 (3) , 1-27
Abstract
Covers for a set of functional dependencies (FDs) are fundamental for many areas of data management, such as integrity maintenance, query optimization, database design, and data cleaning. When declaring integrity constraints, keys enjoy native support in database systems while FDs need to be enforced by triggers or at application level. Consequently, maximizing the use of keys will provide the best support. We propose the new notion of mixed cover for a set of FDs, comprising the set of minimal keys together with a cover for the set of non-key FDs implied by the FD set. We establish sequential and parallel algorithms for computing mixed covers from a given set of FDs, and illustrate that they complement each other in terms of their performance. Even though FD covers are typically smaller in number or size than their corresponding mixed cover, the latter generate orders of magnitude lower overheads during integrity maintenance. We also quantify how mixed covers improve the performance of query, refresh and insert operations on the TPC-H benchmark under different constraint workloads and scaling factors. Finally, we illustrate the growth of performance improvement for optimal over minimal-reduced covers, justifying the significant time required for computing the former.Keywords
Funding Information
- Marsden Fund (MFP-UOA2420)
This publication has 47 references indexed in Scilit:
- Data Profiling2019
- Efficient generation of query plans containing group-by, join, and groupjoinThe VLDB Journal, 2017
- Optimal covers in the relational database modelActa Informatica, 2015
- Incomplete Data and Data Dependencies in Relational Databases2012
- Design by example for SQL table definitions with functional dependenciesThe VLDB Journal, 2011
- Relational Database Index Design and the Optimizers2005
- A Guided Tour of Relational Databases and Beyond1999
- Dependencies in Relational Databases1991
- The theory of data dependencies — An overview1984
- On the relationship of minimum and optimum covers for a set of functional dependenciesActa Informatica, 1983