Redundant Relations in Relational Databases: A Model Theoretic Perspective

Abstract: We initiate in this work the study of a sort of redundancy problem revealed by what we call redundant relations. Roughly, we define a redundant relation in a database instance (dbi) as a k-ary relation R such that there is a first-order query which evaluated in the reduced dbi, (i.e., the dbi without the redundant relation R) gives us R. So, given that first-order types are isomorphism types on finite structures, we can eliminate that relation R as long as the equivalence classes of the relation of equality of the first-order types for all k-tuples in the dbi are not altered. It turns out that in a fixed dbi, the problem of deciding whether a given relation in the dbi is redundant is decidable, though intractable, as well as the problem of deciding whether there is any relation symbol in the schema which is a redundant relation in the given dbi. We then study redundant relations with a restricted notion of equivalence so that the problem becomes tractable