Incremental Integrity Checking: Limitations and Possibilities

Henning Christiansen, Davide Martinenghi

    Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

    Abstract

    Integrity checking is an essential means for the preservation of the intended semantics of a deductive database. Incrementality is the only feasible approach to checking and can be obtained with respect to given update patterns by exploiting query optimization techniques. By reducing the problem to query containment, we show that no procedure exists that always returns the best incremental test (aka simplification of integrity constraints), and this according to any reasonable criterion measuring the checking effort. In spite of this theoretical limitation, we develop an effective procedure allowing general parametric updates that, for given database classes, returns ideal simplifications and also applies to recursive databases. Finally, we point out the improvements with respect to previous methods based on an experimental evaluation.
    OriginalsprogEngelsk
    TitelLogic for Programming, Artificial Intelligence, and Reasoning 12th International Conference, LPAR 2005, Montego Bay, Jamaica, Proceedings, LPAR
    RedaktørerGeoff Sutcliffe, Andrei Voronkov
    Antal sider16
    ForlagKluwer Academic Publishers
    Publikationsdato2005
    Sider712-727
    ISBN (Trykt)3-540-30553-X
    StatusUdgivet - 2005
    BegivenhedLPAR, Logic for Programming, Artificial Intelligence, and Reasoning - Montego Bay, Jamaica
    Varighed: 2 dec. 20056 dec. 2005
    Konferencens nummer: 12

    Konference

    KonferenceLPAR, Logic for Programming, Artificial Intelligence, and Reasoning
    Nummer12
    LandJamaica
    ByMontego Bay
    Periode02/12/200506/12/2005
    NavnLecture Notes in Computer Science
    Vol/bind3835
    ISSN0302-9743

    Citer dette

    Christiansen, H., & Martinenghi, D. (2005). Incremental Integrity Checking: Limitations and Possibilities. I G. Sutcliffe, & A. Voronkov (red.), Logic for Programming, Artificial Intelligence, and Reasoning 12th International Conference, LPAR 2005, Montego Bay, Jamaica, Proceedings, LPAR (s. 712-727). Kluwer Academic Publishers. Lecture Notes in Computer Science, Bind. 3835