A study of homogeneity in relational databases

We define four different properties of relational databases which are relat ed tothe notion of homogeneity in classical model theory. The main question for their definition is, for any given database to determine the minimum i nteger 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 th ere is an automorphism which maps each of these k-tuples onto each other. W e study these four properties as a means to increase the computational powe r of subclasses of the reflective relational machines (RRMs) of bounded var iable complexity. These were introduced by S. Abiteboul, C. Papadimitriou a nd V. Vianu and are known to be incomplete. For this sake we first give a s emantic characterization of the subclasses of total RRM with variable compl exity 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 int erest in their own right. For each k >0, we define the subclass QCQ(k) as t he total queries in the class CQ of computable queries which preserve reali zation of properties expressible in FOk. The nature of these classes is imp licit in the work of S. Abiteboul, M. Vardi and V. Vianu. We prove QCQ(k)=t otal(RRMk) for every k >0. We also prove that these classes form a strict h ierarchy within a strict subclass of total(CQ). This hierarchy is orthogona l to the usual classification of computable queries in time-space-complexit y classes. We prove that the computability power of RRMk machines is much g reater when working with classes of databases which are homogeneous, for th ree of the properties which we define. As to the fourth one, we prove that the computability power of RRM with sublinear variable complexity also incr eases when working on databases which satisfy that property. The strongest notion, pairwise k-homogeneity, allows RRMk machines to achieve completenes s.