Dependency preserving refinements and the fundamental problem of database design

摘要

We introduce a new point of view into database schemes by applying systematically an old logical technique: translation schemes, and their induced formula and structure transformations. This allows us to re-examine the notion of dependency preserving decomposition and its generalization refinement. We demonstrate the usefulness of this approach by recasting the theory of vertical and horizontal decompositions in our terminology. The most important aspect of this approach, however, lies in laying the groundwork for a formulation of the Fundamental Problem of Database Design, namely to exhibit desirable differences between translation equivalent presentations of data and to examine refinements of data presentations in a systematic way. The emphasis in this paper is not on results. The main line of thought is an exploration of the use of an old logical tool in addressing the Fundamental Problem. Translation schemes allow us also to have a new look at normal forms of database schemes and to suggest a new line of search for other normal forms. Illustrating our techniques we show that every scheme specified by functional and inclusion dependencies has a dependency-preserving refinement into BCNF. Furthermore we give a characterization of the embedded implicational dependencies (EID's) using FD's and inclusion dependencies (ID's) and a basic class of refinements consisting of projections and natural joins.