Redundant Relations in Relational Databases: A Model Theoretic Perspective

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.