COMPLETENESS RESULTS FOR RECURSIVE DATA-BASES

We consider infinite recursive (i.e., computable) relational data base s. Since the set of computable queries on such data bases is not close d under even simple relational operations, one must either make do wit h a very modest class of queries or considerably restrict the class of allowed data bases. We define two query languages, one for each of th ese possibilities, and prove their completeness. The first is the lang uage of quantifier-free first-order logic, which is shown to be comple te for the non-restricted case. The second is an appropriately modifie d version of Chandra and Harel's language QL, which is proved complete for the case of ''highly symmetric'' data bases, i.e., ones whose set of automorphisms is of finite index for each tuple width. We also add ress the related notion of BP-completeness. (C) 1996 Academic Press, I nc.