Deductive and Object-Oriented Databases (eBook)

Front Cover 1
Deductive and Object-Oriented Databases 4
Copyright Page 5
Table of Contents 10
GENERAL CHAIRPERSON'S MESSAGE 6
PROGRAM COMMITTEE CHAIRPERSONS' MESSAGE 8
DOOD89 14
External Referees 18
Program Committee Members 19
PART I: 
20 
Chapter 1. 
22 
ABSTRACT 22
PART II: A STATUS UPDATE ON DEDUCTIVE DATABASES 24
Chapter 2. Object Identity and Inheritance in Deductive Databases—an Evolutionary Approach 26
1 Introduction 26
2 Object Identifiers 27
3 Taking Advantage of Object Identities 31
4 Inheritance and Attribute Names 35
5 Conclusion 38
Acknowledgments 39
References 39
Chapter 3. 
41 
Chapter 4. Query Evaluation in Recursive Databases: Bottom-up and Top-down Reconciled 44
1. Introduction 44
2. Background 46
3. Fixpoint Procedures as Bottom-up Meta-interpreters 48
4. The Backward Fixpoint Procedure: Principle 49
5. The Backward Fixpoint Procedure Revisited 51
6. Specialization: The Logic of Magic 52
7. From SLD-Resolution to Fixpoint Computation 56
8. Conclusion 60
Acknowledgements 62
References 62
PART III: DEDUCTIVE QUERY EVALUATION 64
Chapter 5. 
66 
1 Introduction 66
2 Preliminaries 67
3 Termination in Finite EDBs 76
4 Termination in Infinite EDBs 78
5 Complexity and Conclusion 81
References 82
Chapter 6. 
84 
ABSTRACT 84
1. Introduction 84
2. A Motivating Example 86
3. General Outline 87
4. Manipulation of Level-Cycle Sets 87
5. Precompilation of a Cyclic EDB 89
6. Query Processing 92
7. A Comparison with Related Work 94
8. The Applicability of the LCM Method 97
9. Conclusions 99
Acknowledgements 99
References 99
Chapter 7. Distribution of Selections: The Missing Link between Strategies for Relational Databases and Deductive Databases 102
1. Introduction 102
2. Distribution of Selections for Datalog Queries 104
3. Distribution of Selections for General Recursive Queries 105
4. The Relationship of the Distribution of Selections to Other Methods 110
5. Conclusions 117
Acknowledgement 118
References 118
Appendix Proofs of lemma 3.5, theorem 3.7 and theorem 4.4 Proof of lemma 3.5 119
Chapter 8. Combining Deduction by Certainty with the Power of Magic 122
Abstract 122
1. Introduction 122
2. Quantitative Deductive Databases 123
3. Query Optimization in QDD 124
4. The QMagic Set Method 125
5. The Supplementary QMagic Set Method 134
6. Benchmark Results 136
7. Certainty-Guided Deduction 137
8. Summary and Conclusion 138
Appendix: Benchmark Results 140
Literature 138
Chapter 9. On Deductive Query Evaluation in the DedGin System 142
Abstract 142
1 Introduction 142
2 Basics on Deductive Query Processing: QSQ 145
3 Rule compilation in DedGin 149
4 Compile-time optimizations 152
5 Coordination at query-time 155
6 Engineering notes 158
7 Conclusion 160
Acknowledgments 161
References 161
Chapter 10. 
164 
1 Introduction 164
2 Detecting Redundant Derivations 166
3 Eliminating Redundant Derivations 168
4 Controlling Bottom-Up Query Processing 169
5 Controlling Top-Down Query Processing 170
6 Synthesizing and Transforming Control Expressions 171
7 Properties of Programs 177
8 Conclusion 178
9 References 178
10 Appendix 180
PART IV: 
182 
CHAPTER 11. A THEORY OF FUNCTIONAL DEPENDENCIES FOR OBJECT-ORIENTED DATA MODELS 184
1. INTRODUCTION 184
2. DEFINITIONS 185
3. PATH FUNCTIONAL DEPENDENCIES 190
4. DECISION PROCEDURES 195
5. APPLICATIONS 199
6. SUMMARY 201
ACKNOWLEDGEMENTS 202
REFERENCES 202
Chapter 12. 
204 
1. Introduction 204
2. Object Identity and Equality 206
3. Object Equality from Real World Data Modeling 208
4. Relational Concept and its Application 213
5. Summary 214
Acknowledgements 214
References 215
CHAPTER 13. A FORMAL SYSTEM FOR PRODUCING DEMONS FROM RULES IN AN OBJECT-ORIENTED DATABASE 222
1. INTRODUCTION 222
2. MOTIVATIONS 223
3. A FORMAL FRAMEWORK FOR LOGIC RESOLUTION 227
4. APPLICATION TO DEMON GENERATION 232
5. CONCLUSION 237
6. Acknowledgements 237
7. REFERENCES 237
PART V: 
240 
Chapter 14. The Object-Oriented Database System Manifesto 242
Abstract 242
1 Introduction 242
2 Mandatory features: the Golden Rules 244
3 Optional features: the goodies 253
4 Open choices 254
5 Conclusions 256
6 Acknowledgements 256
References 256
Chapter 15. Meta Operations for Type Management in Object-Oriented Databases 260
Abstract 260
1. Introduction 260
2. The Meaning of Schema Evolution 261
3. The Strategies for Schema Evolution 264
4. The System 267
5. Persistent Meta-Objects 268
6. Realizing Lazy Evaluation by Meta-Objects 270
7. Dynamical Switching of Strategies by Meta-Messages 274
8. Conclusion 275
Acknowledgment 275
References 275
CHAPRER 15. A TOOL KIT SYSTEM FOR THE SYNTHESIS AND THE MANAGEMENT OF ACTIVE MEDIA OBJECTS 278
1. INTRODUCTION 278
2. CONCEPTUAL MODELING IN IntelligentPad 280
3. IntelligentPad ARCHITECTURE 283
4. EXAMPLE PAD COMPOSITIONS 285
5. MANAGEMENT AND RETRIEVAL OF PADS 288
6. CONCLUSION 294
ACKNOWLEDGEMENT 295
REFERENCES 295
PART VI: OODB QUERIES 298
CHAPTER 16. OBJECT-ORIENTED QUERIES: EQUIVALENCE AND OPTIMIZATION 300
1. INTRODUCTION 300
2. THE ENCORE QUERY ALGEBRA 301
3. QUERY EQUIVALENCE 305
4. QUERY TRANSFORMATIONS AND OPTIMIZATION 307
5. SUMMARY 312
REFERENCES 313
Chapter 17. On Natural Joins in Object-Oriented Databases 316
1 Introduction 316
2 Motivating Examples 318
3 Basic Definition 320
4 Realizing Natural Join 323
5 Properties of Natural Join 325
6 Concluding Remarks 328
References 329
Chapter 18. Reloop, an Algebra Based Query Language for an Object-Oriented Database System 332
1 Introduction 332
2 The O2 Data Model 333
3 Presentation of the RELOOP Language 337
4 RELOOP Semantics Through an Algebra 341
5 The Steps to a RELOOP -> C02 Translation
6 Conclusion 349
References 349
Chapter 19. A Construction of the algebraic macro operators 351
PART VII: PANEL DISCUSSION 352
Chapter 20. Next Generation Database Management Systems Technology 354
ABSTRACT 354
1. Directions For Next Generation DBMS Technology 354
2. Performance Techniques For OO DBMS 358
3. Integrating Deductive and OO Paradigms 358
4. Multimedia Requirements For Next Generation DBMSs 360
5. Integrating Software technologies 361
6. OO DBMS As An Object Base Environment 362
7. OO versus Deductive Database Systems 362
8. Questions and Answers 363
9. References 365
PART VIII: DATALOG EXTENSION 366
CHAPTER 21. INTEGRATION OF FUNCTIONS DEFINED WITH REWRITING RULES IN DATALOG 368
1 INTRODUCTION 368
2 MOTIVATIONS 369
3 PRELIMINARIES ON REWRITING SYSTEMS 371
4 LANGUAGE 373
5 FIXPOINT AND BOUNDED SEMANTICS 378
6 CONCLUSION 385
ACKNOWLEDGEMENTS 386
References 386
Chapter 22. Possible Model Semantics for Disjunctive Databases 388
Abstract 388
1 Introduction 388
2 Possible Model Semantics for Disjunctive Databases 390
3 Stratified Disjunctive Databases 395
4 Procedural Interpretation 397
5 Summary 400
Acknowledgments 400
References 400
Chapter 23. The Well Founded Semantics for Disjunctive Logic Programs 404
Abstract 404
1 Introduction 404
2 Terminology 407
3 The Well-Founded Semantics 409
4 Procedural Semantics 415
5 Comparison with Other Approaches 416
6 Further Issues 419
7 Discussion 419
Acknowledgements 420
References 420
PART IX: INTEGRATING OBJECTS AND RULES 422
Chapter 24. Formal Models for Object Oriented Databases 424
Abstract 424
1 Introduction 424
2 A Structural Model — the Data Level 426
3 The Schema level 431
4 Declarative Languages 436
5 Higher Order Features 442
6 Conclusions 447
References 448
CHAPTER 25. HILOG: A HIGH-ORDER LOGIC PROGRAMMING LANGUAGE FOR NON-INF DEDUCTIVE DATABASES 450
Abstract 450
1 Introduction 450
2 THE HILOG LANGUAGE 452
3 THE SEMANTICS OF HILOG 454
4 AN EXAMPLE 466
5 CONCLUSIONS 468
REFERENCES 469
APPENDIX A : Definition of Unpacking 470
APPENDIX B : Proof Outlines 471
CHAPTER 26. TOWARDS A DEDUCTIVE OBJECT-ORIENTED DATABASE LANGUAGE 472
1 INTRODUCTION 472
2 THE MODEL 474
3 THE CORE LANGUAGE 478
4 EXTERNALS 480
5 OVERLOADING METHODS 481
7 METHODS AS PROCEDURES 485
8 EXPLICIT CONTROL 486
9 THE WINDOW CLASS 487
10 CONCLUSIONS 489
References 489
Chapter 27. Semantics and Evaluation of Rules over Complex Objects 492
Abstract 492
1 Introduction 492
2 The Complex Object Model 494
3 Requirements for a Rule-Based Language 498
4 Complex Rules and their Semantics 500
5 Evaluation of Complex Rules 506
6 Conclusion and Further Investigations 509
7 References 510
CHAPTER 28. INFERENCE RULES IN OBJECT ORIENTED PROGRAMMING SYSTEMS 512
1. INTRODUCTION 512
2. A MULTI-INHERITANCE LANGUAGE 513
3. INFERENCE RULES 515
4. THE INFERENTIAL OBJECT ORIENTED LANGUAGE 517
5. COMMENTS ON THE DESIGN OF THE LANGUAGE 519
6. A SUGGESTED IMPLEMENTATION 520
7. COMMENTS ON THE IMPLEMENTATION 523
8. A SNEAK PREVIEW OF LOOP PREVENTION AND MEMOISATION 525
9. CONCLUDING REMARKS 526
ACKNOWLEDGEMENT 527
BIBLIOGRAPHY 527
CHAPTER 29. FEATURES OF THE TEDM OBJECT MODEL 530
1. Introduction and Motivation 530
2. TEDM Overview 531
3. Object Terms and An Object Space 535
4. An Extended Object Space 537
5. Data Manipulation Facilities 538
6. Rules and Deductions 542
7. Object Representation of Types and Commands 544
8. Dynamic Constructions of Database Programs 545
9. Summary and Concluding Remarks 545
References 546
Chapter 30. Software Process Modeling as a Strategy for KBMS Implementation 550
1 Introduction 550
2 An Object-Oriented Implementation Layer: The Concept Base Kernel 553
3 Rules and Constraints as Knowledge Base Objects 558
4 Knowledge Base Version and Configuration Management 562
5 User Interfaces as Configurations of Derived Data 565
6 Conclusion: Towards Incremental Object Development in KBMS 567
References 568
PART X: QUERY TRANSFORMATION 570
Chapter 31. Query Optimization for Database Programming Languages 572
Abstract 572
1. Introduction 572
2. FAD 573
3. Conceptual Level FAD 575
4. Internal Level FAD 576
5. Overview of the FAD Optimizer 577
6. The Language Module — RWR 579
7. The Optimizer Module — OPT 584
8. Conclusion 587
Acknowledgments 589
References 589
Chapter 32. Integrating Complex Objects and Recursion 592
1. Introduction 592
2. Recursion in a Complex Object Environment 594
3. Basic Concepts of the MAD Model 596
4. Recursion in the MAD Model: Transitive Closure 602
5. Solving Path Problems with the MAD Model 605
6. Further Comments on Functionality and Applications 607
7. Conclusions 609
8. Acknowledgments 610
9. References 610
Chapter 33. OOLP: A Translation Approach to Object-Oriented Logic Programming 612
Abstract 612
1 Introduction 612
2 OOLP Framework 614
3 OOLP+ 618
4 Related Work 621
5 Conclusions 622
References 623
AUTHOR INDEX 626