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
Loading...
Date
2005
DOI
Open Access Location
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Massey University
Rights
The Author
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.
Description
Keywords
Relational databases, Model theory