Output constraints in multimedia database systems [Elektronische Ressource] / von Thomas Heimrich
163 pages
Deutsch
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Output constraints in multimedia database systems [Elektronische Ressource] / von Thomas Heimrich

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
163 pages
Deutsch

Description

Output Constraintsin Multimedia Database SystemsDissertation zur Erlangung des akademischen GradesDoktor–Ingenieur (Dr. Ing.)vorgelegt der Fakultat¨ fur¨ Informatik und Automatisierungder Technischen Universitat¨ Ilmenauvon Dipl.–Inf. Thomas Heimrich1. Gutachter: Prof. Dr. habil. Kai Uwe Sattler2. Prof. Dr. Klaus Meyer Wegener¨3. Gutachter: Prof. Tamer OzsuTag der Einreichung: 19.09.2005Tag der wissenschaftlichen Aussprache: 13.02.2006urn:nbn:de:gbv:ilm1 2006000019ZusammenfassungSemantische Fehler treten bei jeder Art von Datenverwaltung auf. Herkommliche¨Datenbanksysteme verwenden eine Integritatsk¨ ontrolle, um semantische Fehler zu ver-meiden. Um die Integritat¨ der Daten zu gewahrleisten¨ werden Integritatsre¨ geln be nutzt. Diese Regeln konnen¨ allerdings nur die Konsistenz einfach strukturierter Datenuberpr¨ ufen.¨Multimedia Datenbanksystem verwalten neben einfachen alphanumerischen Datenauch komplexe Mediendaten wie Videos. Um die Konsistenz dieser Daten zu sichern,bedarf es einer erheblichen Erweiterung des bestehenden Integritatsk¨ onzeptes. Dabeimuss besonders auf die konsistente Datenausgabe geachtet werden. Im Gegensatz zualphanumerischen Daten konnen¨ Mediendaten wahrend¨ der Ausgabe verfalscht¨ wer-den. Dieser Fall kann eintreten, wenn eine geforderte Datenqualitat¨ bei der Ausgabenicht erreicht werden kann oder wenn Synchronisationsbedingungen zwischen Me dienobjekten nicht eingehalten werden konnen.

Sujets

Informations

Publié par
Publié le 01 janvier 2006
Nombre de lectures 13
Langue Deutsch
Poids de l'ouvrage 1 Mo

Exrait

Output Constraints
in Multimedia Database Systems
Dissertation zur Erlangung des akademischen Grades
Doktor–Ingenieur (Dr. Ing.)
vorgelegt der Fakultat¨ fur¨ Informatik und Automatisierung
der Technischen Universitat¨ Ilmenau
von Dipl.–Inf. Thomas Heimrich
1. Gutachter: Prof. Dr. habil. Kai Uwe Sattler
2. Prof. Dr. Klaus Meyer Wegener
¨3. Gutachter: Prof. Tamer Ozsu
Tag der Einreichung: 19.09.2005
Tag der wissenschaftlichen Aussprache: 13.02.2006
urn:nbn:de:gbv:ilm1 2006000019Zusammenfassung
Semantische Fehler treten bei jeder Art von Datenverwaltung auf. Herkommliche¨
Datenbanksysteme verwenden eine Integritatsk¨ ontrolle, um semantische Fehler zu ver-
meiden. Um die Integritat¨ der Daten zu gewahrleisten¨ werden Integritatsre¨ geln be
nutzt. Diese Regeln konnen¨ allerdings nur die Konsistenz einfach strukturierter Daten
uberpr¨ ufen.¨
Multimedia Datenbanksystem verwalten neben einfachen alphanumerischen Daten
auch komplexe Mediendaten wie Videos. Um die Konsistenz dieser Daten zu sichern,
bedarf es einer erheblichen Erweiterung des bestehenden Integritatsk¨ onzeptes. Dabei
muss besonders auf die konsistente Datenausgabe geachtet werden. Im Gegensatz zu
alphanumerischen Daten konnen¨ Mediendaten wahrend¨ der Ausgabe verfalscht¨ wer-
den. Dieser Fall kann eintreten, wenn eine geforderte Datenqualitat¨ bei der Ausgabe
nicht erreicht werden kann oder wenn Synchronisationsbedingungen zwischen Me
dienobjekten nicht eingehalten werden konnen.¨ Es besteht daher die Notwendigkeit,
Ouptut Constraints einzufuhren.¨ Mit ihrer Hilfe kann definiert werden, wann die Aus
gabe von Mediendaten semantisch korrekt ist. Das Datenbanksystem kann diese Be
¨ ¨ ¨dingungen uberprufen und so gewahrleisten, dass der Nutzer semantisch einwandfreie
Daten erhalt.¨
In dieser Arbeit werden alle Aspekte betrachtet, die notwendig sind, um Aus
gabebedingungen in ein Multimedia Datenbanksystem zu integrieren. Im einzelnen
werden die Modellierung der Bedingungen, deren datenbankinterne Reprasentation¨
sowie die Bedingungsuberpr¨ ufung¨ betrachtet.
Fur¨ die Bedingungsmodellierung wird eine Constraint Language auf Basis der
Pradikatenlogik¨ eingefuhrt.¨ Um die Definition von zeitlichen und raumlichen¨ Syn
chronisationen zu ermoglichen,¨ verwenden wir Allen Relationen. Fur¨ die effiziente
¨ ¨ ¨Uberprufung der Ausgabebedingungen mussen diese aus der Spezifikationssprache in
eine datenbankinterne Darstellung uberf¨ uhrt¨ werden.
Fur¨ die Darstellung werden Difference Constraints verwendet.
Diese erlauben eine sehr effiziente Bedingungsuberpr¨ ufung.¨ Wir haben Algorithmen
¨entwickelt, die eine effiziente Uberprufung¨ von Ausgabebedingungen erlauben und
¨dies anhand von Experimenten nachgewiesen. Neben der Uberprufung¨ der Bedingun
gen mussen¨ Mediendaten so synchronisiert werden, dass dies den Ausgabebedingun
gen entspricht. Wir haben dazu das Konzept des Output Schedules entwickelt. Dieser
wird aufgrund der definierten Ausgabebedingungen generiert.
Durch die Ausgabebedingungen, die in dieser Arbeit eingefuhrt¨ werden, werden
semantische Fehler bei der Verwaltung von Mediendaten erheblich reduziert. Die Ar-
beit stellt daher einen Beitrag zur qualitativen Verbesserung der Verwaltung von Me
diendaten dar.Abstract
Semantic errors exist as long as data are managed. Traditional database systems try to
prevent this errors by proposing integrity concepts for stored data. Integrity constraints
are used to implement these integrity concepts. However, integrity constraints can only
detect semantic errors in elementary data.
Multimedia database systems manage elementary data as well as complex media
data, like videos. Considering these media data we need a much wider consistency
concept as traditional database systems provide. Especially, data output of media data
must be taken into account. In contrast to alphanumeric data the semantics of media
data can be falsified during data output if data quality or synchronization of data are
not suitable. Thus, we need a concept for output constraints that allow for preventing
semantic errors in case of data output. For integrating output constraints into a multi
media database system we have to consider modelling, representation and checking of
output constraints.
For modelling output constraints we have introduced a constraint language which
uses the same principles as traditional constraint languages. Our constraint specifica
tion language must support temporal and spatial synchronization constraints. How
ever, it is desired to both kinds of synchronization in almost the same manner.
Therefore, we use Allen Relations for defining temporal synchronization constraints
as well as for defining spatial synchronization constraints.
We need a database internal representation of output constraints that makes effi
cient constraint checking possible. The Allen Relations used in the constraint lan
guage cannot be checked efficiently. However, difference constraints are a class of
constraints that allows an very efficient checking. Therefore, we use difference con
straints as database internal representation of output constraints.
As methods for checking consistency of constraints we use an approach
based on graph theory as well as an analytical approach. Both approaches require a
constraint graph as data structure. For data output we need an output order that is
adequate to the defined output constraints. This ‘output schedule’ can be produced
based on the output constraints.
With output constraints, proposed in this thesis, semantical correctness of media
data considering the data output can be supported. Thus, the contribution of this work
is an qualitative improvement of managing media data by database systems.Acknowledgements
My thanks aim to all people who supported my work. Kai–Uwe Sattler, my supervi
sor, gave me the freedom to develop my own ideas and challenged them in numerous
discussions. Furthermore, he gave me the chance to write research papers and helped
me with many hints. Actually, Klaus Meyer–Wegener was my supervisor as well. He
helped me very much during the hard first time of my research. Furthermore, he gave
me the possibility of visiting him regularly which was always very useful. Thanks go
¨to Tamer Ozsu. He gave me the opportunity to visit him and his research group at
the University of Waterloo. I am very glad that he accepted to review this thesis. My
special thanks go to Katja Hose. She cleans up the English, found some content errors,
and made the thesis readable.Contents
1 Motivation 1
2 Requirements on Output Constraints 6
2.1 Wave Field Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Virtual University . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Hospital Database Application . . . . . . . . . . . . . . . . . . . . . 13
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Related Work 17
3.1 Data Models and Architecture of MMDBS . . . . . . . . . . . . . . . 17
3.1.1 Requirements on a Multimedia Database System . . . . . . . 17
3.1.2 Data Models for Systems . . . . . . . . 19
3.1.3 Architecture of Multimedia Database . . . . . . . . . 20
3.1.4 Existing Approaches for Multimedia Database Systems . . . . 22
3.2 Integrity Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.1 Types and Semantics of Integrity Constraints . . . . . . . . . 24
3.2.2 Specification of Integrity Constraints . . . . . . . . . . . . . 26
3.2.3 Checking of Integrity . . . . . . . . . . . . . . . 28
3.3 Presentation of Media Data . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.1 Quality of Service . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.2 Presentation Models for Multimedia Data . . . . . . . . . . . 31
3.4 Consistency Rules for Multimedia Data . . . . . . . . . . . . . . . . 35
3.4.1 Constraints on Data Quality . . . . . . . . . . . . . . . . . . 35
3.4.2 Temporal Consistency . . . . . . . . . . . . . . . . . . . . . 36
3.4.3 Spatialy . . . . . . . . . . . . . . . . . . . . . . . 38
3.4.4 Constraints in Commercial Database Systems . . . . . . . . . 39
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 Modelling of Output Constraints 41
4.1 Taxonomy of Output . . . . . . . . . . . . . . . . . . . . 41
4.2 A Classification of Output Constraints . . . . . . . . . . . . . . . . . 45
4.3 Fundamentals of Output . . . . . . . . . . . . . . . . . . 46
4.3.1 Elements of Constraint Notation . . . . . . . . . . . . . . . . 46
i4.3.2 Temporal Logic . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.3.3 Specification of Temporal Constraints . . . . . . . . . . . . . 49
4.3.4 of Spatial . . . . . . . . . . . . . . 50
4.4 The Database Output . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.5 General Structure of Output Constraints . . . . . . . . . . . . . . . . 54
4.6 Specification Language for Output Conditions . . . . . . . . . . . . . 55
4.6.1 Conditions for Static Output Parameters . . . . . . . . . . . . 56
4.6.2 for Dynamic Output P . . . . . . . . . . 57
4.6.3 Synchronization Conditions . . . . . . . . . . . . . . . . . . 61
4.7 Notation of Output Constraints . . . . . . . . . . . . . . . . . . . . . 65
4.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5 Internal Representation of Output Constraints 69
5.1 Process of Output Constraint Management . . . . . . . . . . . . . . . 69
5.2 Representation of Output Constraints . . . . . . . . . . . . . . . . . . 72
5.2.1 Output Constraints on Output Parameters . . . . . . . . . . . 72
5.2.2 for Synchronization . . . . . . . . . . . . 73
5.2.3 Transforming Temporal and Spatial Lengths . . . . . . . . . . 77
5.3 Storage Structure of Output Constraints . . . . . . . . . . . . . . . . 78
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6 Output Constraints and Data Consistency 80
6.1 Execution Model of Output Constraints . . . . . . . . . . . . . . . . 81
6.2 Consistency Check using Graph Theoretical Approach . . . . . . . . 82
6.3 Building a Partial Constraint Graph . . . . . . . . . . . . . . . . . . 84
6.3.1 Restrictions on Constraint Graphs . . . . . . . . . . . . . . . 84
6.3.2 Modifications of Allen Relations . . . . . . . . . . . . . . . . 85
6.3.3 of Output Objects . . . . . . . . . . . . . . . . 90
6.3.4 Algorithm for Building a Partial Graph . . . . . . . . . . . . 92
6.4 Consistency Check using Analytic Approach . . . . . . . . . . . . . 94
6.5 Auxiliary Data Structure for Checking Consistency . . . . . . . . . . 95
6.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7 Management of Output Schedules 97
7.1 Use Cases for Output . . . . . . . . . . . . . . . . . . . . 97
7.2 Producing an Schedule . . . . . . . . . . . . . . . . . . . . . 98
7.3 Structure of Output Schedules . . . . . . . . . . . . . . . . . . . . . 100
7.4 Consistency of Output . . . . . . . . . . . . . . . . . . . . 101
7.4.1 Modifying Allen Relations in the Front Section of the Output
Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.4.2 Modifying at the End of the Output Line . . . 104
7.4.3 Modifications on Output Objects . . . . . . . . . . . . . . . . 105
7.4.4 Output Schedules with Several Output Lines . . . . . . . . . 105