cse291 4 final

Department of Computer Science & Engineering University of California, San DiegoCSE-291: Ontologies in Data IntegrationSpring 2003: 

Department of Computer Science & Engineering University of California, San Diego CSE-291: Ontologies in Data Integration Spring 2003 Bertram Ludäscher LUDAESCH@SDSC.EDU Recap: First-Order Logic (FO) Formal Ontologies (Guarino) BREAK Guest Lecture by Dr. Gully Burns (USC) on NeuroScholar

Syntax of First-Order Logic (FO): 

Syntax of First-Order Logic (FO) Logical symbols: , , , , ,  ,  (“for all”),  (“exists”), ... Non-logical symbols: A FO signature  consists of constant symbols: a,b,c, ... function symbols: f, g, ... predicate (relation) symbols: p,q,r, .... function and predicate symbols have an associated arity; we can write, e.g., p/3, f/2 to denote the ternary predicate p and the function f with two arguments First-order variables Vars: x, y, ... Formation rules for terms Term : constants and variables are terms if t_1,...t_k are terms and f is a k-ary function symbols then f(t_1,...,t_k) is a term

Syntax of First-Order Logic (FO): 

Syntax of First-Order Logic (FO) Formation rules for formulas Fml : if t1,...tk are terms and p/k is a predicate symbol (of arity k) then p(t1,...tk ) is an atomic formula At (short: atom) all variable occurrences in p(t1,...tk ) are free if F,G are formulas and x is a variable, then the following are formulas: FG, F  G,  F, FG , FG,  F , x: F (“for all x: F(x,...) is true”) x: F (“there exists x such that F(x,...) is true”) the occurrences of a variable x within the scope of a quantifier are called bound occurrences.

Examples: 

Examples x malePerson(x)  person(x). malePerson(bill). child(marriage(bill,hillary),chelsea). Variable: x Constants (0-ary function symbols): bill/0, hillary/0, chelsea/0 Function symbols: marriage/2 Predicate symbols: malePerson/1, person/1, child/2

Semantics of Predicate Logic: 

Semantics of Predicate Logic Let D be a non-empty domain (a.k.a. universe of discourse). A structure is a pair I = (D,I), with an interpretation I that maps ... each constant symbols c to an element I(c) D each predicate symbol p/k to a k-ary relation I(p)  Dk, each function symbol f/k to a k-ary function I(f): DkD Let I be a structure,  : Vars  D a variable assignment. A valuation valI, maps Term to D and Fml to {true, false} valI, (x) =  (x) ; for x  Vars valI, (f(t1,...,tk)) = I(f)( valI, (t1),..., valI, (tk) ); for f(t1,...,tk)  Term valI, (p(t1,...,tk)) = I(p)( valI, (t1),..., valI, (tk) ); for p(t1,...,tk)  At valI, (F  G) = valI, (F) and valI, (G) ; for F,G Fml .... for Fml over , , , ,  , , in the obvious way

Example: 

Example Formula F = x malePerson(x)  person(x). Domain D = {b, h, c, d, e} Let’s pick an interpretation I: I(bill) = b, I(hillary) = h, I(chelsea) = c I(person) = {b, h, c} I(malePerson) = {b} Under this I, the formula F evaluates to true. If we choose I’ like I but I’(malePerson) = {b,d}, then F evaluates to false Thus, I is a model of F, while I’ is not: I |= F I’ |=/= F

FO Semantics (cont’d): 

FO Semantics (cont’d) F entails G (G is a logical consequence of F) if every model of F is also a model of G: F |= G F is consistent or satisfiable if it has at least one model F is valid or a tautology if every interpretation of F is a model Proof Theory: Let F,G, ... be FO sentences (no free variables). Then the following are equivalent: F_1, ..., F_k |= G F_1  ...  F_k  G is valid F_1  ...  F_k   G is unsatisfiable (inconsistent)

Proof Theory: 

Proof Theory A calculus is formal proof system to establish F_1, ..., F_k |= G via formal (syntactic) derivations F_1, ..., F_k |– ... |– G, where the “|–” denotes allowed proof steps Examples: Hilbert Calculus, Gentzen Calculus, Tableaux Calculus, Natural Deduction, Resolution, ... First-order logic is “semi-decidable”: the set of valid sentences is recursively enumerable, but not recursive (decidable) Some inference engines: http://www.semanticweb.org/inference.html

Flashback: Ontologies–Attempt at a Definition : 

