Deductive Databases and Their Applications

✍ Scribed by Robert Colomb

• Publisher: Taylor & Francis
• Year: 1998
• Tongue: English
• Leaves: 188
• Category: Library

✦ Synopsis

An introductory text aimed at those with an undergraduate knowledge of database & information systems describing the origins of deductive database in Prolog, & then goes on to analyse the main deductive database paradigm - the datalog model.

✦ Table of Contents

Book Cover......Page 1
Half-Title......Page 2
Dedication......Page 3
Title......Page 4
Copyright......Page 5
Contents......Page 6
Preface......Page 10
1.1 THE ORIGINS OF DEDUCTIVE DATABASE TECHNOLOGY......Page 11
1.2 SKETCH OF THE TECHNOLOGY......Page 12
1.3.1 Information systems......Page 13
1.3.2 Knowledge-based systems......Page 16
1.4 SKETCH OF THE MATHEMATICAL BASIS......Page 17
1.7 EXERCISES......Page 18
2.1 BASICS......Page 20
2.2.1 Logical view......Page 21
2.2.2 Implementation view......Page 26
2.3 NEGATED GOALS......Page 27
2.4 UPDATES......Page 29
2.5 ALL SOLUTIONS......Page 30
2.8 FURTHER READING......Page 31
2.9 EXERCISES......Page 32
3.1.2 Select......Page 33
3.1.3 Project......Page 34
3.1.5 Combinations......Page 35
3.2 PERSISTENT PROLOG IMPLEMENTATION......Page 36
3.3 RELATIONAL REPRESENTATION OF COMPLEX DATA TYPES......Page 37
3.3.1 Hierarchical data structures......Page 38
3.3.2 Homogeneous relationships......Page 39
3.3.3 Transitive data structures and graphs......Page 40
3.3.4 Elementary graph functions......Page 42
3.3.5 Identifying graph data structures in conceptual models......Page 43
3.6 EXERCISES......Page 44
4.1.1 Motivation and definition......Page 47
4.1.2 Naive algorithm for bottom-up evaluation......Page 48
4.1.4 Bottom-up versus top-down......Page 50
4.2 SEMI-NAIVE BOTTOM-UP ALGORITHM......Page 51
4.3 NEGATION AND STRATIFICATION......Page 53
4.4 AGGREGATION......Page 56
4.5 TOP-DOWN REVISITED......Page 59
4.6 THE ARTIFICIAL INTELLIGENCE PERSPECTIVE: PRODUCTION RULES......Page 60
4.8 STRUCTURE......Page 63
4.11 EXERCISES......Page 65
5.1.1 Functional associations......Page 67
5.1.2 Classifying objects......Page 68
5.1.3 Goal dependency......Page 69
5.1.4 Update/query types......Page 70
5.2.1 Information modelling......Page 71
5.2.2 Knowledge diagrams......Page 72
5.3 DESIGNING A KNOWLEDGE BASE......Page 75
5.4.2 Sample population......Page 77
5.4.3 Data/information model......Page 78
5.4.4 EDB definition......Page 79
5.4.6 Horn clause representation of knowledge......Page 80
5.5 OTHER FORMS OF KNOWLEDGE: PRODUCTION RULES......Page 81
5.8 EXERCISES......Page 82
Major exercise......Page 83
6.1 KNOWLEDGE ACQUISITION......Page 86
6.2.1 Data......Page 87
6.3 BUILDING THE KNOWLEDGE MODEL......Page 88
6.4.1 Overview......Page 89
6.4.2 Information repository......Page 90
6.4.3 Repository for knowledge......Page 92
6.4.5 Discussion......Page 94
6.5 THE CASE TOOL......Page 95
6.6 REPOSITORY AS A DEDUCTIVE DATABASE......Page 96
6.9 EXERCISES......Page 97
7.1 QUALITY AND MAINTAINABILITY......Page 99
7.2.3 Third normal form: no transitive dependencies......Page 100
7.3 QUALITY PRINCIPLES FOR DATA, INFORMATION AND KNOWLEDGE......Page 101
7.3.2 Quality principles for information......Page 102
7.3.3 Quality principles for knowledge......Page 104
7.5 DISCUSSION......Page 108
7.8 EXERCISES......Page 109
8.2 DATALOG AND RELATIONAL ALGEBRA REVISITED......Page 110
8.3.2 Unique binding property......Page 112
8.4 MAGIC SETS TRANSFORMATION......Page 114
8.4.3 Zeroth supplementary predicates......Page 116
8.4.5 IDB predicates......Page 117
8.5 LINEAR RECURSION......Page 121
8.8 EXERCISES......Page 124
9.1 UNFOLDING......Page 126
9.2 FOLDING......Page 128
9.3 EXAMPLE OF FOLDING AND UNFOLDING......Page 129
9.6 EXERCISES......Page 130
10.1 PROPOSITIONAL SYSTEMS......Page 131
10.1.1 Recursion, stratification and indeterminacy......Page 132
10.2.1 Application of unfolding......Page 133
10.2.3 Decision trees......Page 134
10.2.5 Uses of transformed systems......Page 135
10.4 SUMMARY......Page 136
10.6 EXERCISES......Page 137
11.1 UPDATES......Page 138
11.2 INTEGRITY CONSTRAINTS......Page 139
11.3 INTEGRITY CONSTRAINTS AS HORN CLAUSES......Page 140
11.4 EFFECT OF UPDATES......Page 141
11.5 DISCUSSION......Page 143
11.8 EXERCISES......Page 145
12.1 THE PROBLEM OF NON-MONOTONICITY......Page 146
12.2.1 Identification of conflicts......Page 147
12.2.2 Resolving the conflict: the concept of entrenchment......Page 148
12.2.3 Example: software maintenance as belief revision......Page 149
12.3.1 Motivation......Page 151
12.3.2 The ATMS system......Page 152
12.3.3 Discussion......Page 154
12.3.4 ATMS and deductive databases......Page 155
12.5 FURTHER READING......Page 156
12.6 EXERCISES......Page 157
Refresher on joins......Page 159
CHAPTER 2......Page 161
CHAPTER 4......Page 163
CHAPTER 5......Page 165
CHAPTER 6......Page 173
CHAPTER 7......Page 175
CHAPTER 8......Page 176
CHAPTER 9......Page 177
CHAPTER 11......Page 179
CHAPTER 12......Page 181
References......Page 184
Index......Page 185