VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY
……..….***…………
MAI THUY NGA
QUERY PROCESSING AND OPTIMIZATION IN DISTRIBUTED OBJECT-ORIENTED DATABASES
DOCTORAL THESIS IN MATHEMATICS
Major: Mathematical Foundations for Informatics Code: 62 46 01 10
Scientific instructor:
1. Associate Professor, Dr. Doan Van Ban
2. Dr. Nguyen Manh Hung
HANOI – 2017
COMMITMENT
I hereby declare that this is my own research work. The results were written with co-authors and were approved by the authors before being included in the thesis. The results presented in the thesis are honest and have never been published in any other work.
Author
Mai Thuy Nga
THANK YOU
The thesis was completed at the Academy of Science and Technology, Vietnam Academy of Science and Technology. The author would like to express his sincere gratitude and deep respect to Associate Professor, Dr. Doan Van Ban. The author has received his dedicated guidance and valuable scientific research experience throughout his doctoral studies. The author also sincerely thanks Dr. Nguyen Manh Hung for his research orientation and comments to complete the thesis.
During my time as a PhD student, the author has received valuable knowledge and sincere comments from the teachers of the Academy of Science and Technology. The author would like to send the most sincere thanks to the teachers.
The author would like to sincerely thank the Board of Directors of the Institute of Information Technology, Academy of Science and Technology, the Graduate Student Management Department and the functional departments of the Institute of Information Technology and Academy of Science and Technology for creating favorable conditions during the author's study and research.
The author would like to thank the Board of Directors and the Department of Information Technology of Thang Long University for their support in all aspects to help the author complete his study tasks. Sincere thanks to the attention, encouragement and valuable contributions of colleagues.
Finally, the author would like to thank all family members, their encouragement and motivation is the motivation for the author to complete this thesis.
INDEX
TABLE OF CONTENTS i
GLOSSARY OF TERMS iv
ABBREVIATION OF TERMS
LIST OF ILLUSTRATIONS vi
LIST OF TABLES vii
INTRODUCTION 1
CHAPTER 1 - DISTRIBUTED OBJECT-ORIENTED DATABASE 7
1.1. Object-Oriented Database 7
1.1.1. Subject 8
1.1.2. Type and class 9
1.1.3. Component 11
1.1.4. Subclassing and Inheritance 12
1.2. Distributed object-oriented database 14
1.2.1. Distributed object-oriented database model 14
1.2.2. Advantages of Distributed Database 15
1.2.3. Problems to be solved in distributed databases 16
1.2.4. Distributed object-oriented database architecture 20
1.2.5. Object Management 22
1.2.6. Transaction Management 25
1.3. Performance evaluation of HDT database with OO7 library 25
1.3.1. Introduction 25
1.3.2. Some other studies on performance evaluation of HDT database 26
1.3.3. OO7 Database Design 27
1.3.4. Performance Evaluation Scenario 30
1.3.5. Experimental results 32
1.4. Conclusion of chapter 1 36
CHAPTER 2 - FRAGMENTATION AND CLASS ALLOCATION OF DISTRIBUTED OBJECTS 37
2.1. Fragmentation and class allocation of objects 38
2.1.1. Objectives of fragmentation and allocation 38
2.1.2. Fragmentation of object layers 38
2.1.3. Class 41 allocation
2.2. Input information of vertical fragmentation and layer allocation problem 42
2.2.1. Information about Database 42
2.2.2. Application information 45
2.2.3. Network information 48
2.2.4. Table of symbols used 48
2.3. Objective function of fragmentation and allocation 49
2.4. Transform input parameters according to the relationships 50
2.5. AttrFrag algorithm for fragmentation based on attribute 54
2.5.1. Building a query matrix using attribute 54
2.5.2. Building attribute correlation matrix 55
2.5.3. Using BEA algorithm to fragment 55
2.5.4. Adding methods to fragments 57
2.5.5. AttrFrag algorithm for fragmentation based on attribute correlation 57
2.6. FragAlloS algorithm for concurrent fragmentation and allocation of 58
2.6.1. Cost model 59
2.6.2. FragAlloS 60 algorithm
2.6.3. Illustrative example 62
2.6.4. Algorithm evaluation 63
2.6.5. Experimenting with FragAlloS algorithm on OO7 64
2.7. Comparison of algorithms 68
2.8. Conclusion of chapter 2 70
CHAPTER 3 - OPTIMIZING PATH EXPRESSIONS IN DISTRIBUTED OBJECT-ORIENTED DATABASES 72
3.1. Query processing in relational databases 72
3.1.1. Overview of distributed query processing 72
3.1.2. Query processing layers 77
3.2. Distributed Object Query Processing 83
3.2.1. Introduction 83
3.2.2. Object query optimization techniques 85
3.3. BloomOpt algorithm optimizes data transmission in path expression 88
3.3.1. Introduction 88
3.3.2. Query with path expression 89
3.3.3. Bloom 90 filter
3.3.4. Using Bloom filters to reduce communication costs 92
3.3.5. Discussion of parameters 97
3.4. Path Expression Optimization – PathExpOpt Algorithm 97
3.4.1. Graph representing queries as path expressions 97
3.4.2. Query optimization model 100
3.4.3. Split the query tree into induced subtrees 101
3.4.4. Optimization Principle 103
3.4.5. PathExpOpt 105 optimization algorithm
3.4.6. Complexity assessment and algorithm implementation 109
3.4.7. Experimental results 110
3.5. Conclusion of chapter 3 112
CONCLUSION 113
LIST OF AUTHOR'S WORKS 115
REFERENCES 116
GLOSSARY
Path expression | |
Bloom Filter | Bloom filter |
Sympathetic seedlings | Induced subtree |
Class allocation | Class allocation |
Browse objects | Object traversal |
Subgraph of the generative | Induced subgraph |
Complex object | Composite object |
Collection class/type | Collection class |
Object schema | Object schemas |
Cost model | Cost model |
Inheritance relationship | Inheritance relationship |
Class hierarchy | Class hierarchy |
Layer fragmentation | Class fragmentation |
Simple method | Simple method |
Complex method | Complex method |
Query optimization | Query optimization |
Simple properties | Simple attribute |
Complex properties | Complex attribute |
Maybe you are interested!
-
Query Processing and Optimization in Distributed Object-Oriented Databases - 17 -
Query Optimization in Distributed Databases - 11 -
Developing seafood processing industry in Tra Vinh province - 1 -
Classification of Wood Processing Enterprises by Economic Sector -
Food processing - restaurant operations - 2
ABBREVIATION OF TERMS
Database | |
PT Database (Distributed Database) | Distributed database |
Object Oriented Database (Object Oriented Database) | Object-Oriented Database |
Distributed Object Oriented Database (Distributed Object Oriented Database) | Distributed object-oriented database |
DDL (Data Definition Language) | Data Definition Language |
ODL (Object Definition Language) | Object definition language |
ODMG (Object Database Management Group) | Object Database Management Group, the organization that proposed the ODMG model and the OQL language |
OID (Object Identifier) | Object identifier |
OQL (Object Query Language) | Object Query Language |