Transcript CSE 291
Department of Computer Science & Engineering University of California, San Diego CSE-291: Ontologies in Data Integration Spring 2003 Bertram Ludäscher [email protected] CSE-291: Ontologies in Data Integration Outline • Wrapping up last week • What is a representation? • [Thesauri, Topic Maps] • Predicate Logic Primer • Description logics • [RDF & RDF Schema] • [F-logic] • Topic Selection Special thanks: • Alexander Maedche, Steffen Staab: – ECAI’2002 Tutorial on Ontologies CSE-291: Ontologies in Data Integration Ontologies … For What? • Lack of a shared understanding leads to poor communication => People, organizations and software systems must communicate between and among themselves • Disparate modeling paradigms, languages and software tools limit => Interoperability => Knowledge sharing & reuse [Uschold, Gruninger, 96] CSE-291: Ontologies in Data Integration Origin and History (I) • Ontology .... a philosophical discipline, branch of philosophy that deals with the nature and the organisation of reality • Science of Being (Aristotle, Metaphysics, IV, 1) • Tries to answer the questions: What is being? What are the features common to all beings? CSE-291: Ontologies in Data Integration Origin and History (II) • Humans require words (or at least symbols) to communicate efficiently. The mapping of words to things is only indirect possible. We do it by creating concepts that refer to things. • The relation between symbols and things has been described in the form of the meaning triangle: Concept “Jaguar“ [Ogden, Richards, 1923] CSE-291: Ontologies in Data Integration Origin and History (III) • In recent years ontologies have become a hot topic of interest. • Here, an ontology refers to an engineering artifact: • It is constituted by a specific vocabulary used to describe a certain reality, plus • a set of explicit assumptions regarding the intended meaning of the vocabulary. • Thus, ontologies describe a formal partial specification of a specific domain: • Shared understanding of a domain of interest • Formal and machine executeable model of a domain of interest CSE-291: Ontologies in Data Integration Human and machine communication (I) [Maedche et al., 2002] • ... Human Agent 1 Human Agent 2 exchange symbol, e.g. via nat. language Machine Agent 1 Machine Agent 2 exchange symbol, e.g. via protocols Ontology Description Symbol ‘‘JAGUAR“ Formal Semantics Internal models commit commit commit Concept MA1 HA2 HA1 Formal models Ontology commit a specific domain, e.g. animals CSE-291: Ontologies in Data Integration MA2 Things Meaning Triangle Ontology & Natural Language • It is important to emphasize that there is a m:n relationship between words and concepts • This means practically: – different words may refer to the same concept – a word may refer to several concepts • Ontologies languages should provide means for making this difference explicit. CSE-291: Ontologies in Data Integration Example Ontology: C = {c1,c2, c3}, R = {r1}, HC(c2,c1), r1(c2,c3), Lexicon: LC = {person, employee, organisation}, LR = {works at} F(person) = c1, F(employee) = c2, F(organisation) = c3, G(works at) = r1 ... organisation works at c3 r1(c2,c3), .. c1 HC(c2,c1) person employee CSE-291: Ontologies in Data Integration c2 .. .. Ontology vs. Knowledge Bases • There is no clear separation between ontology and knowledge base • Example: person medication Aspirin cured-with Ann Aspirin pill-1 pill-2 taken-aspirins taken-aspirins • Often it remains a modeling decision if something is modeled as concept or as instance. In many applications meta-modeling means are required. CSE-291: Ontologies in Data Integration Types of Ontologies (I) [Guarino, 98] describe very general concepts like space, time, event, which are independent of a particular problem or domain. It seems reasonable to have unified top-level ontologies for large communities of users. describe the vocabulary related to a generic domain by specializing the concepts introduced in the top-level ontology. describe the vocabulary related to a generic task or activity by specializing the top-level ontologies. These are the most specific ontologies. Concepts in application ontologies often correspond to roles played by domain entities while performing a certain activity. CSE-291: Ontologies in Data Integration Ontologies and their Relatives (I) • There are many relatives around: – Controlled vocabularies, thesauri and classification systems available in the WWW, see http://www.lub.lu.se/metadata/subject-help.html • Classification Systems (e.g. UNSPSC, Library Science, etc.) • Thesauri (e.g. Art & Architecture, Agrovoc, etc.) – Lexical Semantic Nets • WordNet, see http://www.cogsci.princeton.edu/~wn/ • EuroWordNet, see http://www.hum.uva.nl/~ewn/ – Topic Maps, http://www.topicmaps.org (e.g. used within knowledge management applications) • In general it is difficult to find the border line! CSE-291: Ontologies in Data Integration Ontologies and their Relatives (II) Catalog / ID Thesauri Terms/ Glossary CSE-291: Ontologies in Data Integration Informal Is-a Formal Is-a Frames Formal Instance General logical constraints Value Axioms Restric- Disjoint tions Inverse Relations, ... Some Ontologies (and Friends) in Action (coming soon to a project near you) CSE-291: Ontologies in Data Integration GEON Architecture Midatlantic Region Rocky Mountains CSE-291: Ontologies in Data Integration SMART (Meta)data I: Logical Data Views Adoption of a standard (meta)data model => wrap data sets into unified virtual views Source: NADAM Team (Boyan Brodaric et al.) CSE-291: Ontologies in Data Integration SMART Metadata II: Multihierarchical Rock Classification for “Thematic Queries” (GSC) –– or: Taxonomies are not only for biologists ... Genesis Fabric Composition “smart discovery & querying” via multiple, independent concept hierarchies (controlled vocabularies) • data at different description levels can be found and processed Texture CSE-291: Ontologies in Data Integration SMART Metadata III: Source Contextualization & Ontology Refinement Biomedical Informatics Research Network http://nbirn.net Focused GEON ontology working meeting last week ... (GEON, SCEC/KR, GSC, ESRI) CSE-291: Ontologies in Data Integration EcoCyc CSE-291: Ontologies in Data Integration Gene Ontology CSE-291: Ontologies in Data Integration http://www.geneontology.org “a dynamic controlled vocabulary that can be applied to all eukaryotes” Built by the community for the community. Three organising principles: Molecular function, Biological process, Cellular component Isa and Part of taxonomy – but not good! ~10,000 concepts Lightweight ontology, Poor semantic rigour. Ok when small and used for annotation. Obstacle when large, evolving and used for mining. Controlled vocabulary • AGROVOC: Agricultural Vocabulary CSE-291: Ontologies in Data Integration Thesauri • AAT: Art & Architecture Thesaurus CSE-291: Ontologies in Data Integration Ontologies - Some Examples • General purpose ontologies: – – – • Domain and application-specific ontologies: – – – – – – – • RDF Site Summary RSS, http://groups.yahoo.com/group/rss-dev/files/schema.rdf UMLS, http://www.nlm.nih.gov/research/umls/ KA2 / Science Ontology, http://ontobroker.semanticweb.org/ontos/ka2.html RETSINA Calendering Agent, http://ilrt.org/discovery/2001/06/schemas/icalfull/hybrid.rdf AIFB Web Page Ontology, http://ontobroker.semanticweb.org/ontos/aifb.html Web-KB Ontology, http://www-2.cs.cmu.edu/afs/cs.cmu.edu/project/theo11/www/wwkb/ Dublin Core, http://dublincore.org/ Meta-Ontologies – – – • WordNet / EuroWordNet, http://www.cogsci.princeton.edu/~wn The Upper Cyc Ontology, http://www.cyc.com/cyc-2-1/index.html IEEE Standard Upper Ontology, http://suo.ieee.org/ Semantic Translation, http://www.ecimf.org/contrib/onto/ST/index.html RDFT, http://www.cs.vu.nl/~borys/RDFT/0.27/RDFT.rdfs Evolution Ontology, http://kaon.semanticweb.org/examples/Evolution.rdfs Ontologies in a wider sense – Agrovoc, http://www.fao.org/agrovoc/ – Art and Architecture, http://www.getty.edu/research/tools/vocabulary/aat/ – UNSPSC, http://eccma.org/unspsc/ – DTD standardizations, e.g. HR-XML, http://www.hr-xml.org/ CSE-291: Ontologies in Data Integration Ontology Representation What is a „representation“? Concept “Jaguar“ CSE-291: Ontologies in Data Integration Ontology Representation Languages • Machines need communication with formal content to restrict meaning • What makes a language „formal“? – model theory (1st order predicate logic) – proof theory (Gentzen calculus) But also: – conventions (e.g. Java) CSE-291: Ontologies in Data Integration What makes a language suitable? For machine communication For human communication model theory proof theory tracktability strong conventions of use human readable names „natural“ primitives strong conventions of use human readable names CSE-291: Ontologies in Data Integration Representation Paradigms (incomplete) Thesauri TopicMaps Taxonomies Ontologies Semantic Nets extended ER-Modell Predicate Logics / Description Logics CSE-291: Ontologies in Data Integration Thesaurus CSE-291: Ontologies in Data Integration Thesauri Example: Fruit similarTo Vegetable NarrowerTerm Orange Apfelsine (german) synonymWith - Graph with labels edges (similar, nt, bt, synonym) - Fixed set of edge labels (aka relations) - no instances - Well known in library science - cf. terminologies / classifications (Dewey) CSE-291: Ontologies in Data Integration CSE-291: Ontologies in Data Integration Topic Maps are ... • Standardized: ISO/IEC 13250:2000 – ISO standard published Jan. 2000 – enabling standard to describe knowledge structures, electronic indices, classification schemes, ... • Web enabled: – XML Topic Maps (XTM) are ready to use • Designed to: – manage the info glut – build valuable information networks above any kind of resources / data objects – enable the structuring of unstructured information CSE-291: Ontologies in Data Integration Back-of-the-Book Index “British Virgin Islands” Gorda Sound see North Sound Little Dix Bay .................... 89 North Sound ....................... 90 Road Harbour see also Road Town ... 73 Road Town ...................... 69,71 Spanish Town ................... 81,82 Tortola ........................... 67 Virgin Gorda ...................... 77 CSE-291: Ontologies in Data Integration Back-of-the-Book Index “British Virgin Islands” Gorda Sound see North Sound Little Dix Bay .................... 89 North Sound ....................... 90 Road Harbour see also Road Town ... 73 Road Town ...................... 69,71 Spanish Town ................... 81,82 Tortola ........................... 67 Virgin Gorda ...................... 77 Topics CSE-291: Ontologies in Data Integration Back-of-the-Book Index “British Virgin Islands” Gorda Sound see North Sound Little Dix Bay .................... 89 North Sound ....................... 90 Road Harbour see also Road Town ... 73 Road Town ...................... 69,71 Spanish Town ................... 81,82 Tortola ........................... 67 Virgin Gorda ...................... 77 Occurrences CSE-291: Ontologies in Data Integration Back-of-the-Book Index “British Virgin Islands” Gorda Sound see North Sound Little Dix Bay .................... 89 North Sound ....................... 90 Road Harbour see also Road Town ... 73 Road Town ...................... 69,71 Spanish Town ................... 81,82 Tortola ........................... 67 Virgin Gorda ...................... 77 Different topic classes CSE-291: Ontologies in Data Integration Back-of-the-Book Index “British Virgin Islands” Gorda Sound see North Sound Little Dix Bay .................... 89 North Sound ....................... 90 Road Harbour see also Road Town ... 73 Road Town ...................... 69,71 Spanish Town ................... 81,82 Tortola ........................... 67 Virgin Gorda ...................... 77 Different occurrences classes CSE-291: Ontologies in Data Integration Back-of-the-Book Index “British Virgin Islands” Gorda Sound see North Sound Little Dix Bay .................... 89 North Sound ....................... 90 Road Harbour see also Road Town ... 73 Road Town ...................... 69,71 Spanish Town ................... 81,82 Tortola ........................... 67 Virgin Gorda ...................... 77 Multiple topic names CSE-291: Ontologies in Data Integration Back-of-the-Book Index “British Virgin Islands” Gorda Sound see North Sound Little Dix Bay .................... 89 North Sound ....................... 90 Road Harbour see also Road Town ... 73 Road Town ...................... 69,71 Spanish Town ................... 81,82 Tortola ........................... 67 Virgin Gorda ...................... 77 Association CSE-291: Ontologies in Data Integration Topics – Computerized Subjects Bay Island Topic classes Town Topics North Sound Little Dix Bay Tortola Subject Subject Virgin Gorda Subject Subject Road Town Spanish Town Subject Subject Road Harbour Subject Resources BVI Welcome CSE-291: Ontologies in Data Integration SurfBVI CaribNet Occurrences North Sound Little Dix Bay Tortola Virgin Gorda Road Town Spanish Town Topics Road Harbour Article Image Map Image Article Article Map Article Image Article Article Map Image Article Map Map Image Occurrences Occurrence classes Resources BVI Welcome CSE-291: Ontologies in Data Integration SurfBVI CaribNet Occurrences North Sound Little Dix Bay Tortola Virgin Gorda Road Town Spanish Town Topics Road Harbour Article Occurrences Map Occurrence classes Image Resources BVI Welcome CSE-291: Ontologies in Data Integration SurfBVI CaribNet Associations Part-Whole Vicinity Geo Containment Association classes Part-Whole Geo Containment Part-Whole Geo Containment Vicinity Associations Geo Containment North Sound Little Dix Bay Tortola Virgin Gorda Road Town Spanish Town Road Harbour CSE-291: Ontologies in Data Integration Topics Associations Part-Whole Vicinity Geo Containment Association classes Associations North Sound Little Dix Bay Tortola Virgin Gorda Road Town Spanish Town Road Harbour CSE-291: Ontologies in Data Integration Topics Class Hierarchies Bay Island Town Topics North Sound Little Dix Bay Tortola Virgin Gorda Road Town Spanish Town Road Harbour CSE-291: Ontologies in Data Integration Topic classes Class Hierarchies Bay Bay for swimming Land Anchor bay Town Capital Island Sub-classes Suburb Topics North Sound Little Dix Bay Tortola Virgin Gorda Road Town Spanish Town Road Harbour CSE-291: Ontologies in Data Integration Super-classes Scopes Geo Containment Geo Umschließung Caribbean Karibik Political Dependency Politische Abhängigkeit Brit. Virgin Islands Brit. Jungferninseln Great Britain Großbritannien Article Artikel Map Karte Image Bild BVI Welcome CSE-291: Ontologies in Data Integration SurfBVI CaribNet Scopes Scopes Geo Containment Geo Umschließung Caribbean Karibik Political Dependency Politische Abhängigkeit Brit. Virgin Islands Brit. Jungferninseln Great Britain Großbritannien Article Artikel Map Karte Image Bild BVI Welcome CSE-291: Ontologies in Data Integration SurfBVI CaribNet Scopes Scopes Geo Containment Geo Umschließung Caribbean Karibik Political Dependency Politische Abhängigkeit Brit. Virgin Islands Brit. Jungferninseln Great Britain Großbritannien Article Artikel Map Karte Image Bild BVI Welcome CSE-291: Ontologies in Data Integration SurfBVI CaribNet Names: English Deutsch Scopes Scopes Geo Containment Geo Umschließung Caribbean Karibik Political Dependency Politische Abhängigkeit Brit. Virgin Islands Brit. Jungferninseln Great Britain Großbritannien Article Artikel Names: English Deutsch Occurrences: Map Karte Public Confidential Image Bild BVI Welcome CSE-291: Ontologies in Data Integration SurfBVI CaribNet Scopes Scopes Geo Containment Geo Umschließung Political Dependency Politische Abhängigkeit Associations: Geography Politics Caribbean Karibik Brit. Virgin Islands Brit. Jungferninseln Great Britain Großbritannien Article Artikel Names: English Deutsch Occurrences: Map Karte Public Confidential Image Bild BVI Welcome CSE-291: Ontologies in Data Integration SurfBVI CaribNet Scope Examples: English, Public, Politics Scopes Geo Containment Associations: Political Dependency Geography Politics Caribbean Brit. Virgin Islands Great Britain Article Names: English Deutsch Occurrences: Map Public Confidential Image BVI Welcome CSE-291: Ontologies in Data Integration SurfBVI CaribNet In-/Semi-formal approaches: Topic Maps, Thesauri Advantages Disadvantages • Capture a lot of modeling experiences • No characterization independent from particular implementation • Intuitive • Interesting primitives that are not available in other approaches (TM) CSE-291: Ontologies in Data Integration • May be misinterpreted (TM) / few primitives (Thesauri) Common errors about ontology representation languages AI people‘s errors Engineer‘s errors • „it is good if it is formal“ • „it works in my application, thus it is good“ • „it is good if someone with a logic background may easily use it“ • „who needs formality anyway?“ • „it is good if the language allows everything“ • „it did not work when I looked at it 10 years ago“ CSE-291: Ontologies in Data Integration Review/Introduction: (Classical) First-order [Predicate] Logic: Short: FO or PL1 CSE-291: Ontologies in Data Integration But first: Propositional Logic: Syntax propositional logic logic> (or "propositional calculus") A system of symbolic logic using symbols to stand for whole propositions and logical connectives. Propositional logic only considers whether a proposition is true or false. In contrast to predicate logic, it does not consider the internal structure of propositions. http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?propositional+logic < • propositions (no internal structure) can be assigned a truth-value: – either true or false (classical 2-valued logic: tertium non datur) • Logical symbols: – conjunction: , disjunction: , negation: , – implication: , equivalence: , parentheses: • Non-logical symbols: – propositional variables p, q, r, ... – signature: set of propositional variables = {p, q, r, ...} • Formation rules for well-formed formulas (wff) – an atomic formula (propositional variable) is a formula – if F, G are formulas, so are: • FG, F G, F, FG , FG, F CSE-291: Ontologies in Data Integration Propositional Logic: Semantics • An interpretation I over a signature is a mapping – I: {true, false} , associating a truth value to every propositional variable • Truth tables describe how to extend I from to composite formulas (Boolean Algebra): – FG, F G, F, FG , FG CSE-291: Ontologies in Data Integration Boolean Algebra, Truth Tables http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?two-valued+logic CSE-291: Ontologies in Data Integration 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: x, y, ... • Formation rules for terms: – 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 CSE-291: Ontologies in Data Integration Syntax of First-Order Logic (FO) • Formation rules for formulas: – if t_1,...t_k are terms and p/k is a predicate symbol (of arity k) then p(t_1,...,p_k) is an atomic formula (short: atom) • all variable occurrences in p(t_1,..., t_k) are free – if F,G are formulas and x is a variable, then the following are formulas: – FG, F G, F, FG , FG, 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. CSE-291: Ontologies in Data Integration 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 CSE-291: Ontologies in Data Integration Semantics of Predicate Logic • Let D be a non-empty domain (a.k.a. domain of discourse, universe). A structure is a pair I = (D,I), with an interpretation I that maps ... – each constant 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): DkD • Given a structure I, and a set of variables X, a valuation is a mapping val: X D, used to evaluate terms and formulas over a given FO signature – with this: term evaluation val(t) yields a domain element, and formula evaluation val(F) yields a truth value CSE-291: Ontologies in Data Integration 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 CSE-291: Ontologies in Data Integration 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: 1. F_1, ..., F_k |= G 2. F_1 ... F_k G is valid 3. F_1 ... F_k G is unsatisfiable (inconsistent) CSE-291: Ontologies in Data Integration 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 CSE-291: Ontologies in Data Integration Description Logics Decidable Fragments of FO (aka terminological logics, member of concept languages) CSE-291: Ontologies in Data Integration Formalism for Ontologies: Description Logic • DL definition of “Happy Father” (Example from Ian Horrocks, U Manchester, UK) CSE-291: Ontologies in Data Integration Description Logic Statements as Rules • Another syntax: first-order logic in rule form (implicit quantifiers): happyFather(X) man(X), child(X,C1), child(X,C2), blue(C1), green(C2), not ( child(X,C3), poorunhappyChild(C3) ). poorunhappyChild(C) not rich(C), not happy(C). • Note: – the direction “” is implicit here (*sigh*) – see, e.g., Clark’s completion in Logic Programming CSE-291: Ontologies in Data Integration Description Logics • Terminological Knowledge (TBox) – Concept Definition (naming of concepts): – Axiom (constraining of concepts): => a mediators “glue knowledge source” • Assertional Knowledge (ABox) – the marked neuron in image 27 => the concrete instances/individuals of the concepts/classes that your sources export CSE-291: Ontologies in Data Integration Querying vs. Reasoning • Querying: – given a DB instance I (= logic interpretation), evaluate a query expression (e.g. SQL, FO formula, Prolog program, ...) – boolean query: check if I |= (i.e., if I is a model of ) – (ternary) query: { (X, Y, Z) | I |= (X,Y,Z) } => check happyFathers in a given database • Reasoning: – check if I |= implies I |= for all databases I, – i.e., if => – undecidable for FO, F-logic, etc. – Descriptions Logics are decidable fragments concept subsumption, concept hierarchy, classification semantic tableaux, resolution, specialized algorithms CSE-291: Ontologies in Data Integration Formalizing Glue Knowledge: Domain Map for SYNAPSE and NCMIR Domain Map = labeled graph with concepts ("classes") and roles ("associations") • additional semantics: expressed as logic rules Purkinje cells and Pyramidal cells have dendrites that have higher-order branches that contain spines. Dendritic spines are ion (calcium) regulating components. Spines have ion binding proteins. Neurotransmission involves ionic activity (release). Ion-binding proteins control ion activity (propagation) in a cell. Ion-regulating components of cells affect ionic activity (release). Domain Expert Knowledge Domain Map (DM) CSE-291: Ontologies in Data Integration DM in Description Logic Source Contextualization & DM Refinement In addition to registering (“hanging off”) data relative to existing concepts, a source may also refine the mediator’s domain map... sources can register new concepts at the mediator ... CSE-291: Ontologies in Data Integration