Flashback: Ontologies–Attempt at a Definition An ontology is ... an explicit specification of a conceptualization [Gruber93] a shared understanding of some domain of interest [Uschold, Gruninger96] Some aspects and parameters: a formal specification (reasoning and “execution”) ... of a conceptualization of a domain (community) ... of some part of world that is of interest (application) Provides: A common vocabulary of terms Some specification of the meaning of the terms (semantics) A shared understanding for people and machines

Human and machine communication (I): 

Human and machine communication (I) ... Machine Agent 1 Things Human Agent 2 Ontology Description Machine Agent 2 exchange symbol, e.g. via nat. language ‘‘JAGUAR“ Internal models Concept Formal models exchange symbol, e.g. via protocols MA1 HA1 HA2 MA2 Symbol commit commit a specific domain, e.g. animals commit commit Ontology Formal Semantics Human Agent 1 Meaning Triangle [Maedche et al., 2002]

Some different uses of the word “Ontology” [Guarino’95]: 

Some different uses of the word “Ontology” [Guarino’95] http://ontology.ip.rm.cnr.it/Papers/KBKS95.pdf 1. Ontology as a philosophical discipline 2. an ontology as an informal conceptual system 3. an ontology as a formal semantic account 4. an ontology as a specification of a “conceptualization” 5. an ontology as a representation of a conceptual system via a logical theory 5.1 characterized by specific formal properties 5.2 characterized only by its specific purposes 6. an ontology as the vocabulary used by a logical theory 7. an ontology as a (meta-level) specification of a logical theory

Ontology as a philosophical discipline: 

Ontology as a philosophical discipline Ontology: branch of philosophy dealing with the nature and organization of reality (in contrast: Epistemology: deals with the nature and sources of our knowledge; “theory of knowledge”) Aristotle: Science of being; dealing with questions such as: What exists? What are the features common to all beings?

What is a Conceptualization?: 

What is a Conceptualization? Conceptualization [Genesereth, Nilsson]: universe of discourse (domain) D = {a,b,c,d,e} relations = {on/2, above/2, clear/1, table/1} Compare (A) and (B): world_A: {on(a,b), on(b,c), on(d,e), table(c), table(e)} world_B: {on(a,b), on(c,d), on(d,e), table(b), table(e)} two different conceptualizations? or rather two different states of the same conceptualization? (A) (B) Meaning is NOT captured by extensional relations / a single state of affairs

Intensional Structures: 

Intensional Structures Meaning is NOT in a single state of affairs (extensional relations) but can be captured by intensional relations An n-ary intensional relation R over domain D is a function R : W  Powerset(Dn) W set of possible worlds {w1, w2, w3, ...} (a possible world is one state of affairs, or a situation) Powerset(Dn) = set of all subsets of Dn (= D x ... x D) So for each w W we have R(w) = a subset of Dn, i.e., with each world we associate the interpretation of R in that world

Example: 

Example Syntax: signature (vocabulary)  = constant symbols: {a,b} relation symbols: {on/2, table/1} Semantics: domain D = {“a_block”, “b_block”} Structure I = (D,I) with some interpretation I: I(a) = “a_block”, I(b) = “b_block” I(on) = {(I(a),I(b)), (I(b),I(c)), (I(d),I(e))} = {(“a_block”,”b_block”), ...} I(table) = {c, e}

How can we capture (some of!) the meaning of “on-ness”? : 

How can we capture (some of!) the meaning of “on-ness”? Many things can be said about “on-ness” (physics of gravity, pressure and deformation, etc.) What is common among all possible states of on/2 over a certain domain D? That is, if we look at all possible worlds W, and the values that I(on)(w) can take, what is common among all those states? What is always true (in all possible worlds) about on/2 is (part of) the meaning of on/2.  (x:  on(x,x)) ; in all possible worlds: x is not on x  (x,y:  (on(x,y)  on(y,x))) ; in all possible worlds: no x is on y while y is on x Good enough? what about on(a,b), on(b,c), on(c,a) ? Even worse: What is someone sees “on” and interprets it as “below”?  we only capture some aspects using the above ontological theory

Another Example: 

Another Example “” is the traditional logician’s symbol for implication (“”)

Some different uses of the word “Ontology” [Guarino’95]: 

Some different uses of the word “Ontology” [Guarino’95] http://ontology.ip.rm.cnr.it/Papers/KBKS95.pdf 1. Ontology as a philosophical discipline 2. an ontology as an informal conceptual system 3. an ontology as a formal semantic account 4. an ontology as a specification of a “conceptualization” 5. an ontology as a representation of a conceptual system via a logical theory 5.1 characterized by specific formal properties 5.2 characterized only by its specific purposes 6. an ontology as the vocabulary used by a logical theory 7. an ontology as a (meta-level) specification of a logical theory conceptualization ontological theory