Armstrong databases for functional and inclusion dependencies |
| |
Authors: | Ronald Fagin Moshe Y. Vardi |
| |
Affiliation: | IBM Research Laboratory, San Jose, CA 95193, USA;Stanford University, Stanford, CA 94305, USA |
| |
Abstract: | An Armstrong database is a database that obeys precisely a given set of sentences (and their logical consequences) and no other sentences of a given type. It is shown that if the sentences of interest are inclusion dependencies and standard functional dependencies (functional dependencies for which the left-hand side is nonempty), then there is always an Armstrong database for each set of sentences. (An example of an inclusion dependency is the sentence that says that every is an .) If, however, the sentences of interest are inclusion dependencies and unrestricted functional dependencies, then there need not exist an Armstrong database. This result holds even if we allow only ‘full’ inclusion dependencies. Thus, a fairly sharp line is drawn, in a case of interest, as to when an Armstrong database must exist. These results hold whether we restrict our attention to finite databases (databases with a finite number of tuples), or whether we allow unrestricted databases. |
| |
Keywords: | Armstrong relation Armstrong database relational database functional dependency inclusion dependency direct product faithfulness logical consequence mathematical logic |
本文献已被 ScienceDirect 等数据库收录! |
|