Kim / Nicolas / Nishio Deductive and Object-Oriented Databases

Proceedings of the First International Conference on Deductive and Object-Oriented Databases (DOOD89) Kyoto Research Park, Kyoto, Japan, 4-6 December 1989
1. Auflage 2014
ISBN: 978-1-4832-9819-1
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 625 Seiten, Web PDF

Deductive databases and object-oriented databases are at the forefront of research in next-generation intelligent database systems.Object-oriented programming and design methodologies have great potential, promising to reduce the complexity of very large software systems in such domains as computer-aided design and manufacturing, integrated office information systems, and artificial intelligence. Object-oriented database systems will enhance the programmer/user productivity of such systems. Research into deductive databases is aimed at discovering efficient schemes to uniformly represent assertions and deductive rules, and to respond to highly expressive queries against the knowledge base of assertions and rules. This area of research is strongly interacting with Logic Programming which has developed in parallel, sharing Logic as a common basis. Recently, research has aimed at integrating the object-oriented paradigm and rule-based deduction to provide a single powerful framework for intelligent database systems.The aim of this book is to present research papers and technical discussions between researchers concerned with deductive databases, object-oriented databases, and their integration.

Autoren/Hrsg.

Kim, W.

Nicolas, J. -M.

Nishio, S.

Inhaltsverzeichnis

1;Front Cover;1
2;Deductive and Object-Oriented Databases;4
3;Copyright Page;5
4;Table of Contents;10
5;GENERAL CHAIRPERSON'S MESSAGE;6
6;PROGRAM COMMITTEE CHAIRPERSONS' MESSAGE;8
7;DOOD89;14
8;External Referees;18
9;Program Committee Members;19
10;PART I:
KEYNOTE ADDRESS;20
10.1;Chapter 1.
Towards a New Step of Logic Paradigm;22
10.1.1;ABSTRACT;22
11;PART II: A STATUS UPDATE ON DEDUCTIVE DATABASES;24
11.1;Chapter 2. Object Identity and Inheritance in Deductive Databases—an Evolutionary Approach;26
11.1.1;1 Introduction;26
11.1.2;2 Object Identifiers;27
11.1.3;3 Taking Advantage of Object Identities;31
11.1.4;4 Inheritance and Attribute Names;35
11.1.5;5 Conclusion;38
11.1.6;Acknowledgments;39
11.1.7;References;39
11.2;Chapter 3.
A Choice Models and Stable Models;41
11.3;Chapter 4. Query Evaluation in Recursive Databases: Bottom-up and Top-down Reconciled;44
11.3.1;1. Introduction;44
11.3.2;2. Background;46
11.3.3;3. Fixpoint Procedures as Bottom-up Meta-interpreters;48
11.3.4;4. The Backward Fixpoint Procedure: Principle;49
11.3.5;5. The Backward Fixpoint Procedure Revisited;51
11.3.6;6. Specialization: The Logic of Magic;52
11.3.7;7. From SLD-Resolution to Fixpoint Computation;56
11.3.8;8. Conclusion;60
11.3.9;Acknowledgements;62
11.3.10;References;62
12;PART III: DEDUCTIVE QUERY EVALUATION;64
12.1;Chapter 5.
On Termination of Datalog Programs;66
12.1.1;1 Introduction;66
12.1.2;2 Preliminaries;67
12.1.3;3 Termination in Finite EDBs;76
12.1.4;4 Termination in Infinite EDBs;78
12.1.5;5 Complexity and Conclusion;81
12.1.6;References;82
12.2;Chapter 6.
The Level-Cycle Merging Method;84
12.2.1;ABSTRACT;84
12.2.2;1. Introduction;84
12.2.3;2. A Motivating Example;86
12.2.4;3. General Outline;87
12.2.5;4. Manipulation of Level-Cycle Sets;87
12.2.6;5. Precompilation of a Cyclic EDB;89
12.2.7;6. Query Processing;92
12.2.8;7. A Comparison with Related Work;94
12.2.9;8. The Applicability of the LCM Method;97
12.2.10;9. Conclusions;99
12.2.11;Acknowledgements;99
12.2.12;References;99
12.3;Chapter 7. Distribution of Selections: The Missing Link between Strategies for Relational Databases and Deductive Databases;102
12.3.1;1. Introduction;102
12.3.2;2. Distribution of Selections for Datalog Queries;104
12.3.3;3. Distribution of Selections for General Recursive Queries;105
12.3.4;4. The Relationship of the Distribution of Selections to Other Methods;110
12.3.5;5. Conclusions;117
12.3.6;Acknowledgement;118
12.3.7;References;118
12.3.8;Appendix Proofs of lemma 3.5, theorem 3.7 and theorem 4.4 Proof of lemma 3.5;119
12.4;Chapter 8. Combining Deduction by Certainty with the Power of Magic;122
12.4.1;Abstract;122
12.4.2;1. Introduction;122
12.4.3;2. Quantitative Deductive Databases;123
12.4.4;3. Query Optimization in QDD;124
12.4.5;4. The QMagic Set Method;125
12.4.6;5. The Supplementary QMagic Set Method;134
12.4.7;6. Benchmark Results;136
12.4.8;7. Certainty-Guided Deduction;137
12.4.9;8. Summary and Conclusion;138
12.4.10;Appendix: Benchmark Results;140
12.4.11;Literature;138
12.5;Chapter 9. On Deductive Query Evaluation in the DedGin System;142
12.5.1;Abstract;142
12.5.2;1 Introduction;142
12.5.3;2 Basics on Deductive Query Processing: QSQ;145
12.5.4;3 Rule compilation in DedGin;149
12.5.5;4 Compile-time optimizations;152
12.5.6;5 Coordination at query-time;155
12.5.7;6 Engineering notes;158
12.5.8;7 Conclusion;160
12.5.9;Acknowledgments;161
12.5.10;References;161
12.6;Chapter 10.
Detecting and Eliminating Redundant Derivations in Logic Knowledge Bases;164
12.6.1;1 Introduction;164
12.6.2;2 Detecting Redundant Derivations;166
12.6.3;3 Eliminating Redundant Derivations;168
12.6.4;4 Controlling Bottom-Up Query Processing;169
12.6.5;5 Controlling Top-Down Query Processing;170
12.6.6;6 Synthesizing and Transforming Control Expressions;171
12.6.7;7 Properties of Programs;177
12.6.8;8 Conclusion;178
12.6.9;9 References;178
12.6.10;10 Appendix;180
13;PART IV:
OODB THEORY;182
13.1;CHAPTER 11. A THEORY OF FUNCTIONAL DEPENDENCIES FOR OBJECT-ORIENTED DATA MODELS;184
13.1.1;1. INTRODUCTION;184
13.1.2;2. DEFINITIONS;185
13.1.3;3. PATH FUNCTIONAL DEPENDENCIES;190
13.1.4;4. DECISION PROCEDURES;195
13.1.5;5. APPLICATIONS;199
13.1.6;6. SUMMARY;201
13.1.7;ACKNOWLEDGEMENTS;202
13.1.8;REFERENCES;202
13.2;Chapter 12.
Object Identity, Equality and Relational Concept;204
13.2.1;1. Introduction;204
13.2.2;2. Object Identity and Equality;206
13.2.3;3. Object Equality from Real World Data Modeling;208
13.2.4;4. Relational Concept and its Application;213
13.2.5;5. Summary;214
13.2.6;Acknowledgements;214
13.2.7;References;215
13.3;CHAPTER 13. A FORMAL SYSTEM FOR PRODUCING DEMONS FROM RULES IN AN OBJECT-ORIENTED DATABASE;222
13.3.1;1. INTRODUCTION;222
13.3.2;2. MOTIVATIONS;223
13.3.3;3. A FORMAL FRAMEWORK FOR LOGIC RESOLUTION;227
13.3.4;4. APPLICATION TO DEMON GENERATION;232
13.3.5;5. CONCLUSION;237
13.3.6;6. Acknowledgements;237
13.3.7;7. REFERENCES;237
14;PART V:
OODB FEATURES;240
14.1;Chapter 14. The Object-Oriented Database System Manifesto;242
14.1.1;Abstract;242
14.1.2;1 Introduction;242
14.1.3;2 Mandatory features: the Golden Rules;244
14.1.4;3 Optional features: the goodies;253
14.1.5;4 Open choices;254
14.1.6;5 Conclusions;256
14.1.7;6 Acknowledgements;256
14.1.8;References;256
14.2;Chapter 15. Meta Operations for Type Management in Object-Oriented Databases;260
14.2.1;Abstract;260
14.2.2;1. Introduction;260
14.2.3;2. The Meaning of Schema Evolution;261
14.2.4;3. The Strategies for Schema Evolution;264
14.2.5;4. The System;267
14.2.6;5. Persistent Meta-Objects;268
14.2.7;6. Realizing Lazy Evaluation by Meta-Objects;270
14.2.8;7. Dynamical Switching of Strategies by Meta-Messages;274
14.2.9;8. Conclusion;275
14.2.10;Acknowledgment;275
14.2.11;References;275
14.3;CHAPRER 15. A TOOL KIT SYSTEM FOR THE SYNTHESIS AND THE MANAGEMENT OF ACTIVE MEDIA OBJECTS;278
14.3.1;1. INTRODUCTION;278
14.3.2;2. CONCEPTUAL MODELING IN IntelligentPad;280
14.3.3;3. IntelligentPad ARCHITECTURE;283
14.3.4;4. EXAMPLE PAD COMPOSITIONS;285
14.3.5;5. MANAGEMENT AND RETRIEVAL OF PADS;288
14.3.6;6. CONCLUSION;294
14.3.7;ACKNOWLEDGEMENT;295
14.3.8;REFERENCES;295
15;PART VI: OODB QUERIES;298
15.1;CHAPTER 16. OBJECT-ORIENTED QUERIES: EQUIVALENCE AND OPTIMIZATION;300
15.1.1;1. INTRODUCTION;300
15.1.2;2. THE ENCORE QUERY ALGEBRA;301
15.1.3;3. QUERY EQUIVALENCE;305
15.1.4;4. QUERY TRANSFORMATIONS AND OPTIMIZATION;307
15.1.5;5. SUMMARY;312
15.1.6;REFERENCES;313
15.2;Chapter 17. On Natural Joins in Object-Oriented Databases;316
15.2.1;1 Introduction;316
15.2.2;2 Motivating Examples;318
15.2.3;3 Basic Definition;320
15.2.4;4 Realizing Natural Join;323
15.2.5;5 Properties of Natural Join;325
15.2.6;6 Concluding Remarks;328
15.2.7;References;329
15.3;Chapter 18. Reloop, an Algebra Based Query Language for an Object-Oriented Database System;332
15.3.1;1 Introduction;332
15.3.2;2 The O2 Data Model;333
15.3.3;3 Presentation of the RELOOP Language;337
15.3.4;4 RELOOP Semantics Through an Algebra;341
15.3.5;5 The Steps to a RELOOP -> C02 Translation;346
15.3.6;6 Conclusion;349
15.3.7;References;349
15.4;Chapter 19. A Construction of the algebraic macro operators;351
16;PART VII: PANEL DISCUSSION;352
16.1;Chapter 20. Next Generation Database Management Systems Technology;354
16.1.1;ABSTRACT;354
16.1.2;1. Directions For Next Generation DBMS Technology;354
16.1.3;2. Performance Techniques For OO DBMS;358
16.1.4;3. Integrating Deductive and OO Paradigms;358
16.1.5;4. Multimedia Requirements For Next Generation DBMSs;360
16.1.6;5. Integrating Software technologies;361
16.1.7;6. OO DBMS As An Object Base Environment;362
16.1.8;7. OO versus Deductive Database Systems;362
16.1.9;8. Questions and Answers;363
16.1.10;9. References;365
17;PART VIII: DATALOG EXTENSION;366
17.1;CHAPTER 21. INTEGRATION OF FUNCTIONS DEFINED WITH REWRITING RULES IN DATALOG;368
17.1.1;1 INTRODUCTION;368
17.1.2;2 MOTIVATIONS;369
17.1.3;3 PRELIMINARIES ON REWRITING SYSTEMS;371
17.1.4;4 LANGUAGE;373
17.1.5;5 FIXPOINT AND BOUNDED SEMANTICS;378
17.1.6;6 CONCLUSION;385
17.1.7;ACKNOWLEDGEMENTS;386
17.1.8;References;386
17.2;Chapter 22. Possible Model Semantics for Disjunctive Databases;388
17.2.1;Abstract;388
17.2.2;1 Introduction;388
17.2.3;2 Possible Model Semantics for Disjunctive Databases;390
17.2.4;3 Stratified Disjunctive Databases;395
17.2.5;4 Procedural Interpretation;397
17.2.6;5 Summary;400
17.2.7;Acknowledgments;400
17.2.8;References;400
17.3;Chapter 23. The Well Founded Semantics for Disjunctive Logic Programs;404
17.3.1;Abstract;404
17.3.2;1 Introduction;404
17.3.3;2 Terminology;407
17.3.4;3 The Well-Founded Semantics;409
17.3.5;4 Procedural Semantics;415
17.3.6;5 Comparison with Other Approaches;416
17.3.7;6 Further Issues;419
17.3.8;7 Discussion;419
17.3.9;Acknowledgements;420
17.3.10;References;420
18;PART IX: INTEGRATING OBJECTS AND RULES;422
18.1;Chapter 24. Formal Models for Object Oriented Databases;424
18.1.1;Abstract;424
18.1.2;1 Introduction;424
18.1.3;2 A Structural Model — the Data Level;426
18.1.4;3 The Schema level;431
18.1.5;4 Declarative Languages;436
18.1.6;5 Higher Order Features;442
18.1.7;6 Conclusions;447
18.1.8;References;448
18.2;CHAPTER 25. HILOG: A HIGH-ORDER LOGIC PROGRAMMING LANGUAGE FOR NON-INF DEDUCTIVE DATABASES;450
18.2.1;Abstract;450
18.2.2;1 Introduction;450
18.2.3;2 THE HILOG LANGUAGE;452
18.2.4;3 THE SEMANTICS OF HILOG;454
18.2.5;4 AN EXAMPLE;466
18.2.6;5 CONCLUSIONS;468
18.2.7;REFERENCES;469
18.2.8;APPENDIX A : Definition of Unpacking;470
18.2.9;APPENDIX B : Proof Outlines;471
18.3;CHAPTER 26. TOWARDS A DEDUCTIVE OBJECT-ORIENTED DATABASE LANGUAGE;472
18.3.1;1 INTRODUCTION;472
18.3.2;2 THE MODEL;474
18.3.3;3 THE CORE LANGUAGE;478
18.3.4;4 EXTERNALS;480
18.3.5;5 OVERLOADING METHODS;481
18.3.6;7 METHODS AS PROCEDURES;485
18.3.7;8 EXPLICIT CONTROL;486
18.3.8;9 THE WINDOW CLASS;487
18.3.9;10 CONCLUSIONS;489
18.3.10;References;489
18.4;Chapter 27. Semantics and Evaluation of Rules over Complex Objects;492
18.4.1;Abstract;492
18.4.2;1 Introduction;492
18.4.3;2 The Complex Object Model;494
18.4.4;3 Requirements for a Rule-Based Language;498
18.4.5;4 Complex Rules and their Semantics;500
18.4.6;5 Evaluation of Complex Rules;506
18.4.7;6 Conclusion and Further Investigations;509
18.4.8;7 References;510
18.5;CHAPTER 28. INFERENCE RULES IN OBJECT ORIENTED PROGRAMMING SYSTEMS;512
18.5.1;1. INTRODUCTION;512
18.5.2;2. A MULTI-INHERITANCE LANGUAGE;513
18.5.3;3. INFERENCE RULES;515
18.5.4;4. THE INFERENTIAL OBJECT ORIENTED LANGUAGE;517
18.5.5;5. COMMENTS ON THE DESIGN OF THE LANGUAGE;519
18.5.6;6. A SUGGESTED IMPLEMENTATION;520
18.5.7;7. COMMENTS ON THE IMPLEMENTATION;523
18.5.8;8. A SNEAK PREVIEW OF LOOP PREVENTION AND MEMOISATION;525
18.5.9;9. CONCLUDING REMARKS;526
18.5.10;ACKNOWLEDGEMENT;527
18.5.11;BIBLIOGRAPHY;527
18.6;CHAPTER 29. FEATURES OF THE TEDM OBJECT MODEL;530
18.6.1;1. Introduction and Motivation;530
18.6.2;2. TEDM Overview;531
18.6.3;3. Object Terms and An Object Space;535
18.6.4;4. An Extended Object Space;537
18.6.5;5. Data Manipulation Facilities;538
18.6.6;6. Rules and Deductions;542
18.6.7;7. Object Representation of Types and Commands;544
18.6.8;8. Dynamic Constructions of Database Programs;545
18.6.9;9. Summary and Concluding Remarks;545
18.6.10;References;546
18.7;Chapter 30. Software Process Modeling as a Strategy for KBMS Implementation;550
18.7.1;1 Introduction;550
18.7.2;2 An Object-Oriented Implementation Layer: The Concept Base Kernel;553
18.7.3;3 Rules and Constraints as Knowledge Base Objects;558
18.7.4;4 Knowledge Base Version and Configuration Management;562
18.7.5;5 User Interfaces as Configurations of Derived Data;565
18.7.6;6 Conclusion: Towards Incremental Object Development in KBMS;567
18.7.7;References;568
19;PART X: QUERY TRANSFORMATION;570
19.1;Chapter 31. Query Optimization for Database Programming Languages;572
19.1.1;Abstract;572
19.1.2;1. Introduction;572
19.1.3;2. FAD;573
19.1.4;3. Conceptual Level FAD;575
19.1.5;4. Internal Level FAD;576
19.1.6;5. Overview of the FAD Optimizer;577
19.1.7;6. The Language Module — RWR;579
19.1.8;7. The Optimizer Module — OPT;584
19.1.9;8. Conclusion;587
19.1.10;Acknowledgments;589
19.1.11;References;589
19.2;Chapter 32. Integrating Complex Objects and Recursion;592
19.2.1;1. Introduction;592
19.2.2;2. Recursion in a Complex Object Environment;594
19.2.3;3. Basic Concepts of the MAD Model;596
19.2.4;4. Recursion in the MAD Model: Transitive Closure;602
19.2.5;5. Solving Path Problems with the MAD Model;605
19.2.6;6. Further Comments on Functionality and Applications;607
19.2.7;7. Conclusions;609
19.2.8;8. Acknowledgments;610
19.2.9;9. References;610
19.3;Chapter 33. OOLP: A Translation Approach to Object-Oriented Logic Programming;612
19.3.1;Abstract;612
19.3.2;1 Introduction;612
19.3.3;2 OOLP Framework;614
19.3.4;3 OOLP+;618
19.3.5;4 Related Work;621
19.3.6;5 Conclusions;622
19.3.7;References;623
20;AUTHOR INDEX;626