Design by Example for SQL Tables with Functional Dependencies

An Armstrong relation satisfies the functional dependencies (FD) implied by a given FD set and violates all other FDs. Therefore, they form an instance of the design-by-example methodology: the example relation exhibits precisely those FDs that the current design perceives as meaningful for the appli-cation domain. The existing framework of Armstrong relations only applies to total relations. We investigate structural properties of Armstrong relations for FDs over SQL tables. That is, arbitrary attributes can be declared NOT NULL and null values apply Zaniolo’s most general no information interpre-tation. In contrast to total relations, FDs do not enjoy Armstrong relations. However, the class of standard FDs with arbitrary NOT NULL constraints does enjoy Armstrong relations. While the problem of finding an Armstrong relation is shown to be precisely exponential, we establish an algorithm that computes Arm-strong relations with a size at most quadratic in that of a minimum-sized Armstrong relation. Our results enable designers to make effective use of Armstrong relations for real SQL tables. This can lead to real world designs that guarantee efficient ways of data processing