A study of homogeneity in relational databases
We define four different properties of relational databases which are related tothe notion of homogeneity in classical model theory. The main question for their definition is, for any given database to determine the minimum integer k, such that whenever two k-tuples satisfy the same properties which are expressible in first order logic with up to k variables (FOk), then there is an automorphism which maps each of these k-tuples onto each other. We study these four properties as a means to increase the computational power of subclasses of the reflective relational machines (RRMs) of bounded variable complexity. These were introduced by S. Abiteboul, C. Papadimitriou and V. Vianu and are known to be incomplete. For this sake we first give a semantic characterization of the subclasses of total RRM with variable complexity k (RRMk) for every natural number k. This leads to the definition of classes of queries denoted as QCQ(k). We believe these classes to be of interest in their own right. For each k >0, we define the subclass QCQ(k) as the total queries in the class CQ of computable queries which preserve realization of properties expressible in FOk. The nature of these classes is implicit in the work of S. Abiteboul, M. Vardi and V. Vianu. We prove QCQ(k)=total(RRMk) for every k >0. We also prove that these classes form a strict hierarchy within a strict subclass of total(CQ). This hierarchy is orthogonal to the usual classification of computable queries in time-space-complexity classes. We prove that the computability power of RRMk machines is much greater when working with classes of databases which are homogeneous, for three of the properties which we define. As to the fourth one, we prove that the computability power of RRM with sublinear variable complexity also increases when working on databases which satisfy that property. The strongest notion, pairwise k-homogeneity, allows RRMk machines to achieve completeness.
query languages database machines query computability completeness of models