The model theoretic notion of type in relational databases : a thesis presented in partial fulfillment of the requirements for the degree of Master of Information Sciences at Massey University, Wellington, New Zealand

Abstract

Abstract. It is well known that finite model theory and database theory are two disciplines intimately connected. A topic which has been deeply studied in the context of finite model theory as well as in classic model theory, but which has not received the same attention in the context of databases, is the concept of type of a tuple. We believe that it is very important to have a clear understanding of the implications of the concept of type in the field of databases. Therefore, we study here the notion of type in FO (first-order logic) and in FOk (the restriction of FO to formulas with up to k variables), as well as in their corresponding infinitary extensions Lcow and L~w' respectively. The FOk types (L~w types) are quite relevant in database theory since they characterize the discerning power of the class of reflective relational machines of S. Abiteboul, C. Papadimitriou and V. Vianu with variable complexity k. We examine the three main characterizations of FO equivalence. These characterizations are based in Ehrenfeucht-Frai"sse games, back and forth systems of partial isomorphisms and isolating formulas for types. We study in detail all of them because they give a clear idea of the relevance of the notion of type in the context of databases, and make the fact that the types of the tuples in a database reflect all the information contained in it very clear. We found that the concept of type turned out to be useful to examine from a new perspective a well known problem of the field of databases, consisting on the redundant storage of information. Specifically, we initiate a study towards a method of normalization of relational databases based on the detection of redundant relations, i.e., relations which can be eliminated from the database without loosing information, by using isolating formulas for the types of the tuples in the database.