Redundant Relations in Relational Databases: A Model Theoretic Perspective

The authors initiate in this paper, the study of a sort of redundancy problem revealed by what they call redundant relations. Roughly, they 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 them R. So, given that first-order types are isomorphism types on finite structures, they 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.