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

Simple item page
dc.contributor.authorPaoletti, Alejandra Lorena
dc.date.accessioned2014-03-25T20:35:58Z
dc.date.available2014-03-25T20:35:58Z
dc.date.issued2005
dc.description.abstractAbstract. 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.en
dc.identifier.urihttp://hdl.handle.net/10179/5175
dc.language.isoenen
dc.publisherMassey Universityen_US
dc.rightsThe Authoren_US
dc.subjectRelational databasesen
dc.subjectModel theoryen
dc.titleThe 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 Zealanden
dc.typeThesisen
massey.contributor.authorPaoletti, Alejandraen
thesis.degree.disciplineInformation Scienceen
thesis.degree.grantorMassey Universityen
thesis.degree.levelMastersen
thesis.degree.nameMaster of Information Sciences (M. Inf. Sc.)en
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
01_front.pdf
Size:
102.67 KB
Format:
Adobe Portable Document Format
Description:
Download
Thumbnail Image
Name:
02_whole.pdf
Size:
2.61 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
804 B
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Theses and Dissertations