Design by example for SQL table definitions with functional dependencies |
| |
Authors: | Sven Hartmann Markus Kirchberg Sebastian Link |
| |
Affiliation: | (1) Department of Informatics, Clausthal University of Technology, Clausthal-Zellerfeld, Germany;(2) Services Platform Lab, Hewlett-Packard Laboratories, Singapore, Singapore;(3) School of Information Management, Victoria University of Wellington, Wellington, New Zealand; |
| |
Abstract: | A database is C-Armstrong for a given set of constraints in a class C if it satisfies every constraint of the set and violates every constraint in C not implied by the set. Therefore, Armstrong databases are test data that perfectly illustrate the current perceptions about
the semantics of a schema. We extend the existing theory of Armstrong relations to a toolbox of Armstrong tables. That is,
we investigate structural and computational properties of Armstrong tables for the class of functional dependencies (FDs)
over SQL tables. Relations are special instances of SQL tables with no duplicate rows and no null value occurrences. While
FDs do not enjoy Armstrong tables, the combined class of standard FDs and NOT NULL constraints does enjoy Armstrong tables.
The problem of finding an Armstrong table is shown to be precisely exponential for this combined class. However, we establish
an algorithm that computes Armstrong tables with a size at most quadratic in that of a minimum-sized Armstrong table. Our
resulting toolbox of Armstrong tables can be applied by data engineers to concisely visualize constraints on SQL data. Such
support can lead to designs that guarantee efficient data management in practice. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|