Intensional logic and epistemic independency of intelligent database agents Zoran Majkić Dipartimento di Informatica e Sistemistica, University of Roma “La Sapienza” Via Salaria 113, I-00198 Rome, Italy majkic@dis.uniroma1.it Abstract. In the typical Web applications each intelligent database agent can be defined as a Knowledge system (KS) with a global ontology, which integrates a number of source data distributed in Web by traditional extensional mappings, and must be robust enough in order to take in account the incomplete and locally inconsistent information of its sources. The traditional extensional semantics for mappings between the different KSs destroys the epistemic independence of KSs: the beliefs of other KSs are forced into a local knowledge of a given KS, so that its own belief depends directly and automatically from them. Actually we want to find a kind of semantics for external mappings between KSs which is less strong w.r.t. the internal KS’s (extensionally based) database mappings. These philo- sophical considerations motivate the need of a new, alternative semantic charac- terization, based not on the extension but on the meaning of concepts used in the mappings between KSs. The Cooperative Information Systems has no centralized schema and no central ad- ministration. Instead, each intelligent database agent (KS) is an autonomous informa- tion system, and information integration is achieved by establishing mappings among various ontologies of these independent KSs. Given the de-centralized nature of the development of the Semantic Web, there will be an explosion in the number of ontolo- gies. Many of these ontologies (that is, KSs) will describe similar domains, but using different terminologies, and others will have overlapping domains. To integrate data from disparate ontologies, we must know the semantic correspondence between their elements. Recently are given a number of different architecture solutions [1,2,3,4]. Queries are posed to one KS, and the role of query processing is to exploit both the data that are internal to the KS, and the mappings with other KSs in the system. In this paper we investigate on the possibility of using the intensional logic for both expressing interschema (inter-ontology) knowledge, and reasoning about it. The basic idea of our approach is to propose an intensional logic-based language to express in- terdependencies between concepts (views defined as conjunctive queries) belonging to different schemas (KS’s ontologies). For example, one can assert in our language  that the concept represented by the view GraduateStudent in theschema is the same as the concept represented by the view SeniorStudent in . Such assertion implies a sort of intensional equivalence between the two concepts, but does not imply that the extension (the set of instances) of the former is always the same as the extension of the later. The existing research papers in the literature share our general goal of representing and using interschema knowledge (for an exhaustive consideration consider [5] ), but their approaches does not guarantee the complete epistemic independencies between differ- ent KSs. Let   and   be the two KSs, denominated by ’Peter’ and ’John’ respectively, and x, x be the concepts of ”the Italian art in the 15’th century” with attributes in x, written in local languages of  and   respectively. We are able to individuate at least two extreme scenarios, developed from the initial article [6] : 1. The strongly-coupled semantics [3] for mappings between different KSs is a direct extension of extensionally based database mappings between views of KSs [5] used for a (strong) data integration systems: For any given KS its own knowledge is locally en- larged by extensional knowledge of other KSs: any dynamic change of the knowledge of other KSs is directly reflected into the local knowledge of this KS. As showed in [3], the added knowledge of other KSs is seen as some kind of local ’source’ database of data-integration system of a given KS. We can paraphrase this by imperative assertion ’John must know all facts about the Italian art in the 15’th century known by Peter’ (also when ’Peter’ in his life cycle changes this part of its own knowledge), formally    x   x , where  is the logic implication. 2. The weakly-coupled semantics [7,4]. At a very beginning was my intuition that the real cooperative information systems, where each KS is completely independent en- tity, with its own epistemic state, which has not to be directly, externally, changed by the mutable knowledge of other independent KSs, needs other meaning (approach) to the mapping between their local knowledge. First requirement is that the knowledge of other KSs can not be directly transferred into the local knowledge of a given peer. The second requirement is that, during the life time of a cooperative information system, any local change of knowledge must be independent of the beliefs that can have other KSs: thus, we have not to constrain the extension of knowledge which may have differ- ent KSs about the same type of real-world concept. In the example above, ’John’ can answer only for a part of knowledge that it really has about Italian art, and not for a knowledge that ’Peter’ has. Thus, when somebody (call him ’query-agent’) ask ’John’ some information about Italian art in the 15’th century, ’John’ is able to respond only by facts known by himself (i.e., certain answers), and eventually indicate to query-agent that for such question probably ’Peter’ is able to give some answer also: so, it is the task of the query-agent to reformulate the question (w.r.t. the local language of ’Peter’) to ’Peter’ in order to obtain some other possible answers. We can paraphrase this by the kind of belief-sentence-mapping ’John believes that also Peter knows something    about Italian art in the 15’th century’, formally  x    x , where  is the believed intensional equivalence. Such belief-sentence has referential (i.e., extensional) opacity. In this case we do not specify that the knowledge of ’John’ is included in the knowledge of ’Peter’ (or vicev-   this concept, x , ersa) for the concept ’Italian art in the 15’th century’, but only that for ’John’ implicitly corresponds to the ’equivalent’ concept, x , for ’Peter’. The ’implicit correspondence between equivalent concepts’ needs a formal semantic defi- nition for it. It was not easy task, because the mapping defined above deals with the semantics of natural language. Motague [8] defined the intension of a sentence as a function from possible worlds to truth values. In what follows we will use one simplified modal logic framework (we will not consider the  time as!"one #%independent $  parameter as in Montague’s original work) with a model  , where '&(*)+is the set of possible worlds, is the accessibility rela- $ tion between worlds ( ), is a non-empty domain of individuals, while is a $- function ,.)0defined /214for 3 the 98following : two / cases: 1. 657  , with a set of functional symbols / of the language, such that for $@  ,9ACB EDGFIHJLK 1M any world = ; < and a functional symbol ? > < , we obtain a function ; $'>,N) 1 3 . 8O: 2.   657 2 , with  a set of predicate symbols of the language and 2 QPS R >T is the set of truth values (true and false, respectively), $V such  that ,WXAfor CB YDGany world ;< and a predicate symbol U0< , weXACobtain a function ;  U F H[Z\K 1 2, B YDGFIHaZbK $@  which defines the extension ] UW^_P a ` a < and ; Uc a 9dR%T of this pred- icate U in the world ; .   The extension of an expression e , w.r.t. / a model 3 , a world ;f< and assignment  g is denoted by ] eh^jik lmk n . Thus, if op<  then$@for a given world ;q< and the g , ] o%^ri?k lmk ns ; S o assignment  u function for variables , while for any formula  t , lmk n w t v ] x t y ^  i k m l k + n =  ! R , means ’A is true in the world ; of a model for assignment g ’. Montague 1 defined the  intension of an expression e as follows: ] eh^ i  k n {zC| J PS;~} ] e ^jik lmk n`S;€< , T , 1M3 i.e., as graph of the function ] eh^ i  k n ] e ^jik lmk n . One thing that should be immediately clear is that intensions are more general that ex- lm‚ƒp„ tensions: if the intension of an expression is given, one can determine its extension with respect to a particular world but not viceversa, i.e., ] eh^rik lmk n ] eh^ i  k n ;† . In particular, if o is a non-logical constant (individual $V  constant or predicate symbol), the definition of the extension of o is, ] o%^Gik lmk n†{zC| J ; o\ . Hence, the intensions of the ,1 3 $V  non-logical constants are the following functions: ] o%^ i  k n g ; o\ . The extension of variable is supplied by the value assignment only, and thus does not m l  ‚ ƒ differ from one world to the other; if ‡ is a variable we have ] ‡W^ i  k n  g ‡ . Carnap suggested that the intension of an expression is nothing more than all the vary- ing extensions the expression can have. In the next !ˆ we will take this definition in order to define that two expressions (or concepts) e are intensionally equivalent, in the following two cases: !ˆ Definition 1. Any two expressions, e , are intensionally equivalent ˆ (in the flat-accumulation or the world-correspondent case, respectively) denoted Gˆ by ‰ e     , if and only if : 1. flat-accumulation case: Šr‹cŒ\i?k n eQŠr‹cŒbi?k n , where for a given expression Ž Ž 3 Ž kn , its ŠG‹Œ (Least Upper Bound) is defined by: Šr‹cŒ\ik n 9{zC| J ] ^ i  ;† . ˆ m l  ‚ ƒ 2. world-correspondent case: ;†6;†’‘ ] e ^ i k n † ; X “ ] ^  i k n ” ; j  m ˆ  k n  , and viceversa, ;†y•;–‘ ] eh^ i  k n ;†X“] ^ i? E ;”Gm . In the context of this work we will consider each temporary instance (in a some time R!— ) of the cooperative information system as a particular possible world ; : the dynamic changes of any local KS knowledge will result in one other possible world. The in- tensional mapping between KSs is given by couples of queries  ‡  ‡˜ where a conjunctive query  ‡c over a KS   and a conjunctive query  ‡c over a peer   are both intensionally equivalent to same real-world entity e , w.r.t. the certain answers from KSs (we consider that each KS   is an epistemic local logic theory with the   modal epistemic operator  , so that the truth of a modal formula    ‡ corresponds to the set of certain answers to the conjunctive query  ‡c only), i.e.,   ‡c†+e  and   ‡™še , thus, by the symmetry and the transitivity of the relation  , we obtain that holds   ‡9   ‡ . Notice that for any& given world ; , both relationships &     ]   ‡c›^ Ei?  k n ; ]   ‡œ^ i  k n ;† , and ]   ‡œ^ i  k n ; ]   ‡œ^ i  k n ;† need not to be satisfied. Moreover, if   and   are local universes for a KS   and   respectively (a local universe is the set of all the values that are elements of the domains used in the local schema of a KS), we do not require that for any o‰<ž pŸ   , the   sentences   oS and   o\ have the same truth value as required in [5]. Proposition 1 Let consider the class of  KSs ¡ with ¡ integrity¤£-constraints ¥€¦ which does not contain negative clauses of the form t ‘‘‘ t”¢ . Then, the intensional equivalencežis © preserved © by¥Qconjunction « logic operation, «{¬(­X¬ that is, if §¨v Œ ‘‘E‘ Œb— , ª , and Œ   E o  , ž© © ª , then §s p® where v is a logic equivalence and ® v o ‘‘E‘‘ o\— . Thus, for any given conjunctive query (virtual concept) to some intelligent database agent, the query-agent will obtain as answer the set of certain (known) answers from this interrogated database agent, and the set of possible answers from other database agents which are able to express the intensionally equivalent virtual concepts to the original user query. We believe that the intensional mapping semantics presented in this paper constitutes a sound basis for studying the various issues related to interschema knowledge represen- tation and reasoning, especially for P2P database systems in Web environment, where peers can be considered as complex database agents. References 1. S.Gribble, A.Halevy, Z.Ives, M.Rodrig, and D.Suciu, “What can databases do for peer-to- peer?,” WebDB Workshop on Databases and the Web, 2001. 2. L.Serafini, F.Giunchiglia, J.Mylopoulos, and P.A.Bernstein, “The local relational model: Model and proof theory,” Technical Report 0112-23, ITC-IRST, 2001. 3. D.Calvanese, G. De Giacomo, M.Lenzerini, and R.Rosati, “Logical foundations of peer-to- peer data integration,” PODS 2004, June 14-16, Paris, France, 2004. 4. Z. Majkić, “Weakly-coupled ontology integration of p2p database systems,” 1st Int. Workshop on Peer-to-Peer Knowledge Management (P2PKM), August 22, Boston, USA, 2004. 5. Tiziana Catarci and Maurizio Lenzerini, “Representing and using interschema knowledge in cooperative information systems,” J. of Intelligent and Cooperative Information Systems, vol. 2, no. 4, pp. 375–398, 1993. 6. M.Lenzerini and Z. Majkić, “General framework for query reformulation,” Semantic Webs and Agents in Integrated Economies, D3.1, IST-2001-34825, February,, 2003. 7. Z. Majkić, “Massive parallelism for query answering in weakly integrated p2p systems,” Workshop GLOBE 04, August 30-September 3,Zaragoza, Spain, 2004. 8. R.Montague, “Formal philosophy. selected papers of richard montague,” in R.Thomason (editor), Yale University Press, New Haven, London, pp. 108–221, 1974.