A Roadmap on Updates

A Roadmap on Updates

Fernando Zacarías Flores (Benemérita Universidad Autónoma de Puebla, Mexico), Dionicio Zacarías Flores (Benemérita Universidad Autónoma de Puebla, Mexico), Rosalba Cuapa Canto (Benemérita Universidad Autónoma de Puebla, Mexico) and Luis Miguel Guzmán Muñoz (Benemérita Universidad Autónoma de Puebla, Mexico)
Copyright: © 2009 |Pages: 6
DOI: 10.4018/978-1-59904-849-9.ch201
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Updates, is a central issue in relational databases and knowledge databases. In the last years, it has been well studied in the non-monotonic reasoning paradigm. Several semantics for logic program updates have been proposed (Brewka, Dix, & Knonolige 1997), (De Schreye, Hermenegildo, & Pereira, 1999) (Katsumo & Mendelzon, 1991). However, recently a set of proposals has been characterized to propose mechanisms of updates based on logic and logic programming. All these mechanisms are built on semantics based on structural properties (Eiter, Fink, Sabattini & Thompits, 2000) (Leite, 2002) (Banti, Alferes & Brogi, 2003) (Zacarias, 2005). Furthermore, all these semantic ones coincide in considering the AGM proposal as the standard model in the update theory, for their wealth in properties. The AGM approach, introduced in (Alchourron, Gardenfors & Makinson, 1985) is the dominating paradigm in the area, but in the context of monotonic logic. All these proposals analyze and reinterpret the AGM postulates under the Answer Set Programming (ASP) such as (Eiter, Fink, Sabattini & Thompits, 2000). However, the majority of the adapted AGM and update postulates are violated by update programs, as shown in (De Schreye, Hermenegildo, & Pereira, 1999).
Chapter Preview
Top

Introduction

Updates, is a central issue in relational databases and knowledge databases. In the last years, it has been well studied in the non-monotonic reasoning paradigm. Several semantics for logic program updates have been proposed (Brewka, Dix, & Knonolige 1997), (De Schreye, Hermenegildo, & Pereira, 1999) (Katsumo & Mendelzon, 1991). However, recently a set of proposals has been characterized to propose mechanisms of updates based on logic and logic programming. All these mechanisms are built on semantics based on structural properties (Eiter, Fink, Sabattini & Thompits, 2000) (Leite, 2002) (Banti, Alferes & Brogi, 2003) (Zacarias, 2005). Furthermore, all these semantic ones coincide in considering the AGM proposal as the standard model in the update theory, for their wealth in properties. The AGM approach, introduced in (Alchourron, Gardenfors & Makinson, 1985) is the dominating paradigm in the area, but in the context of monotonic logic. All these proposals analyze and reinterpret the AGM postulates under the Answer Set Programming (ASP) such as (Eiter, Fink, Sabattini & Thompits, 2000). However, the majority of the adapted AGM and update postulates are violated by update programs, as shown in (De Schreye, Hermenegildo, & Pereira, 1999).

Top

Updates

Update theory deals with knowledge base represented by a propositional theory. Besides, deals with incorporating new knowledge about a dynamic world. This dynamism is due to knowledge comes from the real world, what means that knowledge evolves over time. This exchange rate mainly deals with changes in the extensional part of knowledge bases. However, the problem of updating the intensional part of a knowledge base (rules and descriptions of actions) remains basically unexplored. However, the problem of updates has attracted the researchers’ attention in the last years who are dealing with such updates in the setting of logic programs. Though, some interesting proposals exist with foundation in Answer set programming (ASP), such as (Eiter, Fink, Sabattini & Thompits, 2000) (Leite, 2002) (Banti, Alferes & Brogi, 2003) (Osorio & Zacarias, 2003).

Answer set programming is a new paradigm used in the solution of the update issue. Particularly, this paradigm has taken bigger force around of update theory. A lot of theoretical work around updates under ASP has been developed by connoted researchers such as: Pereira, Alferes, Eiter, Osorio, Leite, Zacarias, and others. In the last years, a lot of theoretical work was devoted to explore the relationships between intuitionistic logic and ASP (Pearce, 1999) (Lifschitz, Pearce & Valverde, 2001). These results have recently provided a characterization of ASP by intuitionistic logic as follows: a literal is entailed by a program in the answer set semantics if and only if it belongs to every intuitionistically complete and consistent extension of the program formed by adding only negated literals (Pearce, 1999). The idea of these completions using in general intermediate logics is due to Pearce (Lifschitz, Pearce & Valverde, 2001). This logical approach provides the foundations to define the notion of non-monotonic inference of any propositional theory (using the standard connectives) in terms of a monotonic logic (namely intuitionistic logic), see (Lifschitz, Pearce & Valverde, 2001) (Pearce, 1999).

Key Terms in this Chapter

Expansion: Which is simply adding the new information A to knowledge base KB.

Beliefs: An agent whose knowledge base is the theory T believes F if and only if F belongs to every intuitionistically complete and consistent extension of T by adding only negated literals.

Principle of Irrelevance of Syntax: The meaning of the knowledge that results from an update must be independent of the syntax of the original knowledge, as well as independent of the syntax of the update itself.

Update: Let P be the program representing the current knowledge base, if it is updated by another program U, then PU is a program updated of P if only if the models of PU are the result of updating each of the models of P according to a given semantics S; to each of these models apply the update request U to obtain a new set of models M; PU is any logic program whose models are exactly M.

Equivalence: Two programs are equivalent if they have exactly the same answer sets.

Weak Irrelevance of Syntax: T1 = T2 implies Bel(K ? T1) = Bel(K ? T2), where K, T1 and T2 are any theories, Bel(T) defines the set of answer sets of T, ? is the update operator, and understanding that equivalence means that both programs (T1 and T2) have the same answer sets.

Causal Rejection Principle: Which enforces that, in case of conflicts between rules, more recent rules are preferred and older rules are overridden.

Complete Chapter List

Search this Book:
Reset