• Login
    View Item 
    •   Home
    • Massey Documents by Type
    • Theses and Dissertations
    • View Item
    •   Home
    • Massey Documents by Type
    • Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    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

    Icon
    View/Open Full Text
    01_front.pdf (102.6Kb)
    02_whole.pdf (2.606Mb)
    Export to EndNote
    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.
    Date
    2005
    Author
    Paoletti, Alejandra Lorena
    Rights
    The Author
    Publisher
    Massey University
    URI
    http://hdl.handle.net/10179/5175
    Collections
    • Theses and Dissertations
    Metadata
    Show full item record

    Copyright © Massey University
    | Contact Us | Feedback | Copyright Take Down Request | Massey University Privacy Statement
    DSpace software copyright © Duraspace
    v5.7-2020.1-beta1
     

     

    Tweets by @Massey_Research
    Information PagesContent PolicyDepositing content to MROCopyright and Access InformationDeposit LicenseDeposit License SummaryTheses FAQFile FormatsDoctoral Thesis Deposit

    Browse

    All of MROCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Statistics

    View Usage Statistics

    Copyright © Massey University
    | Contact Us | Feedback | Copyright Take Down Request | Massey University Privacy Statement
    DSpace software copyright © Duraspace
    v5.7-2020.1-beta1