Volume 6: January - December 1996

Issue 5: October 1996


Novelty in deductive databases

  • Novelty in deductive databases
  • E. Gregoire1 and P. Marquis2 1CRIL, Universite d'Artois, rue de l'Universite, S.P. 16 F-62307 Lens Cedex, France and 2CRIN/CNRS and INRIA-Lorraine, Campus Scientifique - B.P. 239, F-54506 Vandoeuvre-les-Nancy Cedex, France


    In this paper, a notion of novelty of a formula for a concept w.r.t. a deductive database is investigated from a logical point of view. Intuitively, a formula is new for a concept when inserting the formula together with some additional information in the database allows us to infer on instance of the concept (or its negation) from the resulting database, while this proves impossible when only the additional information is inserted. First, this notion is analysed in the framework of first-order Herbrand monotonic databases. A decision procedure is provided, based on a prime implicants characterization. Then, novelty is investigated in the context of non-monotonic-completed-databases. Actually, four types of novelty are put forward to capture various intuitions about the relations between novelty and forms of non-monotonicity. These types of novelty are proved incomparable in the general case and their decision problems are discussed. Finally, possible applications of novelty in the database field are presented.

    Keywords: Deductive databases, novelty, relevance, non-monotonic logics.

    Pages: 683 - 708

    Part of the OUP Journal of Logic and Computation WWW service

    General Information

    Click here to register with OUP.

    This page is maintained by OUP admin

    Last updated 19 Nov 96

    Part of the OUP Journals World Wide Web service.

    Copyright Oxford University Press, 1996