Ontoloby based semantic query processing in database systems [Elektronische Ressource] / von Ben Necib Chokri

Chokri Ben Necib

Sujets

• Informatik

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2007
• Nombre de lectures: 26
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Ontology-based Semantic Query Processing in
Database Systems
DISSERTATION
zur Erlangung des akademischen Grades
doctor rerum naturalium
(Dr. rer. nat.)
im Fach Informatik
eingereicht an der
Mathematisch-Naturwissenschaftlichen Fakultät II
Humboldt-Universität zu Berlin
von
Herr Dipl.-Inf. Ben Necib Chokri
geboren am 07.01.1970 in Tunesien
Präsident der Humboldt-Universität zu Berlin:
Prof. Dr. Christoph Markschies
Dekan der Mathematisch-Naturwissenschaftlichen Fakultät II:
Prof. Dr. Wolfgang Coy
Gutachter:
1. Prof. Johann-Christoph Freytag, Ph.D.
2. Prof. Dr. Felix Naumann
3. Prof. Dr. Kai-Uwe Sattler
eingereicht am: 11. Dezember 2006
Tag der mündlichen Prüfung: 30. November 2007Abstract
Currently, database management systems solely rely on exact syntax of queries to
retrieve data. As consequence query answers often do not meet the user’s intention.
In this thesis we propose an ontology-based semantic query processing approach for
database systems. We use ontologies to transform a user query into another query
that may provide a more meaningful answer to the user. For this purpose, we define
and specify different mappings that relate concepts of an ontology with those of an
underlyingdatabaseanddevelopasetofalgorithmsthatallowustofindthesemappings
in a semi-automatic way. Moreover, we propose a set of semantic rules for transforming
queries using terms derived from the ontology. We classify the rules and demonstrate
their usefulness using practical examples. Furthermore, we make use of the theory of
term rewriting systems to formalize the transformation process and to study the basic
properties for applying these rules. Finally, we implement a prototype system using
current technologies and evaluate its capability by using a real world application.
Keywords:
Databases, Query Processing, Ontologies, SemanticZusammenfassung
Die Bedeutung der in den relationalen Datenbankmanagementsystemen dargestell-
ten Realwelt-Objekten wird weder explizit noch vollständig beschrieben. Demzufolge
treffenhäufigdieseSystememitdenAnfrageantwortennichtdieBenutzerabsichten.Die
vorliegende Dissertation präsentiert einen ontologie-basierten Ansatz für die semanti-
sche Anfrageverarbeitung. In diesem Ansatz sollen semantische Informationen aus ei-
ner gegebenen Ontologie abgeleitet und für die Umformulierung der Benutzeranfrage
verwendet werden. Dies führt zu einer neuen Anfrage, die für den Benutzer sinnvol-
lere Ergebnisse aus der Datenbank zurückliefern kann. Wir definieren und spezifizie-
ren Einschränkungen und Abbildungen zwischen der Ontologie- und den Datenbank-
Konzepten, um eine Ontologie mit einer Datenbank zu verknüpfen. Des Weiteren ent-
wickelnwireineReihevonAlgorithmen,dieunshelfen,dieseAbbildungenaufeinehalb-
automatische Weise zu finden. Außerdem entwickeln wir eine Reihe von semantischen
Regeln, die für die Umformulierung einer Anfrage benutzt werden. Die Haupteigen-
schaft einer Regel ist es, Begriffe einer Anfrage durch andere Begriffe zu ersetzen oder
anzureichern, die von denselben ontologischen Konzepten dargestellt werden. Weiterhin
benutzen wir die Theorie der Termersetzungssysteme, um den Transformationsprozess
zu formalisieren und die wesentlichen Eigenschaften für das Anwenden der Regeln zu
studieren. Aufbauend auf diesem Ansatz wurde ein Prototyp implementiert und wurde
die Fähigkeit unseres Ansatzes durch einer real existierenden Anwendung ausgewertet.
Schlagwörter:
Datenbanken, Anfragebearbeitung, Ontologien, SemantikivContents
1 Introduction 1
2 Query Processing in Databases 4
2.1 Database Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Relational Database Systems . . . . . . . . . . . . . . . . . . . 5
2.1.2 Queries, Query Languages . . . . . . . . . . . . . . . . . . . . . 7
2.1.3 Relational Calculus . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 Basic Steps of Query Processing . . . . . . . . . . . . . . . . . . 8
2.2.2 Query Rewriting for Optimization . . . . . . . . . . . . . . . . . 11
2.3 Algebraic Query Optimization . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.1 Standard Algebraic Transformation . . . . . . . . . . . . . . . . 12
2.3.2 Rule-based Transformation . . . . . . . . . . . . . . . . . . . . . 14
2.4 Semantic Query Optimization . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.1 Categories of Integrity Constraints . . . . . . . . . . . . . . . . 19
2.4.2 Transformation Heuristics . . . . . . . . . . . . . . . . . . . . . 21
2.4.3 Classification and Comparison . . . . . . . . . . . . . . . . . . . 22
2.5 Physical Query Optimization . . . . . . . . . . . . . . . . . . . . . . . 25
2.5.1 Transformation Heuristics . . . . . . . . . . . . . . . . . . . . . 25
2.5.2 Cost Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Semantic Knowledge 29
3.1 Syntax, Semantics, Models . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Semantic Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Ontologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.1 Definition of Ontologies . . . . . . . . . . . . . . . . . . . . . . 39
3.3.2 Describing real world objects . . . . . . . . . . . . . . . . . . . . 40
3.4 The Role of Ontologies . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5 Ontologies versus Conceptual Formalisms . . . . . . . . . . . . . . . . . 43
3.6 Ontology Representation . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.6.1 Kinds of Representation . . . . . . . . . . . . . . . . . . . . . . 46
3.6.2 Graph-based Representation . . . . . . . . . . . . . . . . . . . . 46
3.7 Problem Definition for this Thesis . . . . . . . . . . . . . . . . . . . . . 48
3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
v4 Query Processing Using Ontologies 52
4.1 Semantic Heterogeneity . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2 Use of Ontologies for Query Processing . . . . . . . . . . . . . . . . . . 54
4.2.1 Basis for Mediation . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.2 Query Enhancement . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3 Mappings between Ontologies and Databases . . . . . . . . . . . . . . . 56
4.3.1 Correspondences between Ontology Elements and Database Ex-
tension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.3.2 Mappings between Ontologies and Database Schemas . . . . . . 62
4.4 Mappings Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.4.1 Schema Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.4.2 Matching Process . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.4.3 Linguistic Matching . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.4.4 Structural Matching . . . . . . . . . . . . . . . . . . . . . . . . 72
4.4.5 Semantic Matching . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.5.1 Matching Approaches and Systems . . . . . . . . . . . . . . . . 76
4.5.2 Ontology-based Approaches and Systems . . . . . . . . . . . . . 80
4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5 Query Transformation Rules 87
5.1 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2 Term Rewriting Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.2.1 Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.2.2 Principles of Term Rewriting Systems . . . . . . . . . . . . . . . 90
5.2.3 A Rewriting System for Queries . . . . . . . . . . . . . . . . . . 91
5.3 The Set of Extension Rules . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.3.1 Synonymy Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.3.2 Collection Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.3.3 Part-Whole Rules . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.3.4 Support Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.3.5 Feature Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.3.6 Consistency Rules . . . . . . . . . . . . . . . . . . . . . . . . 103
5.4 The Set of Reduction Rules . . . . . . . . . . . . . . . . . . . . . . . . 110
5.4.1 Sensitivity Rules . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.5 The Basic Properties of the Rule Set . . . . . . . . . . . . . . . . . . . 114
5.5.1 Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.5.2 Confluence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.5.3 The Application Order of Rules . . . . . . . . . . . . . . . . . 119
5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6 ODBT-Prototype: From Concepts to Realization 123
6.1 Ontology Languages and Storage Tools . . . . . . . . . . . . . . . . . . 123
6.1.1 Using RDF for Modelling Ontologies . . . . . . . . . . . . . . . 124
6.1.2 OWL for Mo On . . . . . . . . . . . . . . . 127
vi6.1.3 Jena and Seasme . .