On the finite and general implication problems of independence atoms and keys |
| |
Affiliation: | 1. Department of Mathematics and Statistics, University of Helsinki, Finland;2. Department of Computer Science, University of Auckland, New Zealand |
| |
Abstract: | We investigate implication problems for keys and independence atoms in relational databases. For keys and unary independence atoms we show that finite implication is not finitely axiomatizable, and establish a finite axiomatization for general implication. The same axiomatization is also sound and complete for finite and general implication of unary keys and independence atoms, which coincide. We show that the general implication of keys and unary independence atoms and of unary keys and general independence atoms is decidable in polynomial time. For these two classes we also show how to construct Armstrong relations. Finally, we establish tractable conditions that are sufficient for certain classes of keys and independence atoms not to interact. |
| |
Keywords: | Armstrong relation Axiomatization Dependence logic Finite implication Implication Independence Key |
本文献已被 ScienceDirect 等数据库收录! |
|