Databases Samenvatting
Dieter Castel
Jonas Devlieghere
Karel Domin
Giel Dops
Dennis Frett
Kevin Fockaert
Kenneth Geets
John Gybels
Laurent Janssens
Ben Lefevere
13 januari 2015
Inhoudsopgave
1 Introduction to Databases
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Characteristics of the Database Approach . . . . . . . . . . . . . . . . . . . . . . .
1.3.1 Self-Describing Nature of a Database System . . . . . . . . . . . . . . . . . .
1.3.2 Insulation between Programs and Data, and Data Abstraction . . . . . . . .
1.3.3 Support of Multiple Views of the Data . . . . . . . . . . . . . . . . . . . . .
1.3.4 Sharing of Data and Multiuser Transaction Processing . . . . . . . . . . . .
1.4 Actors on the Scene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.1 Database Administrators . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.2 Database Designers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.3 End Users . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.4 System Analysts and Application Programmers (Software Engineers) . . . .
1.5 Workers behind the Scene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6 Advantages of Using the DBMS Approach . . . . . . . . . . . . . . . . . . . . . . .
1.6.1 Controlling Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.2 Restricting Unauthorized Access . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.3 Providing Persistent Storage for Program Objects . . . . . . . . . . . . . . .
1.6.4 Providing Storage Structures and Search Techniques for Efficient Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.5 Providing Backup and Recovery . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.6 Providing Multiple User Interfaces . . . . . . . . . . . . . . . . . . . . . . .
1.6.7 Representing Complex Relationships among Data . . . . . . . . . . . . . . .
1.6.8 Enforcing Integrity Constraints . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.9 Permitting Inferencing and Actions Using Rules . . . . . . . . . . . . . . . .
1.6.10 Additional Implications of Using the Database Approach . . . . . . . . . . .
1.8 When Not to Use a DBMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
10
10
11
11
11
11
11
12
12
12
12
12
12
13
13
13
13
2 Overview of Database Languages and Architectures
2.1 Data Models, Schemas, and Instances . . . . . . . . .
2.1.1 Categories of Data Models . . . . . . . . . . .
2.1.2 Schemas, Instances and Database State . . . .
2.2 Three-Schema Architecture and Data Independence .
2.2.1 The Three-Schema Architecture . . . . . . . .
2.2.2 Data Independence . . . . . . . . . . . . . . .
2.3 Database Languages and Interfaces . . . . . . . . . .
2.3.1 DBMS Languages . . . . . . . . . . . . . . . .
2.3.2 DBMS Interfaces . . . . . . . . . . . . . . . .
2.4 The Database System Environment . . . . . . . . . .
2.4.1 DBMS Component Modules . . . . . . . . . .
15
15
15
16
16
16
16
17
17
17
18
18
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
13
13
14
14
14
14
14
14
2.4.2 Database System Utilities . . . . . . . . . . . . . . . . . . . . . .
2.4.3 Tools, Application Environments, and Communications Facilities .
Centralized & Client/Server Architectures for DBMSs . . . . . . . . . . .
2.5.1 Centralized DBMSs Architecture . . . . . . . . . . . . . . . . . .
2.5.2 Basic Client/Server Architectures . . . . . . . . . . . . . . . . . .
2.5.3 Two-Tier Client/Server Architectures for DBMSs . . . . . . . . .
2.5.4 Three-Tier and n-Tier Architectures for Web Applications . . . .
Classification of Database Management Systems . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
18
18
18
19
19
19
19
3 The Basic (Flat) Relational Model
3.1 Relational Model Concepts . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Domains, Attributes, Tuples, and Relations . . . . . . . . . . . .
3.1.2 Characteristics of Relations . . . . . . . . . . . . . . . . . . . . .
3.1.3 Relational Model Notation . . . . . . . . . . . . . . . . . . . . . .
3.2 Relational Model Constraints and Relational Database Schemas . . . . .
3.2.1 Domain Constraints . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Key Constraints and Constraints on NULL values . . . . . . . . . .
3.2.3 Relational Databases and Relational Database Schemas . . . . . .
3.2.4 Integrity, Referential Integrity and Foreign Keys . . . . . . . . . .
3.2.5 Other Types of Constraints . . . . . . . . . . . . . . . . . . . . .
3.3 Update Operations, Transactions and Dealing with Constraint Violations
3.3.1 The Insert Operation . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2 The Delete Operation . . . . . . . . . . . . . . . . . . . . . . . .
3.3.3 The Update Operation . . . . . . . . . . . . . . . . . . . . . . . .
3.3.4 The Transaction Concept . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20
20
20
20
21
21
21
21
22
22
22
23
23
23
23
23
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
24
24
24
24
25
25
25
26
26
26
27
27
27
27
27
28
28
28
29
29
29
29
29
2.5
2.6
4 SQL: Data Definition, Constraints, and Basic Queries and Updates
4.1 SQL Data Definition and Data Types . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Schema and Catalog Concepts in SQL . . . . . . . . . . . . . . . . . .
4.1.2 The CREATE TABLE Command in SQL . . . . . . . . . . . . . . . .
4.1.3 Attribute Data Types and Domains in SQL . . . . . . . . . . . . . . .
4.2 Specifying Constraints in SQL . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 Specifying Attribute Constraints and Attribute Defaults . . . . . . . .
4.2.2 Specifying Key and Referential Integrity Constraints . . . . . . . . . .
4.2.3 Giving Names to Constraints . . . . . . . . . . . . . . . . . . . . . . .
4.2.4 Specifying Constraints on Tuples Using CHECK . . . . . . . . . . . . .
4.3 Basis Retrieval Queries in SQL . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 The SELECT-FROM-WHERE Structure of Basic SQL Queries . . . .
4.3.2 Ambiguous Attribute Names, Aliasing, Renaming, and Tuple Variables
4.3.3 Unspecified WHERE Clause and Use of the Asterisk . . . . . . . . . .
4.3.4 Tables as Sets in SQL . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.5 Substring Pattern Matching and Arithmetic Operators . . . . . . . . .
4.3.6 Ordering of Query Results . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.7 Discussion and Summary of Basic SQL Retrieval Queries . . . . . . . .
4.4 INSERT, DELETE, and UPDATE Statements in SQL . . . . . . . . . . . . .
4.4.1 The INSERT Command . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.2 The DELETE Command . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.3 The UPDATE Command . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Additional Features of SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5 SQL: Advanced Queries, Assertions, Triggers, and Views
5.1 More Complex SQL Retrieval Queries . . . . . . . . . . . . . .
5.1.1 Comparisons Involving NULL and Three-Valued Logic
5.1.2 Nested Queries, Tuples, and Set/Multiset Comparisons
5.1.3 Correlated Nested Queries . . . . . . . . . . . . . . . .
5.1.4 The EXISTS and UNIQUE Functions in SQL . . . . .
5.1.5 Explicit Sets and Renaming of Attributes in SQL . . .
5.1.6 Joined Tables in SQL and Outer Joins . . . . . . . . .
5.1.7 Aggregate Functions in SQL . . . . . . . . . . . . . . .
5.1.8 Grouping: The GROUP BY and HAVING Clauses . .
5.2 Specifying Constraints as Assertions and Actions as Triggers .
5.2.1 Specifying General Constraints as Assertions in SQL .
5.2.2 Introduction to Triggers in SQL . . . . . . . . . . . . .
5.3 Views (Virtual Tables) in SQL . . . . . . . . . . . . . . . . . .
5.3.1 Concept of a View in SQL . . . . . . . . . . . . . . . .
5.3.2 Specification of Views in SQL . . . . . . . . . . . . . .
5.3.3 View Implementation, View Update, and Inline Views .
5.4 Schema Change Statements in SQL . . . . . . . . . . . . . . .
5.4.1 The DROP Command . . . . . . . . . . . . . . . . . .
5.4.2 The ALTER Command . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
30
30
30
30
31
31
32
32
33
33
34
34
34
34
34
34
35
35
35
35
6 Formal Relational Languages: The Algebra and Calculus
6.1 Unary Relational Operations: SELECT & PROJECT . . . . . . . . . .
6.1.1 The SELECT Operation . . . . . . . . . . . . . . . . . . . . . .
6.1.2 The PROJECT Operation . . . . . . . . . . . . . . . . . . . . .
6.1.3 Sequences of Operations and the RENAME Operation . . . . .
6.2 Relational Algebra Operations from Set Theory . . . . . . . . . . . . .
6.2.1 The UNION, INTERSECTION, and MINUS Operations . . . .
6.2.2 The CARTESIAN PRODUCT (CROSS PRODUCT) Operation
6.3 Binary Relational Operations: JOIN and DIVISION . . . . . . . . . . .
6.3.1 The JOIN Operation . . . . . . . . . . . . . . . . . . . . . . . .
6.3.2 Variations of JOIN: The EQUIJOIN and NATURAL JOIN . . .
6.3.3 A Complete Set of Relational Algebra Operations . . . . . . . .
6.3.4 The DIVISION Operation . . . . . . . . . . . . . . . . . . . . .
6.3.5 Notation for Query Trees . . . . . . . . . . . . . . . . . . . . . .
6.4 Additional Relational Operations . . . . . . . . . . . . . . . . . . . . .
6.4.1 Generalized Projection . . . . . . . . . . . . . . . . . . . . . . .
6.4.2 Aggregate Functions and Grouping . . . . . . . . . . . . . . . .
6.4.3 Recursive Closure Operations . . . . . . . . . . . . . . . . . . .
6.4.4 OUTER JOIN Operations . . . . . . . . . . . . . . . . . . . . .
6.4.5 The OUTER UNION Operation . . . . . . . . . . . . . . . . . .
6.6 The Tuple Relational Calculus . . . . . . . . . . . . . . . . . . . . . . .
6.6.1 Tuple Variables and Range Relations . . . . . . . . . . . . . . .
6.6.2 Expressions and Formulas in Tuple Relational Calculus . . . . .
6.6.3 The Existential and Universal Quantifiers . . . . . . . . . . . .
6.6.4 Sample Queries in Tuple Relational Calculus . . . . . . . . . . .
6.6.5 Notation for Query Graphs . . . . . . . . . . . . . . . . . . . .
6.6.6 Transforming the Universal and Existential Quantifiers . . . . .
6.6.7 Using the Universal Quantifiers in Queries . . . . . . . . . . . .
6.6.8 Safe Expressions . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
36
36
36
37
37
38
38
39
39
39
40
41
41
42
42
42
43
44
44
44
45
45
46
46
46
46
47
47
47
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6.7
The Domain Relational Calculus
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
7 Conceptual Data Modeling Using Entities and Relationships
7.1 Using High-Level Conceptual Data Models for Database Design . . . . . . . . . . .
7.3 Entity Types, Entity Sets, Attributes, and Keys . . . . . . . . . . . . . . . . . . . .
7.3.1 Entities and Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3.2 Entity Types, Entity Sets, Keys, and Value Sets . . . . . . . . . . . . . . . .
7.4 Relationship Types, Relationship Sets, Roles & Structural Constraints . . . . . . . .
7.4.1 Relationship Types, Sets and Instances . . . . . . . . . . . . . . . . . . . . .
7.4.2 Relationship Degree, Role Names, and Recursive Relationships . . . . . . . .
7.4.3 Constraints on Binary Relationship Types . . . . . . . . . . . . . . . . . . .
7.4.4 Attributes of Relationship Types . . . . . . . . . . . . . . . . . . . . . . . .
7.5 Weak Entity Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.7 ER Diagrams, Naming Conventions, and Design Issues . . . . . . . . . . . . . . . .
7.7.1 Summary of Notation for ER Diagrams . . . . . . . . . . . . . . . . . . . . .
7.7.2 Proper Naming of Schema Constructs . . . . . . . . . . . . . . . . . . . . . .
7.7.3 Design Choices for ER Conceptual Design . . . . . . . . . . . . . . . . . . .
7.7.4 Alternative Notations for ER Diagrams . . . . . . . . . . . . . . . . . . . . .
7.8 Relationship Types of Degree Higher than Two . . . . . . . . . . . . . . . . . . . .
7.8.1 Choosing between Binary and Ternary (or Higher-Degree) Relationships . .
7.8.2 Constraints on Ternary (or Higher-Degree) Relationships . . . . . . . . . . .
7.9 Subclasses, Superclasses, and Inheritance . . . . . . . . . . . . . . . . . . . . . . . .
7.10 Specialization and Generalization in EER . . . . . . . . . . . . . . . . . . . . . . . .
7.10.1 Specialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.10.2 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.11 Constraints and Characteristics of Specialization and Generalization Hierarchies . .
7.11.1 Constraints on Specialization and Generalization . . . . . . . . . . . . . . .
7.11.2 Specialization and Generalization Hierarchies and Lattices . . . . . . . . . .
7.11.3 Utilizing Specialization and Generalization in Refining Conceptual Schemas .
7.12 Modeling of UNION Types Using Categories in EER . . . . . . . . . . . . . . . . .
7.13 A Sample UNIVERSITY EER Schema, Design Choices, and Formal Definitions . .
7.13.1 The UNIVERSITY Database Example . . . . . . . . . . . . . . . . . . . . .
7.13.2 Design Choices for Specialization/Generalization . . . . . . . . . . . . . . . .
7.14 Data Abstraction, Knowledge Representation, & Ontology Concepts . . . . . . . . .
7.14.1 Classification and Instantiation . . . . . . . . . . . . . . . . . . . . . . . . .
7.14.2 Identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.14.3 Specialization and Generalization . . . . . . . . . . . . . . . . . . . . . . . .
7.14.4 Aggregation and Association . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.14.5 Ontologies and the Semantic Web . . . . . . . . . . . . . . . . . . . . . . . .
49
49
49
49
50
50
50
50
50
51
51
51
51
51
51
51
52
52
52
52
52
52
52
53
53
53
53
54
54
54
54
55
55
55
55
55
55
8 Mapping a Conceptual Design into a Logical Design
8.1 Relational Database Design using ER-to-Relational Mapping . . . . . .
8.1.1 ER-to-Relational Mapping Algorithm . . . . . . . . . . . . . . .
8.1.2 Discussion and Summary of Mapping for ER Model Constructs
8.2 Mapping EER Model Constructs to Relations . . . . . . . . . . . . . .
8.2.1 Mapping of Specialization or Generalization . . . . . . . . . . .
8.2.2 Mapping of Shared Subclasses (Multiple Inheritance) . . . . . .
8.2.3 Mapping of Categories (Union Types) . . . . . . . . . . . . . . .
56
56
56
58
58
58
59
59
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
12 SQL Application Programming Using C and Java
12.1 Database Programming: Techniques and Issues . . . . . . . . . .
12.1.1 Approaches to Database Programming . . . . . . . . . . .
12.1.2 Impedance Mismatch . . . . . . . . . . . . . . . . . . . . .
12.1.3 Typical Sequence of Interaction in Database Programming
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
60
60
60
60
61
13 SQL Web Programming Using C PHP
13.1 A Simple PHP Example . . . . . . . . . . . . . . . . . . . . . . .
13.2 Overview of Basic Features of PHP . . . . . . . . . . . . . . . . .
13.2.1 PHP Variables, Data Types, and Programming Constructs
13.2.2 PHP Arrays . . . . . . . . . . . . . . . . . . . . . . . . . .
13.2.3 PHP Functions . . . . . . . . . . . . . . . . . . . . . . . .
13.2.4 PHP Server Variables and Forms . . . . . . . . . . . . . .
13.3 Overview of PHP Database Programming . . . . . . . . . . . . .
13.3.1 Connecting to a Database . . . . . . . . . . . . . . . . . .
13.3.2 Collecting Data from Forms and Inserting Records . . . .
13.3.3 Retrieval Queries from Database Tables . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
62
62
62
62
63
63
63
64
64
64
64
14 Database Design Theory: Introduction to Normalization Using
Multivalued Dependencies
14.1 Informal Design Guidelines for Relation Schemas . . . . . . . . . .
14.1.1 Imparting Clear Semantics to Attributes in Relations . . . .
14.1.2 Redundant Information in Tuples and Update Anomalies . .
14.1.3 NULL values in Tuples . . . . . . . . . . . . . . . . . . . . . .
14.1.4 Generation of Spurious Tuples . . . . . . . . . . . . . . . . .
14.1.5 Summary and Discussion of Design Guidelines . . . . . . . .
14.2 Functional Dependencies . . . . . . . . . . . . . . . . . . . . . . . .
14.2.1 Definition of Functional Dependency . . . . . . . . . . . . .
14.3 Normal Forms Based on Primary Keys . . . . . . . . . . . . . . . .
14.3.1 Normalization of Relations . . . . . . . . . . . . . . . . . . .
14.3.2 Practical Use of Normal Forms . . . . . . . . . . . . . . . .
14.3.3 Definitions of Keys and Attributes Participating in Keys . .
14.3.4 First Normal Form . . . . . . . . . . . . . . . . . . . . . . .
14.3.5 Second Normal Form . . . . . . . . . . . . . . . . . . . . . .
14.3.6 Third Normal Form . . . . . . . . . . . . . . . . . . . . . . .
14.4 General Definitions of Second & Third Normal Forms . . . . . . . .
14.5 Boyce-Codd Normal Form . . . . . . . . . . . . . . . . . . . . . . .
Functional and
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15 Database Design Theory: Normalization Algorithms
15.1 Further Topics in Functional Dependencies: Inference Rules, Equivalence, and Minimal Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.1.1 Inference Rules for Functional Dependencies . . . . . . . . . . . . . . . . . .
15.1.2 Equivalence of Sets of Functional Dependencies . . . . . . . . . . . . . . . .
15.1.3 Minimal Sets of Functional Dependencies . . . . . . . . . . . . . . . . . . . .
15.2 Properties of Relational Decompositions . . . . . . . . . . . . . . . . . . . . . . . .
15.2.1 Dependency Preservation Property of a Decomposition . . . . . . . . . . . .
15.2.2 Nonadditive (Lossless) Join Property of a Decomposition . . . . . . . . . . .
15.2.3 Testing Binary Decompositions for the Nonadditive Join Property . . . . . .
15.2.4 Successive Nonadditive Join Decompositions . . . . . . . . . . . . . . . . . .
15.3 Algorithms for Relational Database Schema Design . . . . . . . . . . . . . . . . . .
5
65
65
65
65
66
66
66
66
66
68
68
68
69
69
69
70
71
71
72
72
72
73
73
73
74
74
74
74
74
15.3.1 Dependency-Preserving Decomposition into 3NF Schemas . . . . . . . . . .
15.3.2 Nonadditive Join Decomposition into BCNF Schemas . . . . . . . . . . . . .
15.3.3 Dependency-Preserving and Nonadditive (Lossless) Join Decomposition into
3NF Schemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.4 About Nulls, Dangling Tuples, and Alternative Relational Designs . . . . . . . . . .
15.4.1 Problems with NULL Values and Dangling Tuples . . . . . . . . . . . . . . .
15.4.2 Discussion of Normalization Algorithms and Alternative Relational Designs .
74
75
75
75
75
75
16 Database File Organizations: Unordered, Ordered, and Hashed
16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16.1.1 Memory Hierarchies and Storage Devices . . . . . . . . . .
16.1.2 Storage of Databases . . . . . . . . . . . . . . . . . . . . .
16.2 Secondary Storage Devices . . . . . . . . . . . . . . . . . . . . . .
16.3 Buffering of Blocks . . . . . . . . . . . . . . . . . . . . . . . . . .
16.4 Placing File Records on Disk . . . . . . . . . . . . . . . . . . . . .
16.4.1 Records and Record Types . . . . . . . . . . . . . . . . . .
16.4.2 Files, Fixed-length Records, and Variable-Length Records
16.4.3 Record Blocking and Spanned versus Unspanned Records .
16.4.4 Allocating File Blocks on Disk . . . . . . . . . . . . . . . .
16.4.5 File Headers . . . . . . . . . . . . . . . . . . . . . . . . . .
16.5 Operations on Files . . . . . . . . . . . . . . . . . . . . . . . . . .
16.6 Files of Unordered Records (Heap Files) . . . . . . . . . . . . . .
16.7 Files of Ordered Records (Sorted Files) . . . . . . . . . . . . . . .
16.8 Hashing Techniques . . . . . . . . . . . . . . . . . . . . . . . . . .
16.8.1 Internal Hashing . . . . . . . . . . . . . . . . . . . . . . .
16.8.2 External Hashing for Disk Files . . . . . . . . . . . . . . .
16.8.3 Hashing Techniques That Allow Dynamic File Expansion .
16.9 Other Primary File Organizations . . . . . . . . . . . . . . . . . .
16.9.1 Files of Mixed Records . . . . . . . . . . . . . . . . . . . .
16.10Parallelizing Disk Access Using RAID Technology . . . . . . . . .
16.11New Storage Systems . . . . . . . . . . . . . . . . . . . . . . . . .
16.11.1 Storage Area Networks . . . . . . . . . . . . . . . . . . . .
16.11.2 Network-Attached Storage . . . . . . . . . . . . . . . . . .
16.11.3 iSCSI Storage Systems . . . . . . . . . . . . . . . . . . . .
Files of
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
Records
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
76
76
76
76
77
77
77
77
77
78
78
78
79
80
80
80
80
81
81
82
82
82
82
82
82
82
17 Database File Indexing Techniques, B-Trees, and B+-Trees
17.1 Types of Single-Level Ordered Indexes . . . . . . . . . . . . .
17.1.1 Primary Indexes . . . . . . . . . . . . . . . . . . . . .
17.1.2 Clustering Indexes . . . . . . . . . . . . . . . . . . . .
17.1.3 Secondary Indexes . . . . . . . . . . . . . . . . . . . .
17.2 Multilevel Indexes . . . . . . . . . . . . . . . . . . . . . . . . .
17.3 Dynamic Multilevel Indexes Using B-trees & B+-Trees . . . .
17.3.1 Search Trees and B-trees . . . . . . . . . . . . . . . . .
17.3.2 B+-trees . . . . . . . . . . . . . . . . . . . . . . . . . .
17.4 Indexes on Multiple Keys . . . . . . . . . . . . . . . . . . . . .
17.4.1 Ordered Index on Multiple Attributes . . . . . . . . . .
17.4.2 Partitioned Hashing . . . . . . . . . . . . . . . . . . .
17.4.3 Grid Files . . . . . . . . . . . . . . . . . . . . . . . . .
17.5 Other Types of Indexes . . . . . . . . . . . . . . . . . . . . . .
17.5.1 Hash Indexes . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
83
83
83
84
84
84
85
85
86
87
87
87
87
87
87
6
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17.5.2 Bitmap Indexes . . . . . . . . . . .
17.5.3 Function-Based Indexing . . . . . .
17.6 Some General Issues Concerning Indexing
17.6.1 Logical versus Physical Indexes . .
17.6.2 Discussion . . . . . . . . . . . . . .
17.6.3 Column-Based Storage of Relations
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18 Introduction to Query Processing and Query Optimization Techniques
18.1 Translating SQL Queries into Relational Algebra . . . . . . . . . . . . . . .
18.2 Algorithms for External Sorting . . . . . . . . . . . . . . . . . . . . . . . . .
18.3 Algorithms for SELECT and JOIN Operations . . . . . . . . . . . . . . . . .
18.3.1 Implementing the SELECT Operation . . . . . . . . . . . . . . . . .
18.3.2 Implementing the JOIN Operation . . . . . . . . . . . . . . . . . . .
18.4 Algorithms for PROJECT and Set Operations . . . . . . . . . . . . . . . . .
18.5 Implementing Aggregate Operations and OUTER JOINs . . . . . . . . . . .
18.5.1 Implementing Aggregate Operations . . . . . . . . . . . . . . . . . .
18.5.2 Implementing OUTER JOINs . . . . . . . . . . . . . . . . . . . . . .
18.6 Combining Operations Using Pipelining . . . . . . . . . . . . . . . . . . . . .
18.7 Using Heuristics in Query Optimization . . . . . . . . . . . . . . . . . . . . .
18.7.1 Notation for Query Trees and Query Graphs . . . . . . . . . . . . . .
18.7.2 Heuristic Optimization of Query Trees . . . . . . . . . . . . . . . . .
18.7.3 Converting Query Trees into Query Execution Plans . . . . . . . . .
18.8 Using Selectivity and Cost Estimates in Query Optimization . . . . . . . . .
18.8.1 Cost components for Query Execution . . . . . . . . . . . . . . . . .
18.8.2 Catalog Information Used in Cost Functions . . . . . . . . . . . . . .
18.8.3 Examples of Cost Functions for SELECT . . . . . . . . . . . . . . . .
18.8.4 Examples of Cost Functions for JOIN . . . . . . . . . . . . . . . . . .
18.8.5 Multiple Relation Queries and JOIN Ordening . . . . . . . . . . . . .
18.8.6 Example to Illustrate Cost-Based Query Optimization . . . . . . . .
18.9 Overview of Query Optimization in Oracle . . . . . . . . . . . . . . . . . . .
18.10Semantic Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . .
20 Foundations of Database Transaction Processing
20.1 Introduction to Transaction Processing . . . . . . . . . . . . . . .
20.1.1 Single-User versus Multiuser Systems . . . . . . . . . . . .
20.1.2 Transactions, Database Items, Read and Write Operations,
20.1.3 Why Concurrency Control Is Needed . . . . . . . . . . . .
20.1.4 Why Recovery Is Needed . . . . . . . . . . . . . . . . . . .
20.2 Transaction and System concepts . . . . . . . . . . . . . . . . . .
20.2.1 Transaction States and Additional Operations . . . . . . .
20.2.2 The System Log . . . . . . . . . . . . . . . . . . . . . . . .
20.2.3 Commit Point of a Transaction . . . . . . . . . . . . . . .
20.3 Desirable Properties of Transactions . . . . . . . . . . . . . . . . .
20.4 Characterizing Schedules Based on Recoverability . . . . . . . . .
20.4.1 Schedules (Histories) of Transactions . . . . . . . . . . . .
20.4.2 Characterizing Schedules Based on Recoverability . . . . .
20.5 Characterizing Schedules Based on Serializability . . . . . . . . .
20.5.1 Serial, Nonserial, and Conflict-Serializable Schedules . . . .
20.5.2 Testing for Conflict Serializability of a Schedule . . . . . .
20.5.3 How Serializability Is Used for Concurrency Control . . . .
7
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
88
88
88
88
88
88
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
89
89
89
90
90
91
92
93
93
93
93
93
94
94
95
96
96
96
96
97
97
98
98
98
99
. . . . . . . . . . 99
. . . . . . . . . . 99
and DBMS Buffers 99
. . . . . . . . . . 100
. . . . . . . . . . 100
. . . . . . . . . . 101
. . . . . . . . . . 101
. . . . . . . . . . 101
. . . . . . . . . . 101
. . . . . . . . . . 102
. . . . . . . . . . 102
. . . . . . . . . . 102
. . . . . . . . . . 102
. . . . . . . . . . 103
. . . . . . . . . . 103
. . . . . . . . . . 103
. . . . . . . . . . 103
20.5.4 View Equivalence and View Serializability . . . . . . . . . . . . . . . . . . . 104
20.5.5 Other Types of Equivalence of Schedules . . . . . . . . . . . . . . . . . . . . 104
20.6 Transaction Support in SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
21 Introduction to Protocols for Concurrency Control in Databases
21.1 Two-Phase Locking Techniques for Concurrency Control . . . . . . .
21.1.1 Types of Locks and System Lock Tables . . . . . . . . . . . .
21.1.2 Guaranteeing Serializability by Two-Phase Locking . . . . . .
21.1.3 Dealing with Deadlock and Starvation . . . . . . . . . . . . .
21.2 Concurrency Control Based on Timestamp Ordering . . . . . . . . . .
21.2.1 Timestamps . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21.2.2 The Timestamp Ordering Algorithm . . . . . . . . . . . . . .
21.3 Multiversion Concurrency Control Techniques . . . . . . . . . . . . .
21.3.1 Multiversion Technique Based on Timestamp Ordering . . . .
21.3.2 Multiversion Two-Phase Locking Using Certify Locks . . . . .
21.4 Validation (Optimistic) Concurrency Control Techniques . . . . . . .
21.5 Granularity of Data Items and Multiple Granularity Locking . . . . .
21.5.1 Granularity Level Considerations for Locking . . . . . . . . . .
21.5.2 Multiple Granularity Level Locking . . . . . . . . . . . . . . .
21.6 Using Locks for Concurrency Control in Indexes . . . . . . . . . . . .
21.7 Other Concurrency Control Issues . . . . . . . . . . . . . . . . . . . .
21.7.1 Insertion, Deletion, and Phantom Records . . . . . . . . . . .
21.7.2 Interactive Transactions . . . . . . . . . . . . . . . . . . . . .
21.7.3 Latches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
105
105
105
107
108
110
110
110
112
112
112
113
114
114
115
115
116
116
117
117
22 Introduction to Database Recovery Protocols
22.1 Recovery Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22.1.1 Recovery Outline and Categorization of Recovery Algorithms .
22.1.2 Caching (Buffering) of Disk Blocks . . . . . . . . . . . . . . .
22.1.3 Write-Ahead Logging, Steal/No-Steal, and Force/No-Foce . .
22.1.4 Checkpoints in the System Log and Fuzzy Checkpoints . . . .
22.1.5 Transaction Rollback and Cascading Roll back . . . . . . . . .
22.1.6 Transactions Actions That Do Not Affect the Database . . . .
22.2 NO-UNDO/REDO Recovery Base on Deffered Update . . . . . . . .
22.3 Recovery Rechniques Based on Immediate Update . . . . . . . . . . .
22.4 Shadow Paging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22.4.1 Before Transaction . . . . . . . . . . . . . . . . . . . . . . . .
22.4.2 During Transaction . . . . . . . . . . . . . . . . . . . . . . . .
22.4.3 Recovery Process . . . . . . . . . . . . . . . . . . . . . . . . .
22.4.4 Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . . .
22.5 The Aries Recovery Algorithm . . . . . . . . . . . . . . . . . . . . . .
22.5.1 Analysis Phase . . . . . . . . . . . . . . . . . . . . . . . . . .
22.5.2 REDO Phase . . . . . . . . . . . . . . . . . . . . . . . . . . .
22.5.3 UNDO Phase . . . . . . . . . . . . . . . . . . . . . . . . . . .
22.5.4 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22.5.5 Log Sequence Number (LSN) . . . . . . . . . . . . . . . . . .
22.5.6 Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22.5.7 Checkpoints . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22.5.8 Recovery from crash . . . . . . . . . . . . . . . . . . . . . . .
22.6 Recovery in Multidatabse Systems . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
118
118
118
119
120
122
122
123
123
124
125
125
126
126
126
126
127
127
127
127
127
128
128
128
128
8
22.7 Database Backup and Recovery from Catastrophic Failures . . . . . . . . . . . . . . 129
22.7.1 Handling more Catastrophic Failures . . . . . . . . . . . . . . . . . . . . . . 129
22.7.2 Increase frequency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
9
Hoofdstuk 1
Introduction to Databases
1.1
Introduction
Een database heeft volgende eigenschappen:
• Het is een representatie van een aspect in de echte wereld, een miniwereld, ook wel universe
of discourse (UoD) genaamd.
• Een database is een verzameling van gerelateerde informatie/data.
• Een database wordt ontworpen, gebouwd en ingevuld voor een specifiek doel.
• Aanpassingen moeten zo snel mogelijk weergegeven worden in de database.
Een database management system (DBMS) is een set van programma’s die de gebruiker toelaat
een database te cre¨eren en te onderhouden.
1.2
An Example
Het manipuleren van een database omvat querying en updating. Een query moet gespecifieerd zijn
in een bepaalde query-taal, behorende tot het DBMS, alvorens hij kan worden uitgevoerd.
1. Het ontwikkelen van een applicatie voor een bestaande database, of het ontwikkelen van een
compleet nieuwe database start met een fase genaamd requirements specification and
analysis. De eisen/voorwaarden van de database worden hier in detail vastgelegd.
2. De eisen/voorwaarden worden omgevormd tot een conceptual design dat weergegeven en
bewerkt kan worden op een computer.
3. Het conceptual design wordt omgezet naar een logical design, dat ge¨ımplementeerd kan
worden in een commercieel DBMS.
4. Het logical design wordt omgezet in een physical design, waar men de verdere specificaties
voor opslag en toegang tot de database zal vastleggen. Hierna kan men beginnen de database
te bevolken.
10
1.3
Characteristics of the Database Approach
Een database bestaat uit een enkele opslagplaats waar gegevens worden bijgehouden die ´e´en keer
gedefinieerd worden en nadien toegankelijk zijn voor alle gebruikers.
1.3.1
Self-Describing Nature of a Database System
Een basiskenmerk van een databasesysteem is dat het systeem niet enkel de database zelf bevat
maar ook een complete definitie of beschrijving van de databasestructuur en zijn beperkingen.
Deze definitie wordt bijgehouden in de DBMS catalogus. De informatie in deze catalogus is de
zogenaamde meta-data, en beschrijft de structuur van de primaire database.
1.3.2
Insulation between Programs and Data, and Data Abstraction
In traditionele bestandsverwerking is de structuur van de data files ingebouwd in het programma
dat gebruik maakt van het bestand. Als de structuur van een bestand gewijzigd wordt, zullen dus
ook alle programma’s die gebruik maken van het bestand, aangepast moeten worden. Een DBMS
daarentegen bewaart de structuur van de bestanden in de catalogus, apart van de programma’s die
het gebruiken. We noemen dit program-data independence.
Een operation (functie of methode) bestaat uit 2 delen. De interface (signature) van een operatie
bevat de naam van de operatie en de data types van zijn argumenten (parameters). De implementatie
van de operatie is apart gedefinieerd en kan aangepast worden zonder dat de interface gewijzigd moet
worden. Gebruikersprogramma’s kunnen met de data werken door middel van operatienamen en
-parameters, onafhankelijk van hoe de operaties ge¨ımplementeerd zijn. We noemen dit programoperation independence.
De karakteristiek die program-data independence en program-operation independence toelaat,
wordt de data abstraction genoemd. Een data model is een soort van data abstraction die voor
een conceptual representation van de data zorgt.
1.3.3
Support of Multiple Views of the Data
Een database heeft vaak meerdere gebruikers die eventueel een ander zicht (view ) willen op de
database. Een view kan een subset van de database zijn maar het kan ook zelf virtuele data
bevatten die afgeleid is van de data in de database maar er niet opgeslagen is.
1.3.4
Sharing of Data and Multiuser Transaction Processing
Een multiuser DBMS moet toelaten dat meerdere gebruikers tegelijkertijd toegang hebben tot
de database. Hiervoor moet de DBMS over concurrency control software beschikken om te
verzekeren dat het updaten van data door meerdere gebruikers correct verloopt zodat ook het
resultaat hiervan correct is.
Een transactie is een uitvoerend programma of proces dat ´e´en of meerdere database accesses
omvat. De isolation-eigenschap verzekert dat elke transactie uitgevoerd wordt, afgezonderd van
andere transacties. De atomicity-eigenschap verzekert dat alle transacties ofwel volledig uitgevoerd
worden, ofwel niet uitgevoerd worden.
11
1.4
Actors on the Scene
Actors on the scene zijn de personen die dagelijks een grote database gebruiken.
1.4.1
Database Administrators
Er is nood aan een chief administrator, we noemen deze de database administrator (DBA). Hij
is verantwoordelijk voor autorisatie, co¨ordinatie, monitoring en de software en hardware resources.
Hij is ook de persoon die verantwoordelijk gesteld kan worden voor problemen zoals veiligheidslekken en een slechte responstijd van het systeem.
1.4.2
Database Designers
Database designers zijn de personen die verantwoordelijk zijn voor het identificeren van de data
die opgeslagen moet worden op de database en voor het kiezen van de juiste datastructuren om
deze op te slagen data voor te stellen in de database.
1.4.3
End Users
Eindgebruikers zijn de personen wiens job eruit bestaat een database te bevragen, up te daten
en rapporten te maken. We kunnen ze onderverdelen in verschillende categorie¨en:
• Casual end users hebben de database occasioneel nodig en hebben mogelijk elke keer andere
gegevens nodig.
• Naive of parametric end users bevragen en updaten de database constant.
• Sophisticated end users (zoals ingenieurs of wetenschappers) kennen de eigenschappen en mogelijkheden van de database zeer goed zodat ze hun eigen applicaties kunnen implementeren.
• Standalone users hebben meestal een persoonlijke database.
1.4.4
System Analysts and Application Programmers (Software Engineers)
System analysts bepalen de eisen van de eindgebruiker en ontwerpen de specificaties voor alleenstaande transacties die voldoen aan deze eisen. Application programmers implementeren deze
specificaties als programma’s die ze testen, debuggen en documenteren.
1.5
Workers behind the Scene
Dit stuk gaat over de mensen die de DBMS software en system environment ontwerpen, ontwikkelen
en de operaties ervan uitschrijven. Ze zijn meestal niet ge¨ınteresseerd in de inhoud van de database.
• DBMS system designers en implementers ontwerpen en implementeren de DBMS modules en
interfaces als een softwarepakket.
• Tool developers ontwerpen en implementeren tools. Tools zijn optionele pakketten die vaak
apart aangekocht kunnen worden.
• Operators en maintenance personnel is het system administration personnel. Ze zijn verantwoordelijk voor het runnen en het onderhoud van de hardware en software environment.
12
1.6
1.6.1
Advantages of Using the DBMS Approach
Controlling Redundancy
De redundantie is het meermaals opslaan van dezelfde data, dit leidt tot verschillende problemen.
• Een simpele update moet meerdere malen uitgevoerd worden, dit is duplication of effort.
• Opslagruimte wordt verspilt.
• Bestanden die dezelfde data voorstellen kunnen inconsistent worden omdat een update niet
wordt doorgevoerd op alle bestanden.
We moeten een database hebben die elk logical data item (bv. naam en geboortedatum) opslaat op
´e´en enkele plaats in de database, dit heet data normalization.
Soms is er echter nood aan gecontroleerde redundantie. Dit komt voor indien we alle data die
vaak samen opgevraagd wordt, in 1 bestand plaatsen. Hierdoor moet er bij een query slechts 1
bestand doorzocht worden i.p.v. meerdere. Dit heet denormalization.
1.6.2
Restricting Unauthorized Access
Als meerdere gebruikers een grote database delen, is het logisch dat niet iedereen toegang heeft tot
alle data. Een DBMS moet een security and authorization subsystem bevatten, waarmee de
DBA accounts kan aanmaken en restricties kan opleggen.
1.6.3
Providing Persistent Storage for Program Objects
Databases kunnen gebruikt worden om persistente opslag voor programma-objecten en datastructuren aan te bieden. Dit is ´e´en van de redenen voor object-oriented database systems. Een
complex object in C++ kan permanent opgeslagen worden in een object-geori¨enteerd DBMS. Zo
een object noemen we persistent, omdat het de be¨eindiging van het programma overleeft en later
direct kan teruggevonden worden.
1.6.4
Providing Storage Structures and Search Techniques for Efficient
Query Processing
Databasesystemen moeten de mogelijkheid hebben tot het effici¨ent uitvoeren van query’s en updates. Omdat een database vaak is opgeslagen op een disk, moet de DBMS speciale datastructuren en
technieken voorzien om de seektime te versnellen. Een oplossing hiervoor is werken met indexering.
Een DBMS biedt vaak buffering of caching modules aan, die bijgehouden worden in het hoofdgeheugen. De query processing and optimization module is verantwoordelijk voor het kiezen
van een effici¨ent query-uitvoeringsplan voor elke query, gebaseerd op de huidige opslagstructuur.
1.6.5
Providing Backup and Recovery
Een DBMS moet de mogelijkheid bezitten om te herstellen van hardware- of softwarefouten. Het
backup and recovery subsystem van de DBMS is verantwoordelijk voor het herstel. Het moet
kunnen herstellen, hervatten of een backup maken.
13
1.6.6
Providing Multiple User Interfaces
Dit omvat query-talen voor casual users, programming language interfaces voor application programmers, formulieren en commando’s voor parametric users en menu-gestuurde interfaces en natural
language interfaces voor standalone users. Vaak in combinatie met een GUI.
1.6.7
Representing Complex Relationships among Data
Een DBMS moet de mogelijkheid bieden om complexe relaties tussen data voor te stellen, evenals de
mogelijkheid om nieuwe relaties te defini¨eren en gerelateerde data snel en effici¨ent terug te vinden.
1.6.8
Enforcing Integrity Constraints
De meeste database applications hebben bepaalde integrity constraints die moeten gelden voor
de data. Een DBMS moet de mogelijkheid bieden om constraints te defini¨eren en ze te handhaven.
1.6.9
Permitting Inferencing and Actions Using Rules
Sommige databasesystemen hebben de mogelijkheid om informatie af te leiden uit reeds bestaande
data. Zulke systemen noemen we deductive database systems. In moderne databases bestaat
de mogelijkheid om triggers te associ¨eren met tabellen. Een trigger is een soort regel die toegepast
wordt bij een update op een tabel, wat resulteert in het uitvoeren van extra operaties zoals het
sturen van een boodschap. Nog sterker zijn active database systems, deze leveren actieve regels
die automatisch acties uitvoeren wanneer bepaalde gebeurtenissen of condities voorkomen.
1.6.10
Additional Implications of Using the Database Approach
• Potential for Enforcing Standards: de DBA wordt toegelaten om een bepaalde standaard te
defini¨eren voor de users.
• Reduced Application Development Time: eens een database is opgezet en runt, is er minder tijd
nodig om een nieuwe applicatie te ontwikkelen, gebruikmakend van de DBMS mogelijkheden.
• Flexibility: moderne DBMS’en laten verschillende soorten van evolutionaire veranderingen
toe in de structuur van de database zonder invloed op de opgeslagen data of applicaties.
• Availability of Up-to-Date information: vanaf het moment dat een gebruiker bepaalde data
heeft ge¨
updatet, moeten deze wijzigingen zichtbaar zijn voor andere gebruikers.
• Economies of Scale: systemen kunnen gedeeld worden om overlappingen te voorkomen op
verschillende niveaus.
1.8
When Not to Use a DBMS
Er zijn bepaalde situaties waarbij het gebruik van een DBMS een onnodige overhead kan veroorzaken, wat niet zou voorkomen bij het traditionele file processing. De overhead van een DBMS kan
volgende oorzaken hebben:
• Te hoge initi¨ele kosten voor hardware, software en training
• De algemeenheid van een DBMS
• Overhead voor het leveren van security, concurrency en recovery
14
Hoofdstuk 2
Overview of Database Languages and
Architectures
DBMS packages zijn gegroeid van ´e´en ge¨ıntegreerd systeem naar modulaire systemen. Deze bestaan
uit verschillende delen. Standaard wordt er gewerkt met twee modules: een client module die de
gebruikersinteractie moet verzorgen en een server module die zaken als dataopslag, toegang, en
het doorzoeken van de database op zich neemt.
2.1
Data Models, Schemas, and Instances
Een belangrijk kenmerk van databases is dat ze een soort van data abstraction voorzien. Hiermee bedoelt men dat zaken als de schijfopslag van de data worden genegeerd, terwijl enkel het
belangrijkste om de data te kunnen bestuderen en interpreteren wordt getoond.
Er worden ook meer en meer hoogniveau operaties ge¨ımplementeerd zodat manipulatie of interpretatie van de opgeslagen data zo eenvoudig mogelijk wordt. Dit wordt ook wel het dynamische
aspect van de database genoemd.
2.1.1
Categories of Data Models
Er zijn een drietal interessante, veel voorkomende datamodellen:
• Hoog-niveau of conceptuele datamodellen
Deze datamodellen gebruiken concepten als entiteiten, attributen en relaties:
– een entiteit stelt een object uit de echte wereld voor
– een attribuut stelt een eigenschap van zo een entiteit voor
– een relatie stelt een associatie voor tussen twee of meer entiteiten
• Representatieve of implementatie-datamodellen
Deze datamodellen worden in commerci¨ele databasesystemen het vaakst gebruikt. Ze maken
gebruik van relaties, maar ook van record structures.
• Laag-niveau of fysieke datamodellen
Deze datamodellen beschrijven hoe data in bestanden wordt opgeslagen in het geheugen door
informatie als het recordformaat, recordsortering en toegangspaden te beschrijven.
15
2.1.2
Schemas, Instances and Database State
Er moet bij elk datamodel een onderscheid gemaakt worden tussen de beschrijving van een database
en de database zelf.
De beschrijving van een database gebeurt in een database schema, ook wel een schema-diagram
genoemd. Dit schema wordt ontwikkeld v´o´or het maken van de database en wordt niet dikwijls
gewijzigd. Dit diagram geeft dus eigenlijk de structuur (de tabellen en hun kolomhoofden) weer
van een database.
De eigenlijke data van een database verandert regelmatig d.m.v. manipulaties. Elke momentopname in de tijd van de data in een database heet de database state (databasetoestand of
instantie).
Je kan het ook als volgt beschrijven: het schema is de intensie van de database, terwijl een
databasetoestand een extensie van dit schema is.
2.2
Three-Schema Architecture and Data Independence
De 3-schema architectuur probeert de volgende drie kenmerken te bereiken en visualiseren:
• Een catalog gebruiken om het schema in op te slaan zodat de database zelfbeschrijvend wordt.
• Isolatie tussen programma’s en opgeslagen data.
• Ondersteunen van meerdere user views (manieren om de data te kunnen interpreteren).
2.2.1
The Three-Schema Architecture
In deze architectuur kunnen schema’s op drie niveaus gedefini¨eerd worden:
• Het interne niveau heeft een intern schema dat de fysische opslagstructuur en de toegangspaden beschrijft.
• Het conceptuele niveau heeft een conceptueel schema (implementatiemodel) dat de structuur van de database weergeeft voor gebruikers.
• Het externe niveau of view niveau heeft een aantal user views (hoe gebruikers data zien).
Deze niveaus moeten uiteraard kunnen samenwerken. Bij het opvragen van data moet deze data
aangepast worden om binnen de view van een zekere gebruik te passen. Deze transformaties tussen
de verschillende niveaus heten mappings.
2.2.2
Data Independence
Data independence binnen de 3-schema architectuur houdt in dat je het schema van ´e´en niveau
kan veranderen zonder dat je het schema van het niveau direct daarboven moet aanpassen. Er zijn
twee types:
• Logical data independence houdt in dat je het conceptueel schema kan aanpassen zonder
dat je daarvoor de externe schema’s of applicaties moet voor aanpassen. Je moet dus de
structuur kunnen aanpassen en constraints kunnen defini¨eren zonder dat je daarvoor een
aanpassing moet doen aan die externe schema’s of applicaties.
• Physical data independence betekent dat je het intern schema kan aanpassen, zonder dat
je aan het conceptueel schema dat er boven draait moet moet raken.
De laatste soort onafhankelijkheid komt in de meeste databases wel voor, maar de eerste soort is
iets moeilijker te verkrijgen.
16
2.3
2.3.1
Database Languages and Interfaces
DBMS Languages
Er zijn 4 theoretische DBMS-talen die belangrijk zijn voor de goede werking van de database:
• De data definition language (DDL) wordt gebruikt om de conceptuele en interne schema’s
te defini¨eren.
• De storage definition language (SDL) specificieert het interne schema.
• De view definition language (VDL) bepaalt de user views en de mappings die ze hebben
naar het conceptueel schema.
• De data manipulation language (DML) staat in voor het manipuleren van data: opvragen,
toevoegen, verwijderen of aanpassen.
Deze zijn theoretisch omdat men in de praktijk niet werkt met aparte talen: alles wordt in ´e´en
ge¨ıntegreerde taal gedefinieerd.
Er zijn 2 soorten DMLs: high-level en low-level. Waar een high-level DML op zichzelf kan
steunen om query’s en dergelijke te processen (het wordt dan ook vaak query-taal genoemd), moet
een low-level DML ingebouwd worden in een algemene programeertaal om gebruik te kunnen maken
van hun functies zoals loops. In dit laatste geval is de low-level taal een data sublanguage van
de host language, de programmeertaal waarin de low-level taal geschreven is.
2.3.2
DBMS Interfaces
Volgende interfaces kunnen in de database aanwezig zijn:
• Menu-Based Interfaces for Web Clients or Browsing. Deze interfaces worden gebruikt
om de inhoud van de database te kunnen opvragen en bekijken met behulp van drop-down
menu’s.
• Forms-Based Interfaces. Deze interfaces maken gebruik van invulvelden om data op te
vragen of om nieuwe data toe te voegen.
• Graphical User Interfaces. Dit type interfaces maakt gebruik van de twee voorgaande
methodes om een nette interface te geven aan de gebruikers.
• Natural Language Interfaces. Hier wordt geprobeerd ingegeven woorden uit een spreektaal
te vertalen zodat de zin kan ge¨ınterpreteerd worden. Dit heet dan keyword-based querying.
• Speech Input and Output. Hierbij kan men via gesproken taal een query ingeven, het
resultaat wordt door de computer ook in gesproken taal gegeven.
• Interfaces for Parametric Users. Interfaces voor gebruikers die een beperkte set commando’s bij herhaling nodig hebben. Door hier een specifieke set van commando’s in te
voeren moeten er minder toetsen worden ingedrukt.
• Interfaces for the DBA. Uiteraard moeten ook de database administrators in staat zijn de
database te kunnen manipuleren. Zij hebben daar deze specifieke interfaces voor.
17
2.4
2.4.1
The Database System Environment
DBMS Component Modules
Elke database en zijn catalogus is opgeslagen op een schijf. Toegang tot deze schijf wordt geregeld
door het besturingssysteem. Daar zit uiteraard ook buffer management ingebakken om disk
read/write operations te schedulen. Bovendien is er nog een stored data manager die de toegang
tot informatie over het systeem beheert.
• Het user-gedeelte van de database bestaat uit de toegang voor de DBA staff, casual users,
application programmers en parametric users.
• Het query and transactie-gedeelte staat in voor het uitvoeren van queries op de data
en het teruggeven van het resultaat. Dit gebeurt in de runtime database processor,
gebruikmakend van de system catalog en de stored data manager. Voordat de query
wordt uitgevoerd is deze reeds gecompiled en geoptimaliseerd door de desbetreffende modules
in het user -gedeelte.
Zie eventueel figuur 2.3 op pagina 39.
2.4.2
Database System Utilities
Elke database heeft een aantal system utilities die helpen bij het beheer van de database:
• Loading. Deze utility staat in voor het inladen van bestaande data files in een bepaald
formaat (bv. tekstbestanden of sequenti¨ele bestanden) in de database.
• Backup. Deze tool maakt een gehele backup van de database om de data te kunnen herstellen bij een disk failure. Soms werkt deze tool met incrementele backup waarbij enkel de
veranderingen sinds de laatste toestand worden opgeslagen.
• Database storage reorganisation. Een tool om een set data te reorganiseren in files of in
een ander pad in de database.
• Performance monitoring. Deze utility houdt het gebruik van de database bij en maakt er
statistieken van die door de administrators kunnen ge¨ınterpreteerd worden.
2.4.3
Tools, Application Environments, and Communications Facilities
Er zijn nog een aantal extra tools die handig kunnen zijn, bijvoorbeeld een information repository. Hierin worden zaken als ontwerpsbeslissingen bijgehouden.
Er is vaak ook communication software nodig om vanop afstand aan de database te kunnen.
2.5
2.5.1
Centralized & Client/Server Architectures for DBMSs
Centralized DBMSs Architecture
De eerste databases werden gebouwd als mainframes met daarop aangesloten terminals, deze terminals hadden geen eigen rekenkracht. Omdat hardware goedkoper werd, begon men de terminals
te vervangen door PC’s en werkstations waarbij het hele DBMS nog steeds centraal draaide.
18
2.5.2
Basic Client/Server Architectures
Dit type architectuur werd ontwikkeld om te kunnen werken in omgevingen met een groot aantal
PC’s, werkstations, printers en allerhande servers. Het idee is om verscheidene servers specifieke
taken te geven in plaats van alles zomaar te centraliseren.
Server-side wordt alles verdeeld over verschillende types servers (printservers, fileservers, webservers, . . . ). Daarnaast is er ook de client-side, waarbij elke machine zijn gebruiker voorziet van de
nodige interfaces om met deze servers te kunnen werken. Al deze servers en machines zijn onderling
verbonden via een communicatienetwerk.
2.5.3
Two-Tier Client/Server Architectures for DBMSs
Een 2-tier client/server architecture is rechtstreeks gegroeid uit de gecentraliseerde architectuur. Interfaces en applicatieprogramma’s werden verhuisd van server- naar client-side. De server
heet in zo’n 2-tier systeem vaak de query server of transaction server omdat dit de functies
van de server zijn. Client-side is er een programma dat via een API met de database kan verbinden
en er query’s kan op uitvoeren binnen de rechten die toegekend zijn aan de client.
De softwarecomponenten zijn dus over 2 soorten systemen verdeeld zijn: clients en servers.
2.5.4
Three-Tier and n-Tier Architectures for Web Applications
Veel webapplicaties werken tegenwoordig met een 3-tier architecture. Er wordt een extra laag
ingebouwd tussen client en server: een application server of web server. Deze server draait
de applicatieprogramma’s en slaat procedures en constraints op waarmee men rekening mee moet
houden bij het opvragen van data van de database server.
Deze middle-tier geldt ook als extra veiligheidsmaatregel: je kan een client verifi¨eren voor je zijn
query doorstuurt naar de databaseserver.
Op de client-layer zijn dan de gebruikers- en webinterfaces aanwezig, terwijl op de server alle
data management services aanwezig zijn.
De verschillende layers kunnen nog verder uit mekaar gehaald worden tot n-tier architectures,
bijvoorbeeld een encryptie-/decryptieserver om communicatie van en naar de servers te beveiligen.
2.6
Classification of Database Management Systems
Om DBMSs te classificeren zijn er een zestal criteria om te beschouwen:
• Het gebruikte datamodel. In veel DBMSs is dat het relationele datamodel.
• Aantal ondersteunde gebruikers. Een single-user system ondersteunt maar ´e´en gebruiker
tegelijk, een multiuser system meerdere.
• Aantal plaatsen waarover de database verdeeld is. Een DBMS is gecentraliseerd als de
data op ´e´en plaats staat en gedistribueerd als de data verspreid is over meerdere plaatsen.
• Kost. Er zijn gratis systemen zoals MySQL en PostgreSQL maar er zijn ook betalende
systemen. Veel geld gaat meestal uit naar het onderhoud van de systemen en ondersteuning
als er problemen zijn. De prioriteiten liggen hier voor particulieren anders dan voor bedrijven.
• Het gekozen type access path. Men gebruikt meestal ge¨ınverteerde bestandstructuren.
• Het doel. Er zijn databases voor algemene doeleinden en voor speciale doeleinden.
19
Hoofdstuk 3
The Basic (Flat) Relational Model
3.1
Relational Model Concepts
Een relationele database bestaat uit verschillende relaties.
Mathematisch Een tabel uit simpele lineaire rijen, ook wel eens naar een flat file genoemd voor
de simpele, lineaire structuur. Rijen hebben elk hun eigen kolom met informatie erin.
Formeel Formeel gezien spreken we over tupels i.p.v. rijen en over attributen i.p.v. kolommen,
elk met een domein. De tabel wordt een relation genoemd.
3.1.1
Domains, Attributes, Tuples, and Relations
Domein Een domein D is een verzameling van onafscheidelijke (of atomische) waardes, bijvoorbeeld een “Naam” bestaande uit letters. Deze waardes zijn volgens de database niet meer te
scheiden. Bij een domein hoort altijd een logische definitie.
Elk domein heeft ook een data type of formaat. Een naam zal uit het datatype string
bestaan, dat zelf uit letters bestaat. Elke tupel zal zich aan dit domein moeten houden. De
kardinaliteit |D| van een domein is het aantal verschillende values dat het kan hebben.
Attributen Een rol (eigenschap) gespeeld door een domein D. Het domein van een attribuut Ai
wordt genoteerd als dom(Ai ).
Formeel: t = {(A1 , w1 ), . . . , (An , wn )} met elke wi ∈ dom(Ai ) of wi = NULL.
Relationeel schema Een relationeel schema R is een n-tupel over een lijst attributen. Een tupel
of rij is een object of verband tussen de attributen. De graad of ariteit van R stelt het aantal
attributen van R voor.
De relatie van een relationeel schema (relational intension) bestaat uit tupels met elk dezelfde attributen (relational extension).
r(R) ⊆ (dom(A1 ) × · · · × dom(An )) is een instantie (instance) van een relatie.
3.1.2
Characteristics of Relations
Ordenen van tupels Abstract gezien hebben tupels geen volgorde. Fysiek gezien moet er wel een
volgorde bestaan (voor het opslaan op de harde schijf).
Ordenen van waardes in een tupel De ordening van attributen (waardes) in een tupel heeft
abstract gezien geen belang, toch wordt meestal een ordening meegegeven.
Een tupel kan ook gezien worden als een set van (<attribuut>,<waarde>) paren waar elk
paar de waarde geeft van een mapping van een attribuut Ai tot een waarde wi van dom(Ai ).
20
Waardes van tupels Elke waarde is steeds atomair en van de eerste normaalvorm (cfr. hoofdstuk
14). Multivalued attributen moeten voorgesteld worden met aparte relaties. Samengestelde
attributen worden voorgesteld door hun afzonderlijke attributen.
Een NULL-waarde betekent dat het attribuut niet van toepassing is of dat de waarde onbekend
is.
Interpretatie van een relatie Relaties kunnen gezien worden als predicaten. De waardes van
elke tupel worden gezien als de waardes die aan de predicaat voldoen.
Een relatie kan ook gezien worden als een declaratie van een type of assertie. Iedere waarde
in die tupel kan dan gezien worden als een feit.
3.1.3
Relational Model Notation
Een relationeel schema R van graad n wordt genoteerd als R(A1 , A2 , . . . , An ). Voorbeelden van
relatienamen zijn Q, R of S, instanties van relaties worden geschreven als q, r of s. Tupels worden
genoteerd als t, u of v.
Een n-tupel t in een relatie r(R) wordt genoteerd als t = < w1 , w2 , . . . , wn >.
Een attribuut A van een relatie R wordt soms genoteerd als R.A. De waarden van een attribuut
Ai worden genoteerd als t.Ai of t[Ai ].
3.2
Relational Model Constraints and Relational Database
Schemas
Er bestaan drie soorten constraints in een database.
• Implicit constraints: de constraints die bij het data model horen.
• Explicit constraints: de constraints die rechtstreeks uitgedrukt worden in de schema’s van
het datamodel, gespecifieerd in de data definition language (DDL).
• Application-based constraints: de constraints die niet rechtstreeks in de schema’s kunnen
worden uitgedrukt. Ook wel business constraints genoemd.
3.2.1
Domain Constraints
De domeinrestricties beperken de mogelijke waarden van attributen: booleans, integers, doubles,
strings. Het domein van een attribuut is altijd enkelvoudig.
Bijvoorbeeld: een attribuut “leeftijd” is een geheel positief getal tussen 18 en 65.
3.2.2
Key Constraints and Constraints on NULL values
Een set van tupels moet uniek zijn, twee tupels mogen dus niet exact dezelfde waarden hebben.
Het gebruik van een (unieke) key lost dit probleem op.
Als U alle attributen van R voorstelt, dus U = {A1 , . . . , An }, dan defini¨eren we de supersleutel
K ⊆ U : de verzameling van attributen die een tupel in R ondubbelzinnig maken (in elke extensie).
Een kandidaatsleutel K is een supersleutel zonder de overtollige attributen. Deze is ook uniek,
er bestaat geen supersleutel K 0 ⊂ K. Een sleutel kan samengesteld of enkelvoudig zijn.
Uit de kandidaatsleutels wordt de primaire sleutel gekozen, deze wordt onderlijnd in het
schema. De andere kandidaatsleutels zijn de alternatieve sleutels, deze worden niet onderlijnd.
Er worden ook constraints vastgelegd die bepalen of een attribuut de waarde NULL mag bevatten.
21
3.2.3
Relational Databases and Relational Database Schemas
Een relationeel databaseschema S is een set van relatieschema’s S = {R1 , . . . , Rm } en een set
van integrity constraints IC. Een relationele databasetoestand DB van S is een set van
relatietoestanden DB = {r1 , . . . , rm } waarbij elke ri de integriteitconstraints in IC volgt.
De statica-regels slaan op 1 toestand van DB en gelden in elke extensie. De dynamica-regels
slaan op toestandsovergangen en gelden voor elke overgang tussen extensies.
3.2.4
Integrity, Referential Integrity and Foreign Keys
Volgens de entitity integrity constraint kan een primaire sleutel nooit NULL zijn. Deze constraint
bepaalt ook dat een tupel niet meer dan 1 keer mag voorkomen in een extensie.
De referential integrity constraint bepaalt dat een verwijzing naar een andere tupel geldig
moet zijn. Als een tupel naar een andere tupel verwijst, moet die andere ook tupel bestaan.
Een verzameling attributen FK van R1 is een foreign key (verwijssleutel ) dat refereert naar R2
als en slechts als:
• De attributen van FK hebben dezelfde domeinen als de de primaire sleutelattributen PK van
relatie R2 .
• Elke waarde van FK in R1 komt voor als de waarde van een tupel in R2 of is NULL.
∀t1 ∈ R1 : t1 [FK ] = NULL ∪ ∃t2 ∈ R2 : t1 [FK ] = t2 [PK ]
Een verwijssleutel kan naar een eigen relatie verwijzen, dit is dus een recursieve relatie.
3.2.5
Other Types of Constraints
Semantic integrity constraints zijn algemene constraints die niet opgelegd kunnen worden door
de data definition language, deze worden opgelegd door de applicaties zelf. Ook een constraint
specification language kan hiervoor zorgen. Een voorbeeld van zo’n constraint is het maximum
aantal werkuren dat een werknemer kan werken.
De functional dependency constraint cre¨eert een functionele relatie tussen 2 sets attributen
X en Y . Een waarde van X bepaalt een unieke waarde van Y in alle toestanden van een relatie:
X → Y . Zie hoofdstukken 14 en 15.
De constraints die tot nu vernoemd werden, zijn state constraints omdat ze bepalen of een
database zich een een geldige toestand bevindt.
Een andere soort constraints zijn de transition constraints en bepalen welke overgangen tussen
databasetoestanden geldig zijn.
Er zijn verscheidene dynamica-regels. De autorisatieregels bepalen welke acties een bepaalde
gebruiker mag uitvoeren. Er bestaan ook precondities en postcondities.
De overgangsregels beschrijven welke volgordes van extensies zijn toegestaan. Bijvoorbeeld:
enkel loonsverhogingen zijn toegestaan, geen verlagingen.
Intrarelationele restricties werken intern, dus binnen 1 relatie. Deze zijn meestal gemakkelijker te controleren. Hier tegenover staan de interrelationele restricties waarbij verschillende
relaties betrokken zijn. Een voorbeeld van deze laatste soort: het salaris van een werknemer moet
altijd kleiner zijn dan het loon van zijn overste.
Tegenwoordig laat men meer soorten restricties automatisch controleren door het DBMS.
22
3.3
3.3.1
Update Operations, Transactions and Dealing with
Constraint Violations
The Insert Operation
Bij het invoegen van nieuwe data moet gekeken worden dat alle bovenstaande constraints niet
overschreden worden. Moest er een constraint overschreden worden, zal het DBMS cascaden. De
toevoeging wordt dan geweigerd en de gebruiker krijgt een melding.
3.3.2
The Delete Operation
Deze operatie kan alleen de referential integrity overschrijden (verwijzing naar een onbestaande of
ongeldige tupel). Het DBMS kan verscheidene dingen doen bij een overschreden constraint:
• De verwijdering weigeren.
• De verwijzende tupels ook weglaten.
• De verwijzende waarden aanpassen (bijvoorbeeld op NULL of default zetten).
• Verschillend reageren in verschillende situaties (ingesteld door de gebruiker).
3.3.3
The Update Operation
Voornamelijk een primaire sleutel aanpassen kan problemen opleveren, er is namelijk een gevaar
voor de uniciteit van de sleutel. De beste oplossing is het verwijderen en direct terug toevoegen van
de tupel.
Bij een wijziging van een verwijssleutel, moet ook de referenti¨ele integriteit gecontroleerd worden.
3.3.4
The Transaction Concept
Een database voert operaties meestal uit in de vorm van transactie zodat er altijd terug naar een
valid state gegaan kan worden moest de huidige operatie mislukken.
23
Hoofdstuk 4
SQL: Data Definition, Constraints, and
Basic Queries and Updates
SQL (Structured Query Language) is een ANSI/ISO-standaardtaal voor een relationeel DBMS.
Het is een gestandaardiseerde taal die gebruikt kan worden voor taken zoals het bevragen en het
aanpassen van gegevens in een relationele databank. SQL kan met vrijwel alle moderne relationele
databankproducten worden gebruikt.
4.1
SQL Data Definition and Data Types
SQL gebruikt de termen table, row en column voor de termen relation, tuple en attribute die in het
formele, relationele model gebruikt worden. Het belangrijkste SQL-commando voor het defini¨eren
van data is het create-statement om schema’s, relaties, domeinen, enz. te cre¨eren.
4.1.1
Schema and Catalog Concepts in SQL
Oudere versies van SQL kenden het concept van relationele database-schema’s niet. Alle tabellen
werden beschouwd als een deel van hetzelfde schema.
Een SQL schema wordt ge¨ıdentificeerd door een schemanaam en bevat een authorization
identifier om de gebruiker of het account die het schema beheert, te identificeren. Het bevat ook
descriptors voor elk element in het schema. Schema elements omvatten tables, views, domains,
constraints, enz.
SQL maakt ook gebruik van een catalog: een verzameling van schema’s in een SQL-omgeving
(een installatie op een computersysteem van een DBMS die gebruik maakt van SQL).
Het aanmaken van een nieuw schema gaat als volgt.
CREATE SCHEMA COMPANY AUTHORIZATION ‘owner’ ;
4.1.2
The CREATE TABLE Command in SQL
Het commando create table wordt gebruikt om een niuewe relatie te defini¨eren door een naam
op te geven en de attributen te specifi¨eren.
Er zijn twee manieren om een nieuwe tabel te defini¨eren, de tweede manier is de aangeraden
manier. Op de plaats van de puntjes moeten nog de attributen met hun datatypes (en domeinen)
ingevuld worden. Dit zien we in 4.1.3.
CREATE TABLE EMPLOYEE (. . . );
CREATE TABLE COMPANY.EMPLOYEE (. . . );
24
4.1.3
Attribute Data Types and Domains in SQL
Voor elk attribuut wordt er tussen de haakjes in het create table-statement een naam en een
datatype ingevuld. Eventueel worden er nog per attribuut enkele restricties toegevoegd. Na de
attributen kunnen er nog tabelrestricties toegevoegd worden.
Er bestaan verschillende soorten datatypes:
• Numeric data types omvatten integers (integer, int en smallint) en floating-point
getallen van verschillende precisie: float (of real) en double precision.
• Character-string data types zijn ofwel fixed-length (char(n) en character(n) met n
het aantal karakters) ofwel variable-length (varchar(n), char varying(n) of character
varying(n) met n het maximum aantal karakters).
• Bit-string data types zijn fixed-length (bit(n)) of variable-length (bit varying(n)).
• Boolean data types hebben de waarden TRUE of FALSE. In SQL is er door de aanwezigheid
van NULL-waarden nog een derde waarde mogelijk: UNKNOWN.
• Het DATE-datatype bestaat uit 10 posities heeft als componenten year, month en day in
de vorm YYYY-MM-DD.
Het TIME-datatype heeft maximum 8 posities en heeft als componenten hour, minute en
second in de vorm HH:MM:SS. Het TIME WITH TIME ZONE-datatype bevat nog 6
extra posities voor een afwijking t.o.v. de standaard universele tijdzone.
• Het TIMESTAMP-datatype bevat de date- en time-velden, plus minimaal 6 posities voor
decimale delen van een seconde en een optionele with time zone-qualifier.
• Het INTERVAL-datatype specifieert een interval (een relatieve waarde) die gebruikt kan
worden om de absolute waarde van een date, time of timestamp te verhogen of te verlagen.
4.2
4.2.1
Specifying Constraints in SQL
Specifying Attribute Constraints and Attribute Defaults
Omdat SQL NULL-waarden toelaat als attribuutwaarde, kunnen we een constraint NOT NULL specifi¨eren als NULL niet toegelaten is als waarde voor een bepaald veld.
Men kan ook een default value defini¨eren voor een attribuut d.m.v. default <value>. Als
er geen default waarde gedefinieerd is, is de default waarde NULL.
Een ander type constraint kan attribuut- en domeinwaarden beperken d.m.v. check x waarbij
x een attribuut- of domeindefinitie is. Bijvoorbeeld:
Dnumber INT NOT NULL
CHECK (Dnumber > 0 AND Dnumber < 21);
De check-clausule kan men ook gebruiken samen met de create domain-statement.
CREATE DOMAIN D NUM AS INTEGER
CHECK (D NUM > 0 AND D NUM < 21);
25
4.2.2
Specifying Key and Referential Integrity Constraints
PRIMARY KEY definieert ´e´en of meerdere attributen die de primaire sleutel van een relatie
vormen. Bijvoorbeeld: de primaire sleutel van department kan als volgt gedefinieerd worden.
Deze restrictie gebeurt bij onmiddellijk bij de definitie van het attribuut.
Dnumber INT PRIMARY KEY;
Men kan een restrictie ook specifi¨eren door met het sleutelwoord CONSTRAINT een restrictie
(met een naam) te defini¨eren. Dit is later makkelijker aanpasbaar.
CONSTRAINT DEPTPK
PRIMARY KEY (Dnumber ),
UNIQUE definieert de alternatieve (secundaire) sleutels. De manieren om alternatieve sleutels te
defini¨eren zijn analoog aan de manieren om primaire sleutels te defini¨eren.
Referenti¨
ele integriteit wordt gespecifieerd door FOREIGN KEY. Bij een integrity violation
zal SQL standaard de restrict-actie uitvoeren. De update-operatie wordt dus geweigerd.
De gebruiker kan ook een andere actie instellen, een referential triggered action kan aan elke
foreign key toegevoegd worden. De andere acties zijn set null, cascade en set default. Zo’n
actie moet meegegeven worden bij een trigger: on delete of on update.
Bijvoorbeeld: we bepalen dat de foreign key “Mgr ssn” in department refereert naar de primaire sleutel “Ssn” in employee. Deze constraint wordt toegevoegd in de definitie van de tabel
department, na de definities van de attributen.
CONSTRAINT DEPTMGRFK
FOREIGN KEY (Mgr ssn) REFERENCES EMPLOYEE(Ssn)
ON DELETE SET DEFAULT
ON UPDATE CASCADE,
4.2.3
Giving Names to Constraints
Het is het beste om alle constraints een naam te geven (zie de voorbeelden in de vorige sectie). De
namen van alle constraints in eenzelfde schema moeten uniek zijn.
4.2.4
Specifying Constraints on Tuples Using CHECK
Als toevoeging op de key- en referentie-constraints zijn er nog andere table-constraints die gedefinieerd kunnen worden door optionele CHECK-clausules op het einde van een CREATE TABLE-statement toe te voegen. Dit zijn de tuple-based constraints omdat ze voor elke tupel
individueel nagekeken worden telkens wanneer een tupel wordt toegevoegd of aangepast.
Bijvoorbeeld: het moment dat een manager aangesteld wordt om een bepaald departement te
leiden, kan uiteraard niet plaatsvinden voordat het departement opgericht wordt. De volgende
constraint wordt toegevoegd achteraan de CREATE TABLE-statement van department.
CHECK (Dept create date <= Mgr start date);
26
4.3
Basis Retrieval Queries in SQL
SQL heeft ´e´en basisoperatie om gegevens op te vragen: SELECT. Deze operatie is niet hetzelfde
als de select-operatie in relationele algebra.
4.3.1
The SELECT-FROM-WHERE Structure of Basic SQL Queries
De basisvorm van het SELECT-statement is hieronder gegeven. Dit wordt ook wel het mapping
block of het select-from-where block genoemd.
SELECT <attributenlijst>
FROM <tabellenlijst>
WHERE <condities>
Hierbij wordt <condities> ingevuld door een Booleaanse conditie: de selectievoorwaarde. Een
conditie als (Dnumber = Dno) noemen we een joinconditie omdat het 2 tupels combineert.
Voor voorbeelden van select-from-where blokken, zie pagina 94-96.
4.3.2
Ambiguous Attribute Names, Aliasing, Renaming, and Tuple Variables
In SQL kunnen we dezelfde naam gebruiken voor 2 of meerdere attributen, zolang ze zich in verschillende relaties bevinden. Bijvoorbeeld:
WHERE CAR.Name = BICYCLE.Name;
Als we een query hebben die tweemaal gebruik maakt van dezelfde relatie, kunnen we de aparte
verwijzingen aparte namen geven: een alias. Deze aliassen zijn dan een soort kopie¨en van de
originele relatie. Bijvoorbeeld:
SELECT E.Fname, E.Lname, S.Fname, S.Lname
FROM EMPLOYEE AS E, EMPLOYEE AS S
WHERE E.Super ssn = S.Ssn;
Het is ook mogelijk om de attributen van een relatie te hernoemen. Bijvoorbeeld:
FROM EMPLOYEE AS E(Fn, Mi, Ln, Ssn, Bd, Addr, Sex, Sal, SSsn, Dno)
4.3.3
Unspecified WHERE Clause and Use of the Asterisk
Als de WHERE-clausule ontbreekt, wordt er geen conditie opgelegd wordt op de tupels. Alle
tupels van de relatie (gespecifieerd in de FROM-clausule) voldoen aan de query.
Als er meer dan 1 relatie gespecifieerd is in de FROM-clausule en als er geen WHERE-clausule
is, dan wordt het Carthesisch product van de relaties genomen.
Als men alle attributen wil selecteren in de SELECT-clausule, zet men gewoon een asterisk (*)
achter SELECT. Dan moet men niet alle mogelijke attributen opsommen.
4.3.4
Tables as Sets in SQL
SQL behandelt een tabel meestal niet als een set maar als een multiset. Duplicaten van tupels
kunnen meer dan ´e´en keer voorkomen in een tabel en in het resultaat van een query. SQL verwijdert
duplicaten niet automatisch uit het resultaat van een query, dit heeft verschillende redenen.
• Het verwijderen van duplicaten is een intensieve taak. Men kan dit toch doen door alle tupels
te sorteren en dan de duplicaten te verwijderen.
27
• Het kan zijn dat de gebruiker de duplicaten wel wil zien in het resultaat van zijn query.
• Als een aggregaatfunctie wordt toegepast op tupels (zie 5.1.7), willen we in de meeste gevallen
geen duplicaten verwijderen.
Als we toch alle duplicaten uit het resultaat willen verwijderen, kunnen we SELECT DISTINCT
gebruiken. Als we de duplicaten wel willen zien, kunnen we SELECT ALL gebruiken, dit is de
standaard optie.
SQL maakt ook gebruik van de wiskundige set theory dat onderdeel is van de relationele algebra (zie H6). Er bestaan 3 verzamelingsoperaties: UNION, EXCEPT en INTERSECT. Het
resultaat van deze operatoren is een set van tupels, dit wil zeggen dat duplicaten verwijderd worden. SQL heeft ook corresponderende operaties voor multisets, hierbij wordt het keyword ALL
toegevoegd, bijvoorbeeld UNION ALL. Deze operaties worden als volgt gebruikt.
(<select-from-where block >) UNION (<select-from-where block >)
4.3.5
Substring Pattern Matching and Arithmetic Operators
In SQL kunnen we vergelijkingscondities defini¨eren op basis van substrings, dit doen we met de
vergelijkingsoperator LIKE. We kunnen dit gebruiken voor string pattern matching, we plaatsen
hiervoor de substring tussen 2 %-tekens. Het %-teken staat voor 0 of meerdere willekeurige tekens,
een underscore ( ) vervangt een enkel karakter. Bijvoorbeeld: we willen de namen opvragen van de
werknemers die in Houston wonen.
SELECT Fname, Lname
FROM EMPLOYEE
WHERE Address LIKE ‘%Houston%’ ;
We kunnen ook gewone wiskundige operaties gebruiken: optellen (+), aftrekken (-), vermenigvuldigen (*) en delen (/). Twee strings kunnen we samenvoegen met de samenvoegingsoperator ||.
De vergelijkingsoperator BETWEEN kan je gebruiken om alle tupels met een attribuutwaarde
tussen 2 constanten te selecteren. De volgende 2 condities zijn identiek.
(Salary > 30000) AND (Salary 6 40000)
Salary BETWEEN 30000 AND 40000
4.3.6
Ordering of Query Results
SQL laat met ORDER BY toe het resultaat van een query te sorteren volgens de waarden van 1
of meerdere attributen die voorkomen in dit resultaat. We kunnen gebruik maken van DESC en
ASC (standaard) om de resultaten in dalende (resp. stijgende) volgorde weer te geven.
SELECT Fname, Lname
FROM EMPLOYEE
ORDER BY Fname DESC, Lname ASC;
4.3.7
Discussion and Summary of Basic SQL Retrieval Queries
Kort samengevat kan een retrieval query in SQL uit 4 delen bestaan:
SELECT <attributenlijst>
FROM <tabellenlijst>
[ WHERE <conditie> ]
[ ORDER BY <attributenlijst> ];
28
4.4
4.4.1
INSERT, DELETE, and UPDATE Statements in SQL
The INSERT Command
INSERT wordt gebruikt om een enkele tupel toe te voegen aan een relatie. Hiervoor specifi¨eren we
de relatienaam en een lijst van waarden voor deze tupel. De waarden moeten in dezelfde volgorde
staan als de attributen in de relatie (zoals beschreven in CREATE TABLE).
INSERT INTO DEPARTMENT
VALUES (‘Research’, 5, ‘333445555’, ‘1988-05-22’ );
We kunnen een attribuut weglaten als NULL toegelaten is of als er een default waarde bestaat.
INSERT INTO EMPLOYEE(Fname, Lname, Ssn)
VALUES (‘Richard’, ‘Marini’, ‘653298653’ );
4.4.2
The DELETE Command
DELETE wordt gebruikt om bepaalde tuples te verwijderen uit een relatie en bevat een WHEREclausule om de tuples te selecteren.
DELETE FROM EMPLOYEE
WHERE Lname = ‘Brown’;
Om de hele tabel te verwijderen, kunnen we DROP TABLE gebruiken.
4.4.3
The UPDATE Command
UPDATE wordt gebruikt om attribuutwaarden van 1 of meerdere geselecteerde tupels aan te
passen. Ook hier is een WHERE-clausule nodig om de aan te passen tuples te selecteren. Een
bijkomende SET specifieert de aan te passen attributen en hun nieuwe waarden.
UPDATE PROJECT
SET Plocation = ‘Bellaire’, Dnum = 5
WHERE Pnumber = 10;
4.5
Additional Features of SQL
• In hoofdstuk 5 bespreken we verschillende technieken om complexe retrieval query’s te maken.
• SQL heeft verschillende technieken om programma’s te schrijven in verschillende programmeertalen om toegang te krijgen tot databases.
• Er was vroeger de mogelijkheid om indices te cre¨eren: CREATE INDEX.
• SQL heeft transaction control commands, zie hoofdstuk 20.
• SQL kan omgaan met privileges.
• In SQL is het mogelijk om triggers te defini¨eren.
• SQL heeft verschillende eigenschappen overge¨erfd van objectgeori¨enteerde modellen, dit leidt
tot geavanceerde relationele systemen: object-relational.
• SQL en relationele databases kunnen overweg met nieuwe technologie¨en zoals XML.
29
Hoofdstuk 5
SQL: Advanced Queries, Assertions,
Triggers, and Views
5.1
5.1.1
More Complex SQL Retrieval Queries
Comparisons Involving NULL and Three-Valued Logic
In SQL kan NULL 3 verschillende betekenissen hebben:
1. Unknown value. Een veld dat leeggelaten wordt (bv. de geboortedatum niet invullen).
2. Unavailable or withheld value. Data die verborgen gehouden wordt (bv. een persoon
heeft een telefoon, maar wil zijn nummer niet geven om persoonlijke redenen).
3. Not applicable attribute. Data die niet van toepassing is (bv. een diploma-veld voor een
persoon die geen studies voltooid heeft).
Omdat het vaak niet mogelijk is om te achterhalen over welk type NULL het gaat, gaat men in SQL
ervan uit dat elke NULL-waarde anders is dan elke andere NULL-waarde. Als men een vergelijking
(bv. AND, OR en NOT) uitvoert met een NULL-waarde, kan de juiste uitkomst zowel TRUE als
FALSE zijn. Daarom wordt de uitkomst van zo’n vergelijking altijd met UNKNOWN aangeduid. SQL
gebruikt dus three-valued logic in plaats van de standaard Boolean logic (two-valued ).
Tabel 5.1 op pagina 112 toont alle mogelijke uitkomsten in deze logica.
De algemene regel is dat in select-project-join queries enkel de combinaties van tupels die evalueren naar TRUE geselecteerd worden. Combinaties van tupels die evalueren naar FALSE of UNKNOWN
worden dus niet geselecteerd. De uitzonderingen op deze regel zien we in 5.1.6.
SQL laat queries toe om na te gaan of een bepaalde waarde NULL is. In plaats van de gewone
vergelijkingsoperatoren, gebruikt men IS of IS NOT.
WHERE Super ssn IS NOT NULL;
5.1.2
Nested Queries, Tuples, and Set/Multiset Comparisons
Voor sommige queries is het nodig dat er bepaalde waarden uit de database gehaald worden die dan
gebruikt worden in een vergelijkingsconditie. Dit soort queries kan in SQL makkelijk geformuleerd
worden met zogenaamde nested queries. Dit zijn volledige select-from-where blokken binnen de
WHERE-clausule van een andere query (de outer query).
We introduceren ook de vergelijkingsoperator IN, hiermee kan een waarde vergeleken worden
met een set (verzameling) van waarden. De operator evalueert naar TRUE als het element een
onderdeel is van de verzameling.
30
SELECT DISTINCT Pnumber
FROM PROJECT
WHERE Pnumber IN (<select-from-where block >);
Je kan ook tupels van waarden vergelijken door ze binnen haakjes te zetten. Bijvoorbeeld: de
volgende query selecteert alle werknemers die werken aan een project met dezelfde (project, uren)combinatie als werknemer 123456789 aan dat project werkt.
SELECT DISTINCT Essn
FROM WORKS ON
WHERE (Pno, Hours) IN
( SELECT Pno, Hours
FROM WORKS ON
WHERE Essn = ‘123456789’ );
Er zijn nog andere operatoren om een enkele waarden v te vergelijken met een set of multiset. De
‘= ANY’-operator is in essentie hetzelfde als de IN-operator maar kan gecombineerd worden met
de volgende operatoren: >, >=, <, <= en <>.
Het keyword ALL kan ook gecombineerd worden met deze operatoren. Zo kan men bijvoorbeeld
de namen vragen van de werknemers die meer verdienen dan alle werknemers uit departement 5.
SELECT Fname, Lname
FROM EMPLOYEE
WHERE Salary > ALL
( SELECT Salary
FROM EMPLOYEE
WHERE Dno = 5 );
5.1.3
Correlated Nested Queries
Twee queries zijn correlated als de binnenste query afhankelijk is van de buitenste query. Dit is
het geval als bijvoorbeeld de binnenste query refereert naar de buitenste query. De binnenste query
moet voor iedere waarde van de buitenste query uitgevoerd worden.
We kunnen de volgende query als volgt zien. Voor elke employee-tupel ek : de binnenste query
haalt de “Essn”-waarden op van alle dependent-tupels met hetzelfde geslacht en dezelfde naam
als ek . Als de “Ssn”-waarde van ek voorkomt in het resultaat van de binnenste query, selecteer die
employee-tupel ek dan.
SELECT E.Fname, E.Lname
FROM EMPLOYEE AS E
WHERE E.Ssn IN
( SELECT Essn
FROM DEPENDENT AS D
WHERE E.Fname = D.Dependent name AND E.Sex = D.Sex );
5.1.4
The EXISTS and UNIQUE Functions in SQL
De EXISTS-functie wordt gebruikt om te kijken of het resultaat van een correlated nested query
leeg is of niet. De functie evalueert naar TRUE als als het resultaat van de nested query minstens 1
tuple bevat, anders naar FALSE. Er bestaat ook NOT EXISTS.
De volgende query kan men als volgt zien. Voor elke employee-tupel ek : haal alle dependenttupels op die verwant zijn aan ek . Als er geen gerelateerde dependent-tupels bestaan, zal ek
geselecteerd niet worden, in het andere geval wel.
31
SELECT E.Fname, E.Lname
FROM EMPLOYEE AS E
WHERE EXISTS
( SELECT *
FROM DEPENDENT AS D
WHERE E.Ssn = D.Essn );
Het is ook mogelijk om het verschil van twee verzamelingen te nemen, hiervoor gebruiken we de
EXCEPT-operator. Voor een voorbeeld verwijzen we naar query Q3A op pagina 117.
De UNIQUE(Q)-operator evalueert naar TRUE als er geen duplicaten voorkomen in het resultaat van de query Q, in het andere geval FALSE. Deze operator kan gebruikt worden om te testen
of het resultaat van een geneste queryeen set of een multiset is.
5.1.5
Explicit Sets and Renaming of Attributes in SQL
In plaats van een nested query te gebruiken in de WHERE-clausule, is het ook mogelijk om zelf een
expliciete set van waarden te defini¨eren. Bijvoorbeeld: de volgende query vraagt de “Essn”-waarden
op van alle werknemers die werken aan project 1, 2 of 3.
SELECT DISTINCT Essn
FROM WORKS ON
WHERE Pno IN (1, 2, 3);
Het is ook mogelijk om attributen in het resultaat te hernoemen met de AS-operator.
SELECT E.Lname AS Employee name, S.Lname AS Supervisor name
FROM EMPLOYEE AS E, EMPLOYEE AS S
WHERE E.Super ssn = S.Ssn;
5.1.6
Joined Tables in SQL and Outer Joins
Het concept van joined tables wordt gebruikt om te vermijden dat een gebruiker zeer veel ‘=’
moet gebruiken in de WHERE-clausule.
Bijvoorbeeld: we willen de namen van alle werknemers opvragen die voor het onderzoeksdepartement werken. De conditie (Dno = Dnumber) zorgt ervoor dat enkel zinvolle tupels gegenereerd
worden met de JOIN-operator.
SELECT Fname, Lname
FROM ( EMPLOYEE JOIN DEPARTMENT ON Dno = Dnumber )
WHERE Dname = ‘Research’;
We kunnen ook gebruik maken van NATURAL JOIN om tabellen samen te voegen. Hierbij wordt
er geen conditie meegegeven maar wordt er gejoind op elk paar attributen met dezelfde naam. Als
de naam van de attributen waarop we willen joinen niet overeenkomen, kunnen we de AS-operator
gebruiken om ze te hernoemen.
SELECT Fname, Lname
FROM ( EMPLOYEE NATURAL JOIN
DEPARTMENT AS DEPT(Dname, Dno, Mssn, Msdate)
)
WHERE Dname = ‘Research’;
Standaard wordt er gejoind met een inner join, hiertegenover staat een outer join. Voor meer
uitleg, zie hoofdstuk 6.
Het is ook toegelaten om joins te nesten, dit noemen we een multiway join.
32
5.1.7
Aggregate Functions in SQL
Aggregaatfuncties laten toe om tupels in een resultaat samen te vatten. De ingebouwde aggregaatfuncties zijn COUNT, SUM, MAX, MIN en AVG.
De COUNT-functie telt het aantal tupels die een bepaalde conditie voldoen en geeft dit aantal
terug als resultaat. Bijvoorbeeld: de volgende query geeft het aantal werknemers terug.
SELECT COUNT (*)
FROM EMPLOYEE;
De volgende query geeft als resultaat het aantal unieke lonen uit de employee-relatie.
SELECT COUNT (DISTINCT Salary)
FROM EMPLOYEE;
COUNT kan ook bij de WHERE-clausule gebruikt worden om bijvoorbeeld werknemers op te
vragen die 2 of meer dependents hebben.
SELECT E.Fname, E.Lname
FROM EMPLOYEE AS E
WHERE ( SELECT COUNT (*)
FROM DEPENDENT AS D
WHERE E.Ssn = D.Essn ) >= 2;
Op deze manier kunnen ook de andere aggregaatfuncties gebruikt worden.
5.1.8
Grouping: The GROUP BY and HAVING Clauses
We willen vaak aggregaatfuncties toepassen op bepaalde groepen van tupels waarbij de groepen
gedefinieerd worden door een bepaald attribuut. Het attribuut waarop gegroepeerd moet worden, duiden we aan met GROUP BY. Als er NULL-waarden voorkomen in het attribuut waarop
gegroepeerd wordt, zal er voor deze tupels een aparte groep gemaakt worden.
Bijvoorbeeld: we willen voor elk departement het departementsnummer, het aantal werknemers
en hun gemiddeld loon opvragen. We nemen als groep ‘alle werknemers met hetzelfde departementsnummer’. Figuur 5.1a op pagina 123 is een visualisatie van deze query.
SELECT Dno, COUNT (*), AVG (Salary)
FROM EMPLOYEE
GROUP BY Dno
Soms willen we enkel informatie over groepen die voldoen aan een bepaalde voorwaarde, hiervoor
kunnen we de clausule HAVING gebruiken.
Het verschil tussen HAVING en een conditie opleggen in WHERE is dat we bij de HAVINGclausule een conditie kunnen opleggen voor een volledige groep tupels. De WHERE-clausule
daarentegen kan enkel condities opleggen aan individuele tupels.
Bijvoorbeeld: we willen van elk project met meer dan 2 werknemers het projectnummer, de
projectnaam en het aantal werknemers opvragen.
SELECT Pnumber, Pname, COUNT (*)
FROM PROJECT, WORKS ON
WHERE Pnumber = Pno
GROUP BY Pnumber, Pname
HAVING COUNT (*) > 2;
33
5.2
5.2.1
Specifying Constraints as Assertions and Actions as
Triggers
Specifying General Constraints as Assertions in SQL
CREATE ASSERTION wordt gebruikt om extra constraints op te leggen, naast de restricties
op tabellen of attribuutwaarden (die bij het aanmaken van een tabel gecre¨eerd worden). Elke latere
wijziging in de gegevensbank wordt slechts toegelaten als er aan de assertie voldaan is.
Bijvoorbeeld: we willen opleggen dat een werknemer nooit meer kan verdienen dan zijn manager.
CREATE ASSERTION SALARY CONSTRAINT
CHECK (
NOT EXISTS (
SELECT *
FROM EMPLOYEE E, EMPLOYEE M, DEPARTMENT D
WHERE E.Salary > M.Salary
AND E.Dno > D.Dnumber
AND D.Mgr ssn > M.Ssn
)
);
5.2.2
Introduction to Triggers in SQL
Bij CREATE TRIGGER wordt er een actie opgegeven die ondernomen zal worden als er niet aan
een bepaalde voorwaarde is voldaan. Triggers zullen dus een database monitoren. Een typische
trigger bevat de volgende elementen:
• Een event die bepaalt wanneer een conditie gecheckt moet worden (meestal bij een update).
• De conditie die bepaalt wanneer een actie uitgevoerd moet worden.
• De actie zelf, dit is een SQL-query of een extern programma.
Voor een voorbeeld van een trigger, zie R5 op pagina 128-129.
5.3
5.3.1
Views (Virtual Tables) in SQL
Concept of a View in SQL
Een view is een tabel die afgeleid wordt uit andere tabellen, de tupels van een view worden niet
expliciet opgeslagen. De defini¨
erende tabellen kunnen ‘echte’ tabellen of ook views zijn. Een
view is enkel virtueel en wordt niet gematerialiseerd.
Views zijn handig als beveiligingsmechanisme, een gebruiker krijgt maar zicht op een deel van de
database. Er is ook geen redundantie doordat er geen nieuwe (expliciete) tabellen gemaakt worden.
5.3.2
Specification of Views in SQL
Men kan een view aanmaken met CREATE VIEW. Een view heeft een bepaalde naam, een
attributenlijst en een query om aan deze attributen te geraken. Na het aanmaken van een view kan
men hierop queries uitvoeren alsof het een echte tabel was.
Een view wordt verwijderd met het commando DROP VIEW.
34
Bijvoorbeeld: we willen een view hebben van alle werknemers die aan een project werken.
CREATE VIEW WORKS ON 1
AS
SELECT Fname, Lname, Pname, Hours
FROM EMPLOYEE, PROJECT, WORKS ON
WHERE Ssn = Essn AND Pno = Pnumber;
5.3.3
View Implementation, View Update, and Inline Views
Het is niet simpel om queries die verwijzen naar views effici¨ent te implementeren. Er bestaan 2
benaderingen om dit probleem aan te pakken.
• Query modification
De query van de view wordt met algoritmes omgevormd tot een query op de onderliggende
tabellen. Het grote nadeel van deze methode is dat de resulterende queries soms heel complex
kunnen zijn, vooral bij views die gedefinieerd zijn door reeds complexe queries.
• View materialization
Als men meerdere queries die naar een bepaalde view verwijzen, na elkaar wil uitvoeren,
kan men tijdelijk de view materialiseren (opslaan als een ’echte’ tabel). Hierbij moet er
natuurlijk een effici¨ent systeem bedacht worden om de echte tabellen up-to-date te houden
met de opgeslagen view.
Niet elke query die verwijst naar een view kan zinvol zijn. Bijvoorbeeld: een query die een attribuut
aanpast dat in de view door de aggregaatfunctie SUM gegenereerd wordt, heeft geen zinvolle vertaling naar een query op een ’echte’ tabel. Soms kan er ook ambigu¨ıteit optreden bij het aanpassen
van een view.
Over het algemeen is een update op een view enkel haalbaar als deze query zonder ambigu¨ıteit
vertaald kan worden naar een zinvolle query op de onderliggende tabellen.
5.4
5.4.1
Schema Change Statements in SQL
The DROP Command
Het DROP-commando wordt gebruikt om schema-elementen (met een naam) te verwijderen, dit
zijn tabellen, domeinen of constraints. Men kan ook een schema zelf verwijderen.
Er zijn 2 manieren waarop een DROP SCHEMA uitgevoerd kan worden.
• CASCADE. Alle schema-elementen en het schema zelf worden verwijderd.
• RESTRICT. Het schema wordt enkel verwijderd als het geen elementen bevat.
Bij DROP TABLE is er een analoog gedrag: bij CASCADE wordt de tabel verwijderd. Bij
RESTRICT wordt de tabel enkel verwijderd als er geen referenties naar de tabel bestaan.
5.4.2
The ALTER Command
De definitie van een tabel of andere benoemde schema-elementen kan veranderd worden met het
ALTER-commando. Er kan bijvoorbeeld een kolom toegevoegd worden aan een tabel of de naam
van een kolom kan veranderd worden.
ALTER TABLE COMPANY.EMPLOYEE
DROP COLUMN Address CASCADE;
ALTER TABLE COMPANY.DEPARTMENT
ALTER COLUMN Mgr ssn SET DEFAULT ‘333445555’ ;
35
Hoofdstuk 6
Formal Relational Languages: The
Algebra and Calculus
In dit hoofdstuk behandelen we twee formele talen voor het relationele model: relationele algebra
en relationele calculus.
6.1
6.1.1
Unary Relational Operations: SELECT & PROJECT
The SELECT Operation
De select-operatie wordt gebruikt om een subset van tupels uit een extensie op te vragen die
voldoen aan een bepaalde conditie. Intu¨ıtief kan het gezien worden als een filter. We beginnen met
een voorbeeld om de werknemers op te vragen die meer verdienen dan 3000.
σ Salary > 3000 (employee)
Een generiek select-statement uit een database ziet er als volgt uit.
σF (R) = σ<conditie> (R)
Het sigma-symbool (σ) wordt hier gebruikt om select aan te duiden. Het selectiecriterium F
(of conditie) is een logische formule die attributen uit de relatie R gebruikt. Een generieke conditie
heeft ´e´en van de volgende vormen.
<attribuutnaam> <vergelijking> <constante>
<attribuutnaam> <vergelijking> <andere attribuutnaam>
De <vergelijking> gebruikt meestal een van de volgende operatoren: {=, <, >, 6, >, 6=}. Condities
kunnen samengesteld worden met de operatoren {∧, ∨, ¬} om meervoudige formules te maken.
De select-operator is unair, hij wordt dus toegepast op een enkele relatie. De select-operator
is ook commutatief, voor het resultaat maakt het dus niet uit in welke volgorde ze uitgevoerd
worden. Dit kan wel een verschil maken in performantie. Er geldt dus:
σC1 (σC2 (. . . (σCn (r)) . . . )) = σC1 ∧ C2 ∧ ... ∧ Cn (r)
In SQL wordt de select-conditie meestal gespecifieerd in het where-gedeelte. Hieronder staat
een voorbeeld van een select-operatie en de bijhorende SQL-query.
σ(Dno = 4) ∧ (Salary > 25000) (employee)
SELECT *
FROM EMPLOYEE
WHERE Dno = 4 AND Salary > 25000
36
6.1.2
The PROJECT Operation
Als we een relatie als een tabel voorstellen, kiest de select-operatie enkele rijen (tupels) hieruit.
De project-operatie daarentegen selecteert bepaalde kolommen. Dus als we enkel ge¨ınteresseerd zijn in bepaalde attributen van een relatie, gebruiken we de project-operatie. Om bijvoorbeeld de voornamen en lonen van alle werknemers op te vragen, gebruiken we de volgende query.
π Fname, Salary (employee)
Hierbij is π dus het symbool voor project. De generieke vorm van een project-operatie heeft de
volgende vorm:
πX (R) = π<attributenlijst> (R)
De attributenlijst is de lijst van attributen die we willen opvragen van de relatie R, met komma’s
tussen de individuele attributen.
Als er attributen opgevraagd worden die geen key zijn, is de kans groot dat er duplicaten
optreden. De project-operatie verwijdert deze duplicaten en geeft dus een lijst met unieke
tupels terug. Moesten duplicaten niet verwijderd worden, zou het resultaat geen tupel zijn maar
een multiset of bag. In het formele model is dit niet toegelaten, in SQL wel.
De project-operatie is niet commutatief, er geldt dat πX (πY (r)) enkel gedefinieerd is als X ⊆ Y .
De project-operatie is dus idempotent, enkel de laatste (buitenste) projectie van opeenvolgende
projecties moet uitgevoerd worden. Dit is makkelijk in te zien met de volgende query’s, de volgende
query vraagt enkel de voornamen op van de werknemers.
π Fname (πBdate, Fname (employee))
De volgende query is ongeldig omdat “Bdate” niet voorkomt in de tupels van voornamen.
π Bdate, Fname (πFname (employee))
Hieronder staat een voorbeeld van een project-operatie en de bijhorende SQL-query.
π Bdate, Salary (employee)
SELECT DISTINCT Bdate, Salary
FROM EMPLOYEE
Merk op dat als we distinct uit de SQL-query weglaten, de duplicate tupels niet verwijderd worden
en we dus niet hetzelfde resultaat krijgen als in de formele relationele algebra.
6.1.3
Sequences of Operations and the RENAME Operation
In de praktijk willen we meestal resultaten van meerdere queries. Dit kan op 2 manieren gebeuren:
ofwel alle queries nesten ofwel gebruik maken van tussenresultaten en daar de opeenvolgende
queries op uitvoeren. In het tweede geval moeten we namen geven aan de tussenresultaten.
Om bijvoorbeeld de voornaam, achternaam en het salaris op te vragen van alle werknemers in
departement 5, kunnen we als volgt te werk gaan:
π Fname, Lname, Salary (σ Dno = 5 (employee))
Door met tussenresultaten te werken, kan men ook het volgende doen:
dep5 emps ← σ Dno = 5 (employee)
result ← π Fname, Lname, Salary (dep5 emps)
37
De tweede manier (met tussenresultaten) is beter leesbaar. Deze manier kunnen we ook gebruiken
om de attribuutnamen in het resultaat een andere naam te geven. Dit gaat als volgt.
temp ← σ Dno = 5 (employee)
R (FirstName, LastName, Salary) ← π Fname, Lname, Salary (temp)
We kunnen ook een formele rename-operatie invoeren, deze heeft de volgende generieke vorm.
ρ S(B1 ,...,Bn ) (R) = ρS (R) = ρ (B1 ,...,Bn ) (R)
Hierbij is R een relatie van graad n, S de nieuwe naam voor de relatie, Bi de nieuwe attribuutnamen
en ρ het symbool van de rename-operatie. In de generieke vorm hierboven hernoemen we in de
eerste term zowel de relatie als de attribuutnamen, in de tweede term enkel de relatie en in de derde
term enkel de attributen.
In SQL gebeurt de rename-operatie met de as-functie.
SELECT E.Fname AS FirstName, E.Lname AS LastName, E.Salary AS Salary
FROM EMPLOYEE AS E
WHERE E.Dno = 5
6.2
Relational Algebra Operations from Set Theory
6.2.1
The UNION, INTERSECTION, and MINUS Operations
De volgende groep van operaties uit de relationele algebra, zijn de standaard wiskundige verzamelingsoperatoren.
Om bijvoorbeeld de “Ssn”-nummers op te vragen van de werknemers die in departement 5
werken of de werknemers die baas zijn van een werknemer uit departement 5, kunnen we de union
(unie) als volgt gebruiken.
dep5 emps ← σ Dno = 5 (employee)
result1 ← π Ssn (dep5 emps)
result2(Ssn) ← π Super ssn (dep5 emps)
result ← result1 ∪ result2
result1 bevat de “Ssn”-nummers van alle werknemers uit departement 5, result2 bevat alle
“Ssn”-nummers van de bazen van werknemers uit departement 5. result bevat dan de unie van
beide resultaten (zonder duplicaten).
Naast union bestaan er ook intersection (doorsnede) en set difference (verschil), ook wel
minus of except genoemd. Dit zijn binaire operaties die enkel gebruikt worden op twee verzamelingen van hetzelfde type. Dit wordt ook wel union compatibility of type compatibility
genoemd. Twee relaties worden compatibel genoemd als ze dezelfde graad hebben en als de corresponderende attributen hetzelfde domein hebben.
We nemen de conventie aan dat de resultaatverzameling dezelfde attribuutnamen gebruikt als
de eerste relatie waarop de operatie toegepast wordt.
Het is makkelijk in te zien dat union en intersection commutatief en associatief zijn. set
difference is dat over het algemeen niet.
In SQL komen union, intersect en except overeen met de eerder beschreven operaties. Daarnaast bestaan er in SQL ook union all, intersect all en except all, deze verwijderen de
duplicaten niet.
38
6.2.2
The CARTESIAN PRODUCT (CROSS PRODUCT) Operation
Het Carthesisch product of kruisproduct (×) is ook een binaire operatie, maar de twee verzamelingen
moeten niet union compatible zijn, in tegenstelling tot de eerder besproken operaties.
Als we bijvoorbeeld A × B uitvoeren, wordt elke tupel uit A gecombineerd met elke tupel uit
B. Stel A bevat n elementen en B bevat m elementen, dan zal het resultaat van het kruisproduct
exact m · n tupels bevatten.
Formeler: een kruisproduct Q = R × S heeft als schema Q(A1 , . . . , An , B1 , . . . , Bm ) en bevat
elke combinatie van tupels uit R en S.
Voorbeeld: op de tabellen voornamen en achternamen voeren we de volgende operatie uit om
de tabel resultaat te bekomen.
resultaat ← voornamen × achternamen
VOORNAMEN
Voorn id Voorn
1
George
2
Albert
ACHTERNAMEN
Achtern id Achtern
1
Orwell
2
Hoffman
=⇒
Voorn id
1
1
2
2
RESULTAAT
Voorn Achtern id
George
1
George
2
Albert
1
Albert
2
Achtern
Orwell
Hoffman
Orwell
Hoffman
We zien meteen dat het resultaat op zich geen betekenis heeft. Over het algemeen is ze enkel nuttig
als we nadien alle ongeldige combinaties wegfilteren, dit doen we meestal door de keys te vergelijken.
echt resultaat ← σ Voorn id = Achtern id (resultaat)
ECHT RESULTAAT
Voorn id Voorn Achtern id Achtern
1
George
1
Orwell
2
Albert
2
Hoffman
Omdat het Carthesisch product zonder de select-operatie niet zo nuttig is (omdat er dan duplicaten bestaan), heeft men de join-operatie ontwikkeld, deze combineert direct de 2 operaties. In
de volgende sectie gaan we hier dieper op in.
In SQL noemt men het Carthesisch product cross join.
6.3
6.3.1
Binary Relational Operations: JOIN and DIVISION
The JOIN Operation
De join-operatie (symbool: ./) wordt gebruikt om gerelateerde tupels van 2 relaties samen te
voegen tot ‘grotere’ tupels. join is eigenlijk een uitvoering van het Carthesisch product, gevolgd
door een selectie. We zullen het nut aantonen door middel van een voorbeeld:
dept mgr ← department ./ Mgr ssn = Ssn employee
result ← π Dname, Lname, Fname (dept mgr)
In de eerste query worden de tabellen departement en employee gejoind met de conditie
Mgr ssn = Ssn. We krijgen dus in dept mgr een lijst van alle departementen met voor elk
departement ook de departementsmanager. Daarna volgt een rename-operatie.
Het verschil tussen het Carthesisch product (×) en de join-operatie (./) is dat bij de joinoperatie direct een conditie meegegeven kan worden.
39
Een generieke join-operatie heeft de volgende vorm (met selectiecriterium F en relaties R, S):
R ./F S = R ./<conditie> S = σF (R × S)
Stel R heeft n tupels en S heeft m tupels, dan zal de join tussen R en S als resultaat n + m tupels
hebben. Ook hier kunnen {∧, ∨, ¬} gebruikt worden om condities samen te voegen.
Een conditie is een theta-join als in F = C1 ∧ · · · ∧ Cn elke Ck van de vorm Ai θ Bj is. Hierbij
geldt dat θ ∈ {=, <, >, 6, >, 6=} en dat dom(Ai ) = dom(Bj ).
Tupels waarvan een join-attribuut NULL is, zullen niet worden opgenomen in het resultaat.
6.3.2
Variations of JOIN: The EQUIJOIN and NATURAL JOIN
De meest gebruikte join-condities zijn deze met enkel gelijkheidscondities Ck in F . Deze noemen
we een equijoin. In het resultaat van een equijoin zal er in elke tupel minstens 1 paar attributen
gelijke waarden hebben.
Als deze attributen die gelijk moeten zijn dezelfde naam hebben, kunnen we gebruik maken van
een natural join. Hierbij moet er geen join-conditie meegegeven worden, maar zal er gejoind
worden op attributen met dezelfde naam. Als de attributen waarop we willen joinen niet dezelfde
naam hebben, moet er eerst een rename-operatie uitgevoerd worden.
Een natural join is dus gelijk aan het uitvoeren van een equijoin waarna men de overtollige
attributen weglaat. Dus per voorwaarde Ai = Bj wordt enkel Ai of Bj behouden.
De generieke notatie van een natural join is als volgt:
R ∗F S
Als X en Y attribuutlijsten zijn van gelijke lengte, dan kan men de natural join ook vereenvoudigd noteren als R ∗X,Y S. De conditie is dan X1 = Y1 ∧ · · · ∧ Xk = Yk . Enkel de attributen in X
blijven behouden na de join.
Een andere vereenvoudigde notatie is R ∗ S waarbij de lijsten X en Y impliciet zijn: ze bevatten
alle attributen die dezelfde naam hebben in R en S.
Als we bijvoorbeeld elke project-tupel willen joinen met elke department-tupel die het project
controleert, kan dit met de volgende query:
proj dept ← project ∗ ρ (Dname, Dnum, Mgr ssn, Mgr start date) (department)
Je kan zien dat er een rename-operatie uitgevoerd wordt: “Dnumber” uit de department-relatie
wordt hernoemd naar “Dnum” zodat de attribuutnaam overeenkomt met die in project. Daarna
wordt er een natural join uitgevoerd.
Het attribuut “Dnum” wordt hier het join-attribuut voor de natural join genoemd, omdat
het het enige attribuut is met dezelfde naam in beide relaties. Als er in beide relaties geen attributen
voorkomen met dezelfde naam zal het resultaat van een natural join leeg zijn.
Bovenstaande query had ook in 2 stappen uitgevoerd kunnen worden.
dept ← ρ (Dname, Dnum, Mgr ssn, Mgr start date) (department)
proj dept ← project ∗ dept
De join-operatie combineert dus data uit 2 relaties zodat gerelateerde informatie in 1 tabel getoond
kan worden. Dit soort operaties noemt men ook inner joins.
join-operaties kunnen ook gebeuren tussen meer dan 2 relaties, bijvoorbeeld:
project ./ Dnum = Dnumber department ./ Mgr ssn = Ssn employee
40
6.3.3
A Complete Set of Relational Algebra Operations
Het is aangetoond dat de set van relationele algebra operaties {σ, π, ∪, ρ, −, ×} een complete set
is. Dit wil zegen dat elke andere operatie uit de relationele algebra geschreven kan worden als een
combinatie van elementen uit deze set.
Bijvoorbeeld, de intersection-operatie kan uitgedrukt worden met union en minus.
R ∩ S ≡ (R ∪ S) − R − S) ∪ (S − R)
Veel operaties uit de relationele algebra zijn dus niet strikt noodzakelijk maar zijn ingevoerd om
het ingeven van queries makkelijker te maken.
6.3.4
The DIVISION Operation
De division-operatie heeft als symbool ÷ en is zinvol voor een speciale vorm van queries.
Een voorbeeld hiervan is “geef de namen van de werknemers die meewerken aan alle projecten
waaraan John Smith werkt”. Om deze query met de division-operatie neer te schrijven, doen we
het volgende:
1. We vragen de lijst op van projectnummers waaraan John Smith werkt.
smith ← σ Fname = ‘John’ ∧ Lname = ‘Smith’ (employee)
smith pnos ← π Pno (works on ./ Essn = Ssn smith)
2. We selecteren alle werknemers met alle projecten waar ze aan werken uit works on.
ssn pnos ← π Essn, Pno (works on)
3. We passen de division-operatie toe op de 2 relaties die we net gemaakt hebben.
ssns(Ssn) ← ssn pnos ÷ smith pnos
result ← π Fname, Lname (ssns ∗ employee)
Over het algemeen wordt de division-operatie op twee relaties uitgevoerd: R(Z) ÷ S(X), waarbij
de attributen van R een subset zijn van de attributen van S, dus X ⊆ Z. Als Y de verzameling
attributen van R is die geen attributen zijn van S, dan geldt Y = Z − X en Z = X ∪ Y .
Het resultaat van division is een relatie T (Y ) die het tupel t bevat als de tupels tR in R
voorkomen met tR [Y ] = t en met tR [X] = tS voor elke tupel tS in S.
Simpeler uitgelegd: voor elke tupel t die in het resultaat van division voorkomt, moet elke
waarde in t uit R in combinatie voorkomen met elke tupel in S.
Een voorbeeld om het duidelijk te maken:
PROJECT AF
Student Opdracht
Fred
Database1
Fred
Database2
Fred
Compiler1
Eugene Database1
Eugene Compiler1
Sarah Database1
Sarah Database2
÷
PROJECT
Opdracht
Database1
Database2
41
−→
RESULTAAT
Student
Fred
Sarah
Als we project af ÷ project uitvoeren, behoren enkel de tupels tot het resultaat die voldoen
aan de volgende voorwaarde: de juiste tupels komen voor in project af in combinatie met elke
tupel in project. Dus in het resultaat zullen enkel studenten opgenomen worden die voorkomen
met zowel opdracht “Database1” als “Database2”. Dit zijn Fred en Sarah.
Eugene wordt niet opgenomen omdat hij enkel voorkomt met Database1 en niet Database2.
De division-operatie kan geschreven worden als een combinatie van de operaties {π, ×, −}.
T1 ← πY (R)
T2 ← πY (S × T1 ) − R
T ← T1 − T2
De division-operatie is ingevoerd om met queries te kunnen werken waarin een universele kwantor ∀ voorkomt.
6.3.5
Notation for Query Trees
Hier beschrijven we de interne voorstelling van queries. Deze voorstelling noemen we een query
tree. Deze bevat de relationele algebra operaties die uitgevoerd worden en wordt soms als datastructuur gebruikt om intern queries voor te stellen in een RDBMS.
Een query tree bevat de input-relaties als bladeren van de boom en bevat de operaties als interne
knopen. Een query tree begint onderaan uit te voeren en voert telkens een knoop uit wanneer
zijn kind-knopen uitgevoerd zijn, de uitvoer stopt als de wortel uitgevoerd is. Telkens een knoop
uitgevoerd wordt, wordt deze vervangen door zijn resultaat.
Bijvoorbeeld: “Voor elk project met als locatie ‘Stafford’, geef de projectnumers, het departementsnummer dat het project controleert en de departemensmanager zijn achternaam, adres en
geboortedatum.” Dit stellen we voor met de volgende query:
raw result ← σ Plocation = ‘Stafford’ (project) ./ Dnum = Dnumber (department)
result ← π Pnumber, Dnum, Lname, Address, Bdate raw result ./ Mgr ssn = Ssn (employee)
De query tree die hiermee overeenkomt is figuur 6.9 op pagina 161. De bladeren P , D en E stellen
de 3 relaties project, department en employee voor. De relationele algebra operaties worden
voorgesteld in de interne knopen. Knoop 1 moet uitgevoerd worden v´o´or knoop 2 omdat deze
resultaten van knoop 1 gebruikt.
6.4
Additional Relational Operations
Sommige queries die vaak nodig zijn in commerci¨ele applicaties, kunnen niet voorgesteld worden met
de originele relationele algebra operaties. In deze sectie zullen we bijkomende operaties defini¨eren.
6.4.1
Generalized Projection
De generalized projection operatie breidt de ‘gewone’ projectie-operatie uit door toe te laten dat
er functies van attributen gebruikt worden. De generieke vorm is:
πF1 ,F2 ,...,Fn (R)
Hier zijn F1 , F2 , . . . , Fn functies op de attributen uit de relatie R.
42
Bijvoorbeeld, we hebben de relatie employee(Ssn, Salary, Deduction, Years service) en we willen
de volgende informatie:
Net Salary = Salary − Deduction
Bonus = 2000 × Years service
Tax = 0.25 × Salary
Dit kunnen we voorstellen met de volgende gegeneraliseerde projectie:
report ← ρ (Ssn, Net salary, Bonus, Tax) π Ssn, Salary − Deduction, 2000 × Years service, 0.25 × Salary (employee)
6.4.2
Aggregate Functions and Grouping
Ook queries die nood hebben aan aggregaatfuncties kunnen niet voorgesteld worden met gewone
relationele algebra operaties, bijvoorbeeld het opvragen van het gemiddelde loon van de werknemers.
Het symbool voor de aggregaatoperatie is F (een rare F). Een generieke aggregaatoperatie heeft
de volgende vorm.
<groeperingsattributen> F <functielijst> (R)
De groeperingsattributen is een lijst attributen uit de relatie R, de functielijst bestaat uit paren
(<functie><attribuut>). Hierin stelt <functie> een attribuut uit R voor en <attribuut> is 1 van
de volgende functies: sum, average, maximum, minimum, count.
Om bijvoorbeeld elk departementsnummer, het aantal werknemers in dat departement en hun
gemiddeld loon op te vragen, kunnen we de volgende query gebruiken.
ρ R(Dno, No of employees, Average sal) Dno F count Ssn, average Salary (employee)
In het bovenstaande voorbeeld hebben we direct de resultaten van de aggregaatfuncties count en
average hernoemd, als we dit niet doen krijgen ze de naam “<functie> <attribuut>”. Als we
geen groeperingsattribuut specifi¨eren, worden de functies toegepast op alle tupels in de relatie. Het
resultaat hiervan zal altijd bestaan uit 1 tupel.
De volgende tabel is het resultaat van de voorbeeldquery.
Dno
5
4
1
No of employees
4
3
1
Average sal
33250
31000
55000
De volgende tabel wordt bekomen als we geen rename-operatie uitvoeren op het resultaat
Dno
5
4
1
Count Ssn
4
3
1
Average Salary
33250
31000
55000
De onderstaande tabel krijgen we als we geen groeperingsattribuut meegeven.
No of employees
8
43
Average sal
35125
6.4.3
Recursive Closure Operations
Een ander soort van operaties die niet voorgesteld kunnen worden met gewone relationele algebra
zijn de recursive closure-operaties (recursieve sluiting). Deze operaties worden toegepast op een
recursieve relatie tussen tupels van hetzelfde type.
Bijvoorbeeld: we willen de baas van een werknemer op elk niveau opvragen, dus de baas e0 van
werknemer e, de baas e00 van werknemer e0 enzovoort. Met gewone relationele algebra is het mogelijk
om de bazen van elkaar op te vragen tot op een specifiek niveau door de tabellen een aantal keer te
joinen. Het is echter niet mogelijk om alle bazen op te vragen. Dit type operaties wordt hier niet
beschreven.
6.4.4
OUTER JOIN Operations
Hier zullen we uitbreidingen van de join-operatie bespreken die nodig zijn om bepaalde queries voor
te kunnen stellen. In de voorgaande beschrijvingen van join-operaties moest er telkens voldaan
zijn aan een bepaalde join-conditie. Dit noemen we inner joins, bij deze joins vallen altijd tupels
weg uit het resultaat, namelijk deze die niet voldoen aan de join-conditie.
Bij outer joins worden alle tupels in beide relaties behouden. Deze operaties zijn soms nodig als
toch blijkt dat de hele tabel nodig is, ook als niet alle tupels overeenkomen.
Bijvoorbeeld: we willen een lijst opvragen van alle werknemers en per werknemer de naam van
het departement dat die leidt. Als een werknemer geen departement leidt, wordt de departmenttupel voor die werknemer NULL in het resultaat. Dit is mogelijk als we een left outer joinoperatie gebruiken.
temp ← employee ./ Ssn = Mgr ssn (department)
result ← π Fname, Minit, Lname, Dname (temp)
Deze left outer join-operatie behoudt elke tupel van de linkse relatie in R ./ S. Als er in S
geen tupel voorkomt die overeenkomt met een tupel uit R, wordt deze in het resultaat aangevuld
met NULL-waarden.
Gelijkaardig hebben we ook de right outer join-operatie (./ ) die elke tupel in de rechtse
relatie (dus S) behoudt. Er bestaat ook een full outer join-operatie ( ./ ) die zowel alle tupels
in de eerste als in de tweede relatie behoudt.
6.4.5
The OUTER UNION Operation
De outer union-operatie (∪+ ) is ontwikkeld om de unie te nemen van tupels uit 2 relaties die
overeenkomstige attributen hebben maar niet union-compatible zijn.
Deze operatie neemt de union van tupels in 2 relaties R(X, Y ) en S(X, Z) die gedeeltelijk
compatibel zijn. Dit betekent dat slechts enkele attributen (bijvoorbeeld X) union-compatible
zijn. De union-compatible attributen komen slechts eenmaal voor in het resultaat. De attributen
die niet union-compatible zijn, worden ook behouden in het resultaat T (X, Y, Z).
De outer union-operatie is dus hetzelfde als de full outer join-operatie op de unioncompatible attributen.
Twee tupels t1 in R en t2 in S matchen als t1 [X] = t2 [X]. Deze zullen worden gecombineerd tot
een enkele tupel in t. Tupels in R en S die geen overeenkomstige tupel hebben in de andere relatie,
worden aangevuld met NULL-waarden.
44
Voorbeeld: we hebben 2 relaties met redelijk overeenkomstige schema’s:
student (Name, Ssn, Department, Advisor)
instructor (Name, Ssn, Department, Rank)
Als we de outer union-operatie toepassen op deze 2 relaties krijgen we als resultaat:
student or instructor (Name, Ssn, Department, Advisor, Rank)
Alle tupels uit beide relaties zullen voorkomen in het resultaat, tupels met dezelfde (Name, Ssn,
Department)-combinatie zullen slechts 1 keer voorkomen. Tupels uit de student-relatie zullen
onder het attribuut “Rank” NULL-waarden in het resultaat hebben. Bij tupels uit instructor
zal dit het geval zijn onder “Advisor”. Merk op dat dezelfde persoon nog altijd tweemaal kan
voorkomen in het resultaat als hij ingeschreven is als student ´en als instructor.
Er bestaat ook een inner union-operatie: Q = R ∪− S met Attr(Q) = Attr(R) ∩ Attr(S).
Analoog is outer union gedefinieerd als: Q = R ∪+ S met Attr(Q) = Attr(R) ∪ Attr(S).
6.6
The Tuple Relational Calculus
In deze en de volgende sectie introduceren we een andere, formele querytaal voor het relationele
model: de relational calculus. Er zijn 2 versies: tuple relational calculus (6.6) en domain
relational calculus (6.7). In beide gevallen gaat het om declaratieve expressies, we zeggen dus
niet hoe we aan het resultaat geraken maar wat we willen. Dit verschilt met relationele algebra
waarin een opeenvolging van queries wordt gegeven in een bepaalde volgorde (dus procedural ).
Men heeft aangetoond dat men in de relationele algebra dezelfde queries kan uitvoeren als in de
relationele calculus en vice versa. We zeggen dus dat hun expressive power identiek is.
We noemen een bepaalde querytaal L relationally complete als we in L elke query kunnen
beschrijven die in relationele calculus te schrijven valt.
6.6.1
Tuple Variables and Range Relations
Tupelcalculus is gebaseerd op het specifieren van tupelvariabelen, een tupelvariabele kan als
waarde elke individuele tupel aannemen uit een relatie. Een simpele query in tupelcalculus heeft
de volgende vorm:
t cond(t)
Hierbij is t de tupelvariabele en cond(t) is een Booleaanse expressie waarin t voorkomt. Het
resultaat van zo’n query is de verzameling van alle tupels t waarvoor cond(t) waar is.
Bijvoorbeeld: we vragen alle werknemers op die een loon hebben van meer dan $50000:
t employee(t) AND t.Salary > 50000
De conditie employee(t) zegt dat t moet behoren tot de werknemers. Elke werknemer waarvoor
(t.Salary > 50000) naar true evalueert, zal worden opgenomen in het resultaat.
De bovenstaande query geeft alle attribuutwaarden terug van werknemers die voldoen aan de
conditie. We kunnen ook maar enkele attributen selecteren:
t.Fname, t.Lname employee(t) AND t.Salary > 50000
Voor een query in tupelcalculus hebben we dus de volgende informatie nodig:
• Voor elke tupel t moeten we een range relation R specifi¨eren, dit is een conditie van de vorm
R(t). Als we dit niet doen, zal t waarden aannemen van tupels uit het hele universum.
In het voorbeeld hierboven: employee(t).
45
• Een conditie om enkel bepaalde combinaties van tupels te selecteren.
In het voorbeeld hierboven: t.Salary > 50000.
• De set van attributen die we willen opvragen.
In het voorbeeld hierboven: t.Fname, t.Lname.
6.6.2
Expressions and Formulas in Tuple Relational Calculus
Een generieke expressie in tupelcalculus heeft de volgende vorm:
t1 .Aj , t2 .Ak , . . . , tn .Am cond(t1 , t2 , . . . , tn , tn+1 , tn+2 , . . . , tn+m )
Hierbij zijn t1 , t2 , . . . , tn , tn+1 , . . . , tn+m tupelvariabelen en elke Ai is een attribuut van de relatie
ti . cond is een conditie opgebouwd uit calculus atoms die 1 van de volgende vormen hebben:
• R(ti ) met R de naam van een relatie. Dit atoom duidt de range van ti aan als de relatie met
naam R.
• (ti .A op tj .B) met op een vergelijkingsoperator uit de set {= , < , > , 6 , > , 6= , . . . }.
• (ti .A op c) met c een constante waarde.
Een formule is opgebouwd uit meerdere atomen, gecombineerd met de logische operatoren AND,
OR en NOT.
6.6.3
The Existential and Universal Quantifiers
We voegen nu ook kwantoren toe: de universele kwantor (∀) en de existenti¨
ele kwantor (∃).
Dit zou gekend moeten zijn, indien niet kan je best sectie 6.6.3 op pagina 173-174 lezen.
6.6.4
Sample Queries in Tuple Relational Calculus
We geven 1 voorbeeldquery in tupelcalculus waarin een kwantor gebruikt wordt. Voor andere
voorbeelden bekijk je best sectie 6.6.4 op pagina 174-175.
van alle werknemers die aan ‘Research’ werken.
nWe willen de naam en het adres
t.Fname, t.Lname, t.Address employee(t) AND
o
(∃d) department(d) AND d.Dname = ‘Research’ AND d.Dnumber = t.Dno
6.6.5
Notation for Query Graphs
In deze sectie stellen we een grafische manier voor om queries in relationele calculus voor te stellen.
Deze queries gebruiken geen kwantoren: select-project-join queries. De grafische weergave van
deze queries noemen we een query graph.
Relaties worden voorgesteld met relation nodes die aangeduid worden met enkele cirkels.
Constanten noemen we constant nodes en hebben een dubbele cirkel. Selectie- en join-condities
worden in de grafe voorgesteld als verbindingen (edges) en de attributen die we opvragen zijn
aangeduid in vierkante haakjes boven elke relatie.
Zo’n query graph duidt niet de volgorde aan waarin deze uitgevoerd moeten worden en is dus
een neutralere vorm dan de query tree om een query grafisch weer te geven.
Voor query-optimalisatie wordt meestal een query tree gebruikt omdat het handiger is om te
weten in welke volgorde dingen uitgevoerd moeten worden.
Een voorbeeld van een query graph vind je op pagina 175.
46
6.6.6
Transforming the Universal and Existential Quantifiers
Hier worden de logische regels beschreven om existenti¨ele en universele kwantoren te transformeren
naar elkaar door gebruik te maken van AND, OR en NOT. Als je deze regels niet meer kent, lees
dan even sectie 6.6.6 op pagina 176.
6.6.7
Using the Universal Quantifiers in Queries
Als we universele kwantoren willen gebruiken in een uitdrukking, moeten we op enkele dingen letten.
Neem als voorbeeld dat we alle werknemers uit departement 5 willen selecteren, het is logisch
dat we hierbij een universele kwantor kunnen gebruiken. Om een universele kwantor naar true te
laten evalueren, moet de formule waar zijn voor elk element uit het universum. Maar in onze query
willen we enkel de werknemers uit departement 5.
We kunnen dit oplossen door alle tupels waarin we niet ge¨ınteresseerd zijn, automatisch naar
true te laten evalueren. Dit doen we door de conditie de vorm NOT R(x) OR conditie(x) te
geven als we enkel ge¨ınteresseerd zijn in tupels uit de relatie R. Elke tupel die niet in R voorkomt
zal dus naar true evalueren.
In principe maken we hier een implicatie (∀x) R(x) ⇒ conditie(x) die we
omvormen tot een
disjunctie. In het voorbeeld wordt dit (∀x) department(x) ⇒ x.Dnum = 5 . Deze formule zegt:
“als x een departement is, dan moet het nummer 5 zijn”. Als we deze conditie in tupelcalculus
noteren, krijgen we (∀x) NOT department(x) OR x.Dnum = 5 .
6.6.8
Safe Expressions
We noemen uitdrukkingen die gegarandeerd een eindig aantal tupels teruggeven safe, in het andere
geval unsafe. De volgende query is unsafe omdat er oneindig veel tupels in het universum bestaan
die geen werknemer zijn.
t NOT employee(t)
We kunnen het concept van een safe uitdrukking preciezer defini¨eren aan de hand van het concept
van het domein van een uitdrukking in tupelcalculus. Het domein van het voorgaande voorbeeld is
de set van alle attribuutwaarden die voorkomen in een tupel van de employee-relatie.
Een uitdrukking noemen we veilig als alle waarden in het resultaat uit dit domein komen. Ons
voorbeeld is dus niet veilig omdat er ook tupels in het restultaat voorkomen die niet voorkomen in
employee (eigenlijk komt geen enkele tupel in het resultaat uit employee).
47
6.7
The Domain Relational Calculus
Naast tuple relational calculus hebben we ook domain relational calulus of domeincalculus.
Het verschil tussen domeincalculus en tupel calculus ligt in het type van variabelen die we
gebruiken in de formules. In de domeincalculus laten we de variabelen waarden aannemen uit de
domeinen van attributen in plaats van over tupels.
De generieke vorm van een domain calculus query is de volgende.
x1 , x2 , . . . , xn cond(x1 , x2 , . . . , xn , xn+1 , xn+2 , . . . , xn+m )
Hierbij zijn (x1 , x2 , . . . , xn , xn+1 , xn+2 , . . . , xn+m ) de domeinvariabelen die rangen over domeinen
van attributen, cond is een conditie. Een formule is ook hier opgebouwd uit atomen (die waar of
vals kunnen zijn), hier hebben ze echter een beetje een andere vorm dan in tupel calculus:
• R(x1 , x2 , . . . , xj ) met R de naam van een relatie van graad j. Om alles wat leesbaarder te
maken laten we kommas weg: R(x1 x2 x3 )
• (xi op xj ) met op een vergelijkingsoperator uit de set {= , < , > , 6 , > , 6= , . . . }.
• (xi op c) met c een constante.
Om bijvoorbeeld de geboortedatum en het adres van de werknemer John B. Smith op te vragen,
gebruiken we de volgende uitdrukking
n
u, v (∃q)(∃r)(∃s)(∃t)(∃w)(∃x)(∃y)(∃z)
o
employee(qrstuvwxyz) AND q = ‘John’ AND r = ‘B’ AND s = ‘Smith’
Hiervoor hebben we dus 10 variabelen nodig, 1 om over elk domein van attributen te gaan. Veel
van de gespecifieerde variabelen worden echter niet gebruikt. Bij domeincalculus is het dus nodig
om de volgorde te kennen waarin attributen opgeslagen zijn, vooraleer we ze kunnen opvragen.
Een andere (iets kortere) manier om de voorgaande query neer te schrijven, is het gebruiken van
constanten in de uitdrukking.
u, v employee(‘John’, ‘B’, ‘Smith’, t, u, v, w, x, y, z)
Om de naam en het adres van alle werknemers op te vragen die in het ‘Research’-departement
werken, gebruiken we de volgende uitdrukking.
n
q, s, v (∃z)(∃l)(∃m) employee(qrstuvwxyz) AND
o
department(lmno) AND l = ‘Research’ AND m = z
48
Hoofdstuk 7
Conceptual Data Modeling Using
Entities and Relationships
7.1
Using High-Level Conceptual Data Models for Database Design
1. Requirements collection and analysis. Data- en functievereisten onderzoeken voor gebruikers.
2. Conceptual design. Cre¨eren van het hoogniveau, conceptuele schema van de database.
3. Logical Design. Het maken van een database schema in de vorm van een implementation
data model op basis van het hoogniveau data model. Ook wel data model mapping genoemd.
4. Physical Design. Het daadwerkelijk opzetten van de interne opslagstructuren, bestandsorganisatie, indexen, toeganspaden, ... Hieronder valt ook het ontwikkelen van de applicatieprogramma’s om de databasetransacties te implementeren.
Zie ook figuur 7.1 op pagina 196 voor een diagram van deze fases.
7.3
7.3.1
Entity Types, Entity Sets, Attributes, and Keys
Entities and Attributes
Een entiteit is een ding in de echte wereld met een onafhankelijk bestaan, zij het fysiek of conceptueel. Elke entiteit heeft attributen, eigenschappen die de entiteit omschrijven. Deze attributen
zijn een groot stuk van de data die wordt opgeslagen.
Een attribuut kan verder opgesplitst worden in deelattributen, bijvoorbeeld: het attribuut
“Adres” kan bijvoorbeeld omschreven worden door de deelattributen “Straat”, “Huisnummer”,
“Postcode” en “Gemeente”. Dit noemt men een composite attribute. In het andere geval spreekt
men over een simple attribute.
Een attribuut kan single-valued of multivalued zijn. In het laatste geval is het mogelijk dat
een entiteit voor ´e´en attribuut meerdere waarden heeft (bv. een persoon heeft geen, ´e´en of meerdere
diploma’s).
Een attribuut kan stored zijn, of kan derived (afgeleid) zijn uit andere attributen (bv. de
“Leeftijd” kan afgeleid worden uit de “Geboortedatum”).
Een attribuut kan de waarde NULL hebben, wat wil zeggen dat het attribuut niet in gebruik is
voor een bepaalde entiteit of dat de waarde van het attribuut onbekend is.
49
Bij een combinatie van twee of meer van bovenstaande mogelijkheden spreken we van een complex attribute.
7.3.2
Entity Types, Entity Sets, Keys, and Value Sets
Een entity type is een verzameling van gelijksoortige entiteiten, in een database zullen die meestal
in een tabel per type worden verzameld. Een entity set is een momentopname van zo’n verzameling
in de tijd.
Een key attribute van een entiteitstype is een attribuut dat uniek is voor elke entiteit uit dat
type (bv. het rijksregisternummer van een persoon) en deze entiteit dus onderscheidt.
Een value set is een domein van waarden. Elk attribuut heeft een value set waar het zich aan
houdt, het kan dus enkel waarden uit dat opgelegd domein aannemen.
7.4
7.4.1
Relationship Types, Relationship Sets, Roles & Structural Constraints
Relationship Types, Sets and Instances
Een relatietype tussen n entiteitstypes bepaalt een set van associaties (verbanden) tussen de
entiteiten van deze entiteitstypes. Bijvoorbeeld: bij de twee entiteiten employee en department
kan een relatietype works for bestaan, hierbij werkt een employee dan bij een departement.
7.4.2
Relationship Degree, Role Names, and Recursive Relationships
De relatiegraad van een relatie is het aantal entiteitstypes die deel uitmaken van die relatie. In
het bovenstaande voorbeeld is works for dus van graad 2.
Recursieve relaties zijn relaties waarbij een entiteitstype meerdere keren voorkomt, telkens
in een andere rol. Bijvoorbeeld, supervision bepaalt een relatie tussen 2 employees.
7.4.3
Constraints on Binary Relationship Types
Er zijn 2 structural constraints van een relatietype:
• De kardinaliteitsratio van een binaire relatie bepaalt het maximum aantal relatie-instances
waaraan een entiteit kan deelnemen. Bijvoorbeeld, de kardinaliteitsratio van department
t.o.v. employee is 1:N , wat wil zeggen dat een departement N employees kan hebben, maar
een employee kan maar bij 1 departement werken.
• De deelnamebeperking (participation constraint of minimale kardinaliteit constraint)
bepaalt het minimum aantal relatie-instances waaraan een entiteit kan deelnemen. Elke zijde
van een relatie heeft ofwel een totale participatie, ofwel een parti¨ele participatie.
– Totale participatie: elke entiteit van een entiteitstype moet gerelateerd zijn aan een
entiteit van een ander entiteitstype. Bijvoorbeeld: elke employee moet werken voor een
departement, de participatie van employee in de works for-relatie is dus totaal.
– Parti¨
ele participatie: een deel entiteiten van een entiteitstype moet gerelateerd zijn
aan een ander entiteitstype. Bijvoorbeeld: slechts enkele employees beheren een departement, de participatie van employee in de manages-relatie is dus partieel.
50
7.4.4
Attributes of Relationship Types
Net zoals een entiteit omschreven wordt door attributen, kan ook een relatie attributen bevatten.
Bijvoorbeeld, de relatie works for kan het attribuut “Start date” hebben om aan te geven hoelang
iemand al voor een departement werkt.
7.5
Weak Entity Types
Zwakke entiteitstypes zijn identiek aan normale entiteitstypes met uitzondering dat ze geen key
attribute hebben. Ze hangen altijd af van een relatie omdat die relatie hun betekenis geeft. De
entiteit die een zwakke entiteit identificeert, is de eigenaar van de zwakke entiteit. Er is steeds een
totale participatie in de identificerende relatie.
Bijvoorbeeld, een dependent van een employee heeft geen key attribute maar elke dependent verwijst maar naar 1 bestaande employee.
Een zwak entiteitstype heeft meestal een partial key (discriminator), als er dan meerdere
zwakke entiteiten van eenzelfde eigenaar afhankelijk zijn, kan er gemakkelijk een onderscheid gemaakt worden.
7.7
7.7.1
ER Diagrams, Naming Conventions, and Design Issues
Summary of Notation for ER Diagrams
De notaties van de structuren in ER-diagrammen die hier overlopen zijn, staan op pagina 217.
7.7.2
Proper Naming of Schema Constructs
Voor entiteitstypes gebruiken we namen in het enkelvoud. Bij het opstellen van een database uit
een tekst geldt dat de zelfstandige naamwoorden meestal voor entiteitstypes zijn en de werkwoorden
voor relatietypes.
Entiteitstypes en relatietypes schrijven we volledig in hoofdletters. Attributen beginnen met een
hoofdletter. De namen van rollen zijn volledig in kleine letters.
7.7.3
Design Choices for ER Conceptual Design
Het gebeurt vaak bij het ontwerpen van de database dat een concept eerst als attribuut wordt
toegekend aan 1 entiteitstype, maar dat het uiteindelijk een relatietype wordt omdat het naar een
ander entiteitstype verwijst.
Het kan ook voorkomen dat een attribuut dat bij verschillende entiteitstypes aanwezig is, wordt
vervangen door een onafhankelijk entiteitstype. Het omgekeerde kan ook.
7.7.4
Alternative Notations for ER Diagrams
In plaats van het noteren van structurele constraints m.b.v. de kardinaliteitsratio en participatiebeperkingen (enkele of dubbele lijn), kan je ze ook noteren in de vorm (min,max). Deze waarden geven
dan het minimum en maximum aantal relatie-instances weer waaraan een entiteit moet verbonden
zijn. Als min gelijk is aan 0, is er sprake van parti¨ele participatie, anders totale participatie.
Zie figuur 7.15 op pagina 220 voor een voorbeeld hiervan.
51
7.8
7.8.1
Relationship Types of Degree Higher than Two
Choosing between Binary and Ternary (or Higher-Degree) Relationships
Het is uiteraard mogelijk om relaties te hebben met een graad groter dan 2. Ternaire relaties of
relaties van nog hogere graad komen weliswaar niet vaak voor, omdat het in theorie mogelijk is om
zo’n relatie op te splitsen in relaties van lagere graad. Dan verkrijgen we:
• maak 3 binaire relaties tussen de entiteitstypes van de ternaire relatie.
• maak van de ternaire relatie een zwak entiteitstype, dan zullen alle andere entiteitstypes van
de ternaire relatie een nieuwe, binaire relatie krijgen met het nieuwe, zwakke entiteitstype.
Afhankelijk van de situatie hoeft dit geen zwak entiteitstype te zijn, als er een unieke key kan
worden gevonden die elke entiteit van dit type kan identificeren.
7.8.2
Constraints on Ternary (or Higher-Degree) Relationships
Voor relatietypes van een hogere graad zijn er twee notaties: kardinaliteitsratio of min-max. Elk
heeft zijn eigen constraints. Bij de kardinaliteitsratio gebruiken we M en N om “een aantal”
deelnemers aan de relatie voor te stellen. Bij min-max geven het minimum en maximum aan
hoeveel entiteiten van een entiteitstype mogen deelnemen aan de relatie.
7.9
Subclasses, Superclasses, and Inheritance
Al het voorgaande viel onder het ER model. Dit schema breiden we uit tot EER, ofwel Enhanced
ER. Deze uitbreiding omvat subklassen, superklassen, alsook de daarmee gepaard gaande specialisatie en generalisatie. Ook voeren we overerving in voor attributen en relaties.
Op pagina 225 staat een voorbeeld van hoe dit in een schema genoteerd kan worden.
7.10
Specialization and Generalization in EER
7.10.1
Specialization
Specialisatie is het proces van het aanmaken van subklassen voor een entiteitstype. Het entiteitstype waarvoor subklassen worden gecre¨eerd is dan de superklasse van deze nieuwe subklassen.
Subklassen worden gemaakt om specifiekere attributen te kunnen toekennen aan een stuk van het
superklasse-entiteitstype. Deze worden ook wel lokale attributen genoemd.
Een entiteitstype kan meerdere specialisaties hebben, elk met 1 of meerdere subklassen.
7.10.2
Generalization
Generalisatie is in principe het omgekeerde proces: je groepeert enkele entiteitstypes door enkele
gemeenschappelijke attributen toe te kennen aan een nieuwe superklasse van deze entiteitstypes.
52
7.11
Constraints and Characteristics of Specialization and
Generalization Hierarchies
7.11.1
Constraints on Specialization and Generalization
Bij sommige specialisaties is het mogelijk om precies vast te leggen welke entiteiten in een subklasse terecht moeten komen. Zo’n subklassen heten dan predikaatgedefinieerde subklassen (of
predikaatgedefinieerd). De conditie die dit beslist is het bepalende predikaat.
Als alle subklassen in een specialisatie hun conditie op hetzelfde superklasse-attribuut hebben,
dan heet deze specialisatie een attribuutgedefinieerde specialisatie. Het attribuut heet dan het
bepalende attribuut.
Als de specialisatie bepaald is door andere kenmerken, spreken we van een gebruikersgedefinieerde subklasse.
De constraint disjointness (d) bepaalt dat een entiteit deel kan uitmaken van maximaal 1 subklasse
van een bepaalde specialisatie. Als de entiteiten van een specialisatie niet disjunct moeten zijn,
spreekt men van overlapping (o).
De constraint volledigheid kan totaal of partieel zijn. Bij totale specialisatie moet elke
entiteit van een superklasse ook deel moet uitmaken van minstens ´e´en subklasse ervan, dit wordt
genoteerd met een dubbele lijn. Bij parti¨
ele specialisatie moet dit niet (enkele lijn).
Deze 2 soorten constraints zijn onafhankelijk van elkaar.
7.11.2
Specialization and Generalization Hierarchies and Lattices
Subklassen kunnen nog verder onderverdeeld worden in meerdere subklassen. Hierbij moet een
onderscheid gemaakt worden tussen:
• Een specialisatie-hi¨
erarchie: een subklasse kan maar van 1 superklasse afhangen.
• Een specialisatie-tralie: een subklasse kan van meer dan 1 superklasse afhangen. Men
spreekt ook van een gedeelde subklasse.
Een subklasse erft de attributen van alle directe en indirecte superklassen.
Er wordt ook gesproken van generalisatie-hi¨erarchie en generalisatie-tralie. Deze zijn analoog aan
de specialisatie-varianten.
7.11.3
Utilizing Specialization and Generalization in Refining Conceptual Schemas
Bij het ontwikkelen van een database schema volgens het top-down principe zal er standaard
vertrokken worden vanuit een aantal klassen voor een aantal basis-identiteitstypes. Deze klassen
zullen al naargelang het doel van de database gespecialiseerd worden. Het kan gebeuren dat je merkt
dat een subklasse eigenlijk van meer dan ´e´en superklasse moet afhangen, wat een tralie cre¨eert.
Een tweede manier is het bottom-up principe. Dan begin je met zo specifiek mogelijke klassen te
maken, die je vervolgens naargelang hun doel generaliseert naar superklassen.
53
7.12
Modeling of UNION Types Using Categories in EER
Soms is het nodig om een entiteitstype in een relatie te kunnen voorstellen met meerder superklassen.
Die worden dan gegroepeerd in een unie (u), een subklasse van zo’n unie heet een categorie. Een
entiteit in de subklasse van de categorie behoort dan tot 1 superklasse (uit de unie van superklassen).
Een totale categorie houdt de unie van alle entiteiten in de superklassen bij (dubbele lijn).
Een parti¨
ele categorie houdt een deelverzameling van deze unie bij (enkele lijn).
Vergelijk met een gemeenschappelijke subklasse:
• Een gemeenschappelijke subklasse is een deelverzameling van een doorsnede van superklassen.
• Een entiteit in de subklasse behoort tot elke superklasse.
• Alle attributen van de superklassen worden overge¨erfd naar de subklassen.
7.13
A Sample UNIVERSITY EER Schema, Design Choices, and Formal Definitions
7.13.1
The UNIVERSITY Database Example
Lees het voorbeeld met nogal grote tekening in het boek op pagina’s 239 - 241.
7.13.2
Design Choices for Specialization/Generalization
Er zijn een aantal guidelines die je kan volgen bij het opmaken van een database schema:
• Maak enkel subklassen aan als het van belang is voor de database, anders wordt het schema
onnodig ingewikkeld.
• Subklassen met weinig lokale attributen en geen specifieke relaties kunnen best in hun superklasse gestoken worden. De lokale attributen zet je dan op waarde NULL voor entiteiten die
geen deel uitmaken van de “subklasse”.
Dit kan ook gedaan worden als alle subklassen weinig lokale attributen hebben.
• Unies en categorie¨en moeten worden vermeden tenzij het niet anders kan.
• Het kiezen voor disjunctie/overlapping en totale/parti¨ele constraints hangt af van het doel
van de database. Standaard kiest men voor overlapping en de parti¨ele contraint.
54
7.14
Data Abstraction, Knowledge Representation, & Ontology Concepts
Hier worden 4 abstractieconcepten besproken die worden gebruikt in EER modellen en knowledgerepresentation schema’s. Deze laatste zijn ook een soort database-modellen, maar waarbij wordt
uitgegaan van het goed representeren van reeds gegeven data.
7.14.1
Classification and Instantiation
Classificatie is het onderverdelen van objecten en entiteiten in objectklassen en entiteitstypes, ook
wel het identificeren genoemd.
Instantiatie is net het omgekeerde, namelijk het in het leven roepen van objecten en entiteiten
op basis van reeds gemaakte objectklassen en entiteitstypes.
7.14.2
Identification
Bij identificatie zijn klassen en objecten uniek identificeerbaar door een zogenaamde identifier.
Identificatie is nodig op twee niveau’s: om een onderscheid te maken tussen objecten en klassen, en
om objecten te kunnen identificeren en linken aan hun betekenis in de echte wereld.
7.14.3
Specialization and Generalization
Specialisatie betekent hier het verder onderverdelen van klassen van objecten in meer gespecialiseerde subklassen. Generalisatie is weer net het omgekeerde.
7.14.4
Aggregation and Association
Een aggregatie is een abstract concept om samengestelde objecten te maken uit een aantal componentobjecten. Dit kan bijvoorbeeld zijn: het combineren van attributen uit een aantal objecten
tot 1 aggregaatobject. De objecten moeten weliswaar reeds een zekere afhankelijkheid ten op zichte
van mekaar hebben, bijvoorbeeld van hetzelfde entiteitstype afkomstig zijn.
Een associatie wordt gebruikt om onafhankelijke objecten met mekaar te associ¨eren. Dit wordt
in EER voorgesteld met een relatie.
7.14.5
Ontologies and the Semantic Web
Een populair concept dezer dagen is het semantische web. Veel informatie is opgeslagen in documenten en de bedoeling is om die documenten op een geautomatiseerde manier te leren interpreteren.
Daarvoor moet dus een ontologie opgesteld worden, wat op volgende manieren kan:
• Met een thesaurus (woordenboek) de relatie tussen woorden weergeven die een concept
vormen.
• Een taxonomy beschrijft hoe een aantal concepten met mekaar geassocieerd zijn.
• Een gedetailleerd databaseschema wordt soms als een ontologie beschouwd omdat het concepten (entiteiten en attributen) beschrijft en de relaties ertussen.
• Een logische theorie die gebruik maakt van wiskundige logica om zo concepten te defini¨eren.
55
Hoofdstuk 8
Mapping a Conceptual Design into a
Logical Design
8.1
8.1.1
Relational Database Design using ER-to-Relational
Mapping
ER-to-Relational Mapping Algorithm
Stap 1: Mapping of Regular Entity Types
Voor elk normaal (sterk) entiteitstype E in het ER-schema maak je een relatie S die alle simple
attributes van E bevat. Kies ´e´en van de sleutelattributen van E als de primary key van S. Als er
meerdere sleutelattributen werden ge¨ıdentificeerd werden voor E, dan wordt de informatie die deze
attributen beschrijft, behouden om de secondary (unieke) keys van S te specifi¨eren.
Relaties die gecre¨eerd werden door de mapping van entiteitstypes worden soms entity relations
genoemd omdat elke tupel een entity instance voorstelt.
Stap 2: Mapping of Weak Entity Types
Voor elk zwak entiteitstype W in het ER-schema met als eigenaar een entiteitstype E maak je
een relatie S die alle simple attributes van W bevat. Als extra voeg je de primary key attributes
van de relatie(s) die overeenkomen met die van eigenaar E toe als foreign key attributes van S.
Dit zorgt voor de mapping van de identificerende relatie type van W . De primary key van S is de
combinatie van de primary key(s) van de owner(s) en de parti¨ele key van W .
Als er een weak entity W2 bestaat met als eigenaar ook een weak entity W1 , dan moet je eerst
W1 mappen voor W2 om eerst de primary key te kunnen defini¨eren.
Stap 3: Mapping of Binary 1:1 Relationship Types
Voor elke binary 1:1 relatietype R in het ER-schema identificeer je de relaties S en T die overeenkomen met de entiteitstypes in R. Er zijn drie manieren om dit te doen. De eerste is de handigste
manier en moet gebruikt worden, behalve bij speciale gevallen (zie verder).
• Foreign key approach
Kies ´e´en van de relaties S en neem als foreign key in S de primary key van T . Het is beter
om een entiteitstype te kiezen met totale participatie in R voor de rol van S. Voeg alle
simple attributes van het 1:1 binary relatietype R toe als attributen van S.
Voorbeeld: in department verwijst de foreign key “Mgr ssn” naar “Ssn” van een employee
omdat elk departement een manager heeft. Dit vormt dan het relatietype manages.
56
Het is mogelijk om de primary key van S als foreign key in T de nemen. Maar in het voobeeld
van company zou dan 98% van de foreign keys NULL zijn (zie pagina 273). Ook is het
mogelijk om foreign keys te hebben in S en T , maar dan cre¨eer je redundantie.
• Merged relation approach
Hier voegen we twee entiteitstypes en het relatietype samen in een enkele relatie. Dit is
mogelijk wanneer beide entiteitstypes totale participatie hebben, want dit betekent dat de
twee tabellen telkens exact hetzelfde aantal tupels zal hebben.
• Cross-reference of relationship relation approach
Bij deze methode maken we een derde relatie R met als doel om de primary keys van de
twee relaties S en T te cross-referencen. Deze methode is noodzakelijk voor M:N relaties. De
relatie R noemt men dan een relationship relation of soms ook lookup table. Dit omdat
elke tupel in R een relatie-instance representeert die gerelateerd is aan een koppel van S met
een koppel van T . Het nadeel is dat we hier een extra relatie nodig hebben en we een extra
join-operatie nodig hebben.
Stap 4: Mapping of Binary 1:N Relationship Types
Voor elk normaal, binair 1:N relatietype R identificeer je de relatie S die het participerende entiteitstype aan de N -kant voorstelt. T stelt het entiteitstype aan de 1-kant voor.
Voeg in S een foreign key toe die verwijst naar de primary key van de relatie T . Dit doen we
omdat elke entity instance aan de N -kant gerelateerd wordt aan maximum 1 entity instance van de
1-kant. Voeg alle simple attributes van het 1:N relatietype toe als attributen van S.
In het voorbeeld verwijst de foreign key “Dno” in employee naar de primary key “Dnumber”
van department. Dit moet de relatie works for voorstellen.
Stap 5: Mapping of Binary M:N Relationship Types
Voor elk binary M:N relatietype R cre¨eer je een nieuwe relatie S die R representeert. Neem als
foreign key attributen in S de primary keys van de deelnemende entiteitstypes, de combinatie van
deze foreign keys zal de primary key van S vormen. Voeg ook alle simple attributes van R toe als
attributen van S.
Merk op dat we een M:N relatietype niet kunnen voorstellen door 1 foreign key in ´e´en van de
deelnemende relaties. We moeten dus opnieuw een relationship relation S maken.
Voorbeeld: de foreign keys “Essn” en “Pno” in het works on-relatietype verwijzen naar de primary keys van employee en project. Deze foreign keys vormen de primary key van works on.
Stap 6: Mapping of Multivalued Attributes
Cre¨eer voor elk multivalued attribuut A een nieuwe relatie S met daarin een attribuut dat overeenkomt met A. In S zit ook een verwijssleutel K die het entiteitstype voorstelt dat A als multivalued
attribuut heeft. De primary key van S is de combinatie van A en K.
Voorbeeld: we maken voor het meerwaardig attribuut “Locations” een relatie dept locations
met daarin een foreign key “Dnumber” dat verwijst naar het departement waar “Locations” bijhoort.
Stap 7: Mapping of N -ary Relationship Types
Voor elk n-ary relatietype R (met n > 2) maak je een nieuwe relatie S die R voorstelt. Neem
als foreign key attributes in S de primary keys van de deelnemende entiteitstypes. Voeg ook alle
simple attributes van het n-ary relatietype toe als attributen van S. De primary key van S is de
combinatie van alle foreign keys.
57
8.1.2
Discussion and Summary of Mapping for ER Model Constructs
In een relationeel schema worden relatietypes niet expliciet voorgesteld, ze worden voorgesteld met
twee attributen A en B. E´en hiervan is een primary key, de andere een foreign key (over hetzelfde
domein) in de twee relaties S en T . Twee tupels in S en T zijn gerelateerd als ze beide dezelfde
waarde hebben voor A en B.
Bij de binary 1:1 of 1:N relatietypes is er meestal ´e´en enkele join-operatie nodig. Bij het M:N
relatietype zijn er 2 join-operaties nodig. Verder zijn er voor een n-ary relatietype n join-operaties
nodig om de relatie instances volledig te materialiseren.
ER model
Entiteitstype
1:1 of 1:N relatietype
M:N relatietype
n-ary relatietype
Enkelvoudig attribuut
Samengesteld attribuut
Meerwaardig attribuut
Value set
Key attribuut
8.2
8.2.1
Relationeel model
Entiteitsrelatie
Foreign key (of relationship relation)
Relationship relation en 2 foreign keys
Relationship relation en n foreign keys
Attribuut
Verzameling enkelvoudige attributen
Relatie en een foreign key
Domein
Primaire (of secundaire) sleutel
Mapping EER Model Constructs to Relations
Mapping of Specialization or Generalization
We kunnen een extra stap maken voor het mappen van specialisaties of generalisaties.
Stap 8: Options for Mapping Specialization or Generalization
Zet elke specialisatie met m subklassen {S1 , . . . , Sm } en een superklasse C om tot relatieschema’s.
Hierbij zijn {k, a1 , . . . , an } de attributen van C en is k de primary key. Er zijn meerdere opties.
• Option 8A: Multiple relations — superclass and subclasses
Maak een relatie L voor C met attr(L) = {k, a1 , a2 , . . . , an } en met de primary key PK (L) = k.
Maak ook relaties Li voor elke subklasse Si (met 1 6 i 6 m). Er geldt dan dat PK (Li ) = k
en dat attr(Li ) = {k} ∪ { attr(Si ) }.
Deze optie werkt voor elke specialisatie.
• Option 8B: Multiple relations — subclass relations only
Maak een relatie Li voor elke subklasse Si , met 1 6 i 6 m. Er geldt ook dat PK (Li ) = k en
dat attr(Li ) = { attr(Si ) } ∪ {k, a1 , . . . , an }.
Deze optie werkt enkel voor specialisaties waarvan de subklassen disjunct en totaal zijn (elke
entity in de superklasse moet tot minstens 1 van de subklassen behoren). Bij een niet-totale
specialisatie is er verlies van gegevens. Bij een niet-disjunctie specialisatie is er redundantie.
• Option 8C: Single relation with one type attribute
Maak ´e´en relatie L met attr(L) = {k, a1 , a2 , . . . , an } ∪ { attr(S1 ) } ∪ · · · ∪ { attr(Sm ) } ∪ {t} en
met primary key PK (L) = k. Het attribuut t noemt men een type attribute (of discrimating
attribute) waarvan de waarde aanduidt tot welke subklasse een tupel behoort. Men laat t weg
als de specialisatie predikaatgedefinieerd is.
Deze optie werkt enkel voor specialisaties waarvan de subklasses disjunct zijn. Er is een
gevaar voor veel NULL-waarden als er veel specifieke attributen in de subklassen zitten.
58
• Option 8D: Single relation with multiple type attributes
Maak 1 relatie L met attr(L) = {k, a1 , . . . , an } ∪ {attr(S1 )} ∪ · · · ∪ {attr(Sm )} ∪ {t1 , . . . , tm }
en met primary key PK (L) = k. Elke ti (met 1 6 i 6 m) is een Booleaans attribuut die
aanduidt of een tupel tot een subklasse Si behoort of niet.
Deze optie wordt gebruikt voor specialisaties waarvan de subklasses elkaar overlappen. Ook
hier is er een gevaar voor veel NULL-waarden.
Opties 8A en 8B kunnen multiple-relation options genoemd worden omdat er voor elke subklasse
een nieuwe relatie wordt gemaakt (bij 8A zelfs een nieuwe relatie voor de superklasse).
De opties 8C en 8D worden dan single-relation options genoemd omdat er telkens maar 1
nieuwe relatie wordt gemaakt.
Lees eventueel pagina 279-281, hier worden de opties in detail en met voorbeelden uitgelegd.
8.2.2
Mapping of Shared Subclasses (Multiple Inheritance)
Een gedeelde subklasse is een subklasse die behoort tot meerdere superklassen, er is sprake van
multiple inheritance. Deze superklassen moeten allemaal hetzelfde key-attribuut hebben omdat
we anders de subklasse modelleren als een categorie (union type).
Zie figuur 8.6 op pagina 281 voor een voorbeeld hiervan (met figuur 7.26 op pagina 237).
8.2.3
Mapping of Categories (Union Types)
We voegen een extra stap toe aan de procedure om categorie¨en te kunnen mappen. Een categorie
(of union type) is een subklasse van de unie van twee of meer superklassen. Deze superklassen
kunnen verschillende keys hebben omdat ze behoren tot verschillende entiteitstypes.
Zie figuur 8.7 op pagina 282 voor een voorbeeld hiervan (met figuur 7.26 op pagina 237).
Stap 9: Mapping of Union Types (Categories)
Bij deze stap is het gebuikelijk om een nieuw key-attribuut te maken, genaamd een surrogate key.
We maken een relatie aan die correspondeert met de categorie en voegen alle attributen van de
categorie toe aan deze relatie. De primary key van de relatie is dan de surrogate key. We voegen
ook de surrogate key toe als foreign key in elke relatie die correspondeert met een superklasse van
de categorie. Dit om de overeenkomst in waardes tussen de surrogate key en de primary key van
elke superklasse te specifi¨eren.
Voor een categorie waarbij de superklasses dezelfde key hebben, is een surrogate key niet nodig.
59
Hoofdstuk 12
SQL Application Programming Using C
and Java
12.1
Database Programming: Techniques and Issues
Hoewel de meeste databasesystemen interactive interfaces hebben om direct SQL-commando’s in
uit te voeren, wordt bij de meeste database-interacties toch meestal een applicatieprogramma of
database-applicatie gebruikt.
12.1.1
Approaches to Database Programming
• Embedding database commands in a general-purpose programming language
Database statements zijn ingebouwd in de programmeertaal zelf. Een precompiler of preprocessor zoekt deze dan in de programmacode en vervangt de statements in het programma door
functie-aanroepen naar de DBMS-gegenereerde code. Deze techniek heet embedded SQL.
• Using a library of database functions
Voor een bepaalde programmeertaal bestaat een bibliotheek met functies die toegang verschaffen tot de database. De resultaten van die functie worden dan beschikbaar gesteld aan
het programma in een API (application programming interface).
• Designing a brand-new language
Een volledig nieuwe database-programmeertaal wordt ontwikkeld die compatibel is met het
gegevensmodel en de querytaal. Dit wordt weinig toegepast in de praktijk.
12.1.2
Impedance Mismatch
De term impedance mismatch wordt gebruikt om het probleem aan de duiden tussen het verschil
van de database en de programmeertaal. Voor verschillende programmeertalen moeten bindings
ontworpen worden om de verschillen tussen het gegevensmodel en het model van de programmeertaal
te overbruggen.
Een binding definieert de overeenkomsten van de attribuuttypes (bv. varchar ) met de datatypes
van de programmeertaal (bv. string).
Zo’n binding moet ook het resultaat van een query (verzameling van tupels) aan een datastructuur in het programma koppelen. Omdat een voorstelling in een tabelstructuur in een programmeertaal vaak onmogelijk is, worden de tupels 1 voor 1 geanalyseerd (met een iterator).
Deze problemen worden geminimaliseerd als de programmeertaal hetzelfde model gebruikt als
de database (zoals Oracle’s PL/SQL).
60
12.1.3
Typical Sequence of Interaction in Database Programming
Een client program kan verbinding maken met 1 of meer databaseservers.
1. Het programma opent een connection met de databaseserver (met een adres van de server en
eventueel een loginnaam en een paswoord).
2. Er is interactie tussen het programma en de database: de database levert resultaten van
queries die het programma naar de database stuurt.
3. De verbinding met de database wordt gesloten.
61
Hoofdstuk 13
SQL Web Programming Using C PHP
13.1
A Simple PHP Example
PHP is een general-purpose scripting language, geschreven in C. PHP is vooral goed voor het
aanpassen en manipuleren van tekstpagina’s en dynamische HTML-pagina’s.
PHP loopt op de middle-tier web server waar PHP-commando’s de HTML-files zullen manipuleren om de dynamische pagina’s te maken. De gegenereerde HTML-pagina wordt dan naar de
client tier verzonden. Het DBMS bevindt zich op de bottom-tier database server.
Zie pagina 469-470 voor een voorbeeld van PHP.
13.2
Overview of Basic Features of PHP
13.2.1
PHP Variables, Data Types, and Programming Constructs
In PHP worden namen voor variabelen voorafgegaan met het $-teken. In de naam van een variabele
mogen letters, cijfers en het underscore-teken ( ) voorkomen. De namen zijn case sensitive en het
eerste karakter mag geen cijfer zijn. De waarde die aan een variabele wordt toegekend, bepaalt wat
voor type deze variabele is. Het type kan dus bij een nieuwe toekenning veranderen.
In PHP zijn er veel manieren om strings te processen. Hier volgen de drie meest gebruikte
manieren om strings en tekst uit te drukken.
• Single-quoted strings. Bijvoorbeeld $var = ‘wereld!’.
• Double-quoted strings. Hierin worden variabelen omgezet naar de waarde die ze op dat
moment hebben (bv. ‘‘Hallo $var’’). De herkenning van deze variabele door de interpreter
wordt interpolating variables genoemd. Dit gebeurt niet bij single-quoted strings.
• Here documents. Dit wordt gebruikt om lange teksten toe te kennen aan een variabele.
Men begint met het schrijven van <<<DOCNAME, hierna volgt de eigenlijke tekst die opgeslagen
wordt in een variabele. Het einde van de tekst wordt aangeduid met het codewoord (in dit
geval DOCNAME) op een lege regel. De variabelen worden hier ook ge¨ınterpoleerd.
Single-quoted strings worden gebruikt als er geen variabelen in de string voorkomen, anders worden
double-quoted strings of here documents gebruikt.
Om strings aan elkaar te plakken, wordt de period-operator (.) gebruikt.
In PHP bestaan uiteraard ook integers en floating point getallen, ook de Booleaanse variabele
bestaat. For-lussen, while-lussen en if-statements bestaan ook.
62
13.2.2
PHP Arrays
Arrays zijn belangrijk in PHP omdat ze lijsten van elementen toelaten. Een 1-dimensionale array
kan gebruikt worden voor een lijst van keuzes. Bij 2-dimensionale arrays wordt de eerste dimensie
gebruikt als de rijen van een tabel en de tweede dimensie als de kolommen (attributen) per rij.
Een numerische array associeert een index (startend met 0) met elk element.
$fruit1 = array (‘appel’, ‘banaan’, ‘aardbei’);
Een associatieve array voorziet elementparen (key ⇒ value). Hierbij wordt een element opgeroepen via de key, alle keys moeten dus uniek zijn.
$fruit2 = array (‘F1’ => ‘appel’, ‘F2’ => ‘banaan’, ‘F3’ => ‘aardbei’);
Als er geen keys worden gegeven bij het aanmaken van een array, worden de keys automatisch
numerisch. Beide soorten arrays hebben geen limiet op de grootte. Arrays kunnen doorlopen
worden via een foreach-loop of via een for-loop.
13.2.3
PHP Functions
Het defini¨eren van functies en het oproepen van functies werkt hetzelfde als in Java.
• De argumenten van de functies zijn passed by value. De meegegeven waarden worden dus
‘gekopi¨eerd’ naar de functie-argumenten wanneer de functie wordt opgeroepen.
• Return values van een functie worden achter het keyword return gegeven. Een functie kan
eender welk type variabele teruggeven.
• De regels voor variabelen in PHP zijn analoog aan de regels in andere programmeertalen.
Globale variabelen buiten de functie kunnen niet gebruikt worden in deze functie, tenzij ze
gerefereerd worden met de speciale array $GLOBALS. Bijvoorbeeld $GLOBALS[‘abc’] zal de
waarde opvragen van de globale variabele $abc (gedefinieerd buiten de functie).
13.2.4
PHP Server Variables and Forms
Er zijn een aantal built-in entries in de array $ SERVER die informatie kunnen geven over de server
waar de interpreter op draait. Een aantal van deze entries zijn:
• $ SERVER[‘SERVER NAME’] geeft de website terug waarop de interpreter draait.
• $ SERVER[‘REMOTE ADDRESS’] is het IP-adres van de computer die met de server communiceert (bv. 129.107.61.8).
• $ SERVER[‘REMOTE HOST’] is de websitenaam van de client computer (bv. wiki.wina.be).
• $ SERVER[‘PATH INFO’] is het deel van de URL dat na de slash komt, achteraan de URL.
• $ SERVER[‘QUERY STRING’] geeft de string terug die in de URL achter het vraagteken staat.
In deze string kunnen variabelen en waarden meegegeven worden.
• $ SERVER[‘DOCUMENT ROOT’] is de root directory waar de files op de server staan, deze files
zijn beschikbaar voor client users.
Een andere built-in array is $ POST, deze is ook automatisch globaal. $ POST maakt het mogelijk
voor de programmeur om inputwaarden (gegeven door de user) binnen te krijgen. De keys in deze
array zijn de namen van de inputparameters.
63
13.3
Overview of PHP Database Programming
Er bestaan veel libraries voor PHP met daarin handige functies, deze worden gegroepeerd in PEAR
(PHP Extension and Application Repository). De PEAR DB library geeft functies voor toegang
tot een database, hiermee kunnen verschillende databases worden aangesproken (bv. MySQL).
13.3.1
Connecting to a Database
Om de databasefuncties te kunnen gebruiken, moet eerst de PEAR DB library module ingeladen
worden. Daarna kan men met een database verbinden via $d = DB::connect(‘string’); waarbij
string de informatie over de database voorstelt.
In principe kunnen nu de meeste SQL commando’s doorgegeven worden aan de verbonden
database via de query functie. De functie $q = $d->query(‘query’); neemt een SQL-commando
als string en geeft deze door aan de database voor uitvoering. Als de database iets teruggeeft, wordt
dit resultaat bijgehouden in een query-variabele (in dit voorbeeld $q).
Zie pagina 477-479 voor een duidelijk en uitgewerkt voorbeeld.
13.3.2
Collecting Data from Forms and Inserting Records
Het is gebruikelijk in database-applicaties om informatie te verzamelen met HTML. Bijvoorbeeld,
bij het bestellen van een ticket wordt persoonlijke informatie ingevoerd en dan bijgehouden in een
database record op een database server. Bij zo’n toepassingen wordt de variabele $ POST gebruikt,
hierboven al beschreven.
Omdat er met het INSERT commando ‘slechte’ strings kunnen worden meegegeven, kan men
beter de veiligere placeholders gebruiken (met het ?-symbool).
Zie pagina 479-480 voor een duidelijk en uitgewerkt voorbeeld.
13.3.3
Retrieval Queries from Database Tables
We geven 3 voorbeelden van retrieval queries de resultaten te interpreteren.
• While-loop. Een while-loop overloopt elke rij in het resultaat. De functie $q->fetchrow()
haalt de volgende record in het resultaat binnen. De loop start bij het eerste record.
• Dynamic query. De condities in deze query zijn gebaseerd op wat de user ingeeft, op basis
van deze condities wordt bepaald welke rijen geselecteerd worden. Omdat deze query dus
sterk afhangt van de input gegeven door de user, worden hier best placeholders gebruikt.
• getAll() query. Deze methode geeft een andere manier voor een loop over de rijen van de
query. De functie $q->getAll() geeft alle records van de query terug in 1 enkele variabele.
Een foreach-loop kan gebruikt worden om te itereren over de individuele records.
Zie pagina 480-481 voor een duidelijk en uitgewerkt voorbeeld.
64
Hoofdstuk 14
Database Design Theory: Introduction
to Normalization Using Functional and
Multivalued Dependencies
14.1
Informal Design Guidelines for Relation Schemas
De volgende vier informele richtlijnen kunnen gebruikt worden om de kwaliteit van een relationeel
schema te bepalen.
14.1.1
Imparting Clear Semantics to Attributes in Relations
Wanneer verschillende attributen samen gegroepeerd worden tot een relationeel schema, wordt
ervan uitgegaan dat attributen die bij een relatie horen ook een werkelijke betekenis hebben. De
semantiek van een relatie verwijst naar de betekenis ten gevolge van de interpretatie van attributen
in een tupel. Meestal is een eenvoudig uit te leggen schema ook beter.
Richtlijn 1. Ontwerp een relationeel schema zodat zijn betekenis eenvoudig uit te leggen is. Combineer geen attributen van verschillende entiteits- en relatietypes in een nieuwe relatie.
14.1.2
Redundant Information in Tuples and Update Anomalies
E´en van de doelen van het ontwerpen van een schema is de benodigde opslagplaats voor de relaties
te minimaliseren. Het groeperen van attributen in aparte relaties zorgt voor een verminderd geheugengebruik. Wanneer dit niet zou gebeuren en bijvoorbeeld het resultaat van een natural join van
twee relaties als nieuwe relatie bijgehouden wordt, dan is het te verwachten dat verschillende tupels
overlappende informatie bevatten. Terwijl deze informatie, wanneer ze in aparte relaties beschreven
wordt, slechts ´e´en keer wordt opgeslagen.
Een bijkomend probleem bij het opslaan van natural joins van relaties, is dat deze leiden tot
zogenaamde update anomalies. Laat R de relatie zijn die bekomen wordt uit de natural join van
S en T : R = S ∗ T . Dan kunnen deze anomalie¨en onderverdeeld worden als volgt.
Insertion anomalies. Bij het toevoegen van een tupel s (van relatie S) aan relatie R, moeten
alle attributen van de tupel t uit T waarmee s gejoind werd, gekend zijn en correct ingevoerd
worden. Alleen dan is deze tupel s consistent met de andere tupels uit S die met t gejoind
werden. Als enkele waarden niet gekend zijn, kan men NULL gebruiken.
Als bovendien de primaire sleutel van R deze uit S bevat, is het onmogelijk tupels uit T toe
te voegen die geen overeenkomstige tupel hebben in S.
65
Deletion anomalies. Stel, in R komt een tupel s voor die samenhangt met een bepaalde tupel t,
deze s is de laatste tupel die samenhangt met die tupel t. Als men dan die tupel s verwijdert
(en dus ook t), zijn we alle informatie over die tupel t kwijt.
Modification anomalies. Als men de waarde van een attribuut in een tupel t wijzigt, dan moeten
alle andere tupels in R die t bevatten, ook gewijzigd worden.
Zie de voorbeelden op pagina 491-493.
Richtlijn 2. Ontwerp een relationeel schema op zo’n manier dat er geen toevoeg-, weglaat- of
wijzigingsanomalie¨en aanwezig zijn in de relaties. Moesten deze er toch zijn, vermeld dit dan
duidelijk.
14.1.3
NULL values in Tuples
Wanneer veel attributen samengevoegd worden in 1 relatie, maar als sommige attributen maar
voor enkele tupels een zinvolle waarde hebben, kunnen er veel NULL-waarden in de tabel worden
toegevoegd. Dit kan leiden tot problemen bij onder andere joins en aggregaatfuncties.
Richtlijn 3. Vermijd, voor zover dit mogelijk is, om attributen die vaak NULL-waarden opleveren,
aan relaties toe te voegen.
14.1.4
Generation of Spurious Tuples
Richtlijn 4. Ontwerp een relationeel schema op zo’n manier dat bij het joinen, met gelijkheidscondities op attributen die primaire sleutels of verwijssleutels zijn, geen spurious (onechte)
tupels gecre¨eerd worden. Vermijd relaties die overeenkomstige attributen hebben die geen
primaire sleutel – verwijssleutel verband hebben
14.1.5
Summary and Discussion of Design Guidelines
De vier richtlijnen die besproken werden, laten op een informele manier toe de kwaliteit van een
relationeel schema te garanderen. In de rest van dit hoofdstuk presenteren we formele concepten
om de kwaliteit van individuele relationele schema’s te kunnen bepalen.
14.2
Functional Dependencies
14.2.1
Definition of Functional Dependency
Definitie. Zij R een relatieschema met R = {A1 , A2 , . . . , An } en X en Y attributenverzamelingen
die deelverzamelingen zijn van R.
Een functionele afhankelijkheid X → Y specifieert een restrictie op de mogelijke tupels
die in alle mogelijke extensies r van R kunnen voorkomen.
De restrictie bepaalt dat als er voor 2 tupels t1 en t2 in r geldt dat t1 [X] = t2 [X], dan moet
er ook gelden dat t1 [Y ] = t2 [Y ].
Formeel: X → Y als en slechts als X 6= ∅ en als er in alle mogelijke extensies r van R geldt:
t1 , t2 ∈ r en t1 [X] = t2 [X] =⇒ t1 [Y ] = t2 [Y ].
De attributen in Y hangen dus af van de attributen in X (of ze worden bepaald door de attributen
in X). Anders gezegd: Y is functioneel afhankelijk (FD) van X.
66
Enkele opmerkingen:
• De woorden “in alle mogelijke extensies” hangt af van de betekenis van de relatie. Uit die
betekenis volgen bepaalde restricties waaraan de extensies moeten voldoen.
Een FD is dus een eigenschap van een relationeel schema R, niet een eigenschap van een
bepaalde relatietoestand van R.
• Als X een kandidaatsleutel is van een relatie R, dan geldt X → Y voor elke Y ∈ R. Dit komt
omdat geen 2 tupels in een legale toestand r(R) dezelfde sleutelwaarde mogen hebben.
• Als in R geldt dat X → Y , wil dat niets zeggen over Y → X in R.
Een functionele afhankelijkheid is een eigenschap van de betekenis van de attributen. Ze beschrijft
expliciet bepaalde restricties waaraan een relatie steeds moet voldoen. Men kan functionele afhankelijkheden in schema’s aanduiden met behulp van pijlen.
Als er een functionele afhankelijkheid optreedt in een schema, dan wordt deze vastgelegd door
middel van een restrictie. Op deze manier wordt ervoor gezorgd dat de FD geldt voor alle tupels
in alle extensies van R. Een extensie r(R) is een legale extensie als ze voldoet aan alle functionele
afhankelijkheidsrestricties.
We bespreken 3 basic afleidingsregels, deze zijn correct en volledig.
• FD1 – Reflexiviteitsregel: Y ⊆ X ⇒ X → Y .
• FD2 – Uitbreidingsregel: { X → Y } |= XZ → Y Z.
• FD3 – Transitiviteitsregel: { X → Y , Y → Z } |= X → Z.
Er bestaan ook 3 extra afleidingsregels, deze kunnen bewezen worden met de basic afleidingsregels.
• FD4 – Decompositieregel: { X → Y Z } |= X → Y .
• FD5 – Verenigingssregel: { X → Y , X → Z } |= { X → Y Z }.
• FD6 – Pseudo-transitiviteitsregel: { X → Y , W Y → Z } |= W X → Z.
Uit de betekenis van relaties en attributen leidt men eerst een verzameling functionele afhankelijkheden F af. Met de afleidingsregels kunnen dan alle FD’s gevonden worden die uit F volgen. De
sluiting F + van F is de verzameling van alle FD’s die door F ge¨ımpliceerd worden.
XF + is de sluiting van X ten opzichte van F , met andere woorden: de verzameling van alle
attributen die bepaald zijn door X. Om F + te berekenen, moet men dan voor elke X ∈ F waarvoor
geldt dat X → Y , met de afleidingsregels XF + afleiden.
Een voorbeeld van zo’n sluiting ten opzichte van F : { Ssn }+ = { Ssn , EName }. Merk op dat
X ook meerdere attributen kan bevatten.
Zij E en F verzamelingen FD’s van R.
E wordt overdekt door F a.s.a. E ⊆ F + . Alle FD’s in E volgen dan uit F via de afleidingsregels
en E + ⊆ F + . Om na te gaan of E wordt overdekt door F moet men voor alle X → Y in E de
sluiting XF + bepalen en controleren of Y ⊆ XF + .
E en F zijn equivalent a.s.a. E + = F + .
67
14.3
Normal Forms Based on Primary Keys
14.3.1
Normalization of Relations
Normalisatie van data is een proces waarbij relationele schema’s geanalyseerd worden op basis van
hun functionele afhankelijkheden en primaire sleutels, hierdoor verkrijgt men de gewenste eigenschappen die de redundantie minimaliseren en anomalie¨en beperken. Kortom: normalisatie brengt
een relatie in een bepaalde normaalvorm. Hoe hoger de normaalvorm, des te minder functionele
afhankelijkheden zich kunnen voordoen.
De normalisatieprocedure levert:
• Een formeel model voor het analyseren van relationele schema’s op basis van hun sleutels en
functionele afhankelijkheden.
• Een serie normaalvormtesten die uitgevoerd kunnen worden op individuele relationele schema’s
zodat de relationele database genormaliseerd kan worden tot het gewenste niveau.
Definitie. Een normaalvorm legt bepaalde eisen op aan relaties. De normaalvorm van een relatie is de hoogste normaalvormvoorwaarde waaraan ze voldoet en geeft dus de graad van
normalisatie aan.
De attributenverzameling van een relatieschema SR noteren we met UR , de verzameling afhankelijkheden schrijven we als FR . Er geldt dat SR = <UR , FR >.
Definitie. Een verzameling relatieschema’s δ(SR ) = {SR1 , SR2 , . . . , SRk } is een decompositie van
SR a.s.a. UR = UR1 ∪ UR2 ∪ · · · ∪ URk .
Decompositie is dus het opdelen van relatieschema’s die niet voldoen aan de eisen in relatieschema’s
die wel voldoen aan de eisen. Een goede decompositie van een schema bevat dezelfde informatie
maar bevat geen onnodige relaties. Een goede decompositie is ook effici¨ent te onderhouden.
Definitie. Het normaliseren van een gegevensbank is voor elke relatie in die gegevensbank een
decompositie bepalen zodat alle resulterende relaties in een bepaalde normaalvorm zijn.
De normaalvormen toegepast op afzonderlijke relaties bieden geen voldoende voorwaarde voor een
goed relationeel schema. Er moet nog rekening gehouden worden met eigenschappen van het relationeel schema als een geheel, waaronder hoofdzakelijk de volgende eigenschappen:
• De nonadditive join of lossless join eigenschap garandeert dat, na decompositie van de
relaties, er geen onechte tupels gegenereerd worden bij het joinen van relaties.
• De dependency preservation eigenschap garandeert dat de functionele afhankelijkheden
behouden blijven na decompositie.
14.3.2
Practical Use of Normal Forms
Normalisatie wordt gebruikt bij het ontwerpen van een database om de kwaliteit van het ontwerp
te garanderen. Soms kunnen sommige relaties echter in een lagere normaalvorm gehouden worden
om performantieredenen. Dit komt omdat een hogere normaalvorm een speciaal geval is van de
normaalvorm er net onder.
Alternatieve definitie. Er wordt gesproken van decompositie wanneer de join van twee relaties
in hogere normaalvorm bewaard wordt als een basis relatie, in lagere normaalvorm.
68
14.3.3
Definitions of Keys and Attributes Participating in Keys
Definitie. Een supersleutel K van een relatie R determineert elk attribuut in R.
Anders gezegd: K is een supersleutel van een relatie R met schema SR = <U, F > a.s.a. K ⊆ U
zodat voor geen 2 verschillende tupels t1 en t2 uit een legale extensie geldt dat t1 [K] = t2 [K].
Anders gezegd: K is een supersleutel voor R a.s.a. K ⊆ U en K → U ∈ F + .
Anders gezegd: K is een supersleutel a.s.a. KF+ = U .
Definitie. K is een kandidaatsleutel voor R met schema SR = <U, F > a.s.a. K is een supersleutel voor R en geen enkele echte deelverzameling van K is een supersleutel voor R.
Definitie. Een attribuut A is een sleutelattribuut voor een relatie R met schema SR = <U, F >
a.s.a. er bestaat een sleutel K voor R waarvoor geldt A ∈ K.
Uit de kandidaatsleutels kiest men een primaire sleutel, de andere kandidaatsleutels noemt men
secundaire sleutels. Attributen in de primaire sleutel mogen nooit NULL zijn.
Een relatieschema SR = <U, F > is in de nulde normaalvorm als er geen voorwaarden zijn opgelegd
aan de attributen. De attributen mogen dus samengesteld of meerwaardig zijn.
14.3.4
First Normal Form
Definitie. Een relatieschema SR = <U, F > is in de eerste normaalvorm (1NF) a.s.a. het domein
van elk attribuut van U enkelvoudig is.
Anders gezegd: een attribuut van U mag geen verzamelingen of tupels als waarde hebben.
Als in een relatie toch meerwaardige attributen voorkomen, worden er meerdere tupels voorzien
(redundantie) of wordt er een nieuwe relatie gecre¨eerd met dezelfde sleutel.
Eventuele samengestelde attributen worden opgesplitst in meerdere attributen.
Geneste attributen (meervoudige attributen die samenstellingen zijn) worden op gelijkaardige
manier weggewerkt.
Merk op dat de nieuwe gegevensbank dezelfde informatie bevat als de oorspronkelijke. Er is tevens
geen enkele eis gesteld aan de verzameling van functionele afhankelijkheden F .
14.3.5
Second Normal Form
De tweede normaalvorm is vooral belangrijk als aanloop naar de derde normaalvorm.
Definitie. Zij X → Y .
Y is partieel functioneel afhankelijk van X als er een Z ⊂ X bestaat zodat Z → Y .
Anders is Y volledig functioneel afhankelijk van X.
Anders gezegd: Y is partieel afhankelijk als een attribuut A ∈ X kan verwijderd worden uit
X en er na de verwijdering nog steeds geldt dat X → Y .
Definitie. Een relatieschema SR = <U, F > is in de tweede normaalvorm (2NF) a.s.a. voor geen
enkel niet-sleutelattribuut A van U geldt dat A partieel functioneel afhankelijk is van een
kandidaatsleutel van R.
Anders gezegd: voor elk niet-sleutelattribuut moet de hele primaire sleutel nodig zijn om het
determineren.
69
Testen of een schema voldoet aan 2NF, gebeurt door de functionele afhankelijkheden te testen
waarbij het linkerlid een deel is van de primaire sleutel. Als de primaire sleutel uit 1 enkel attribuut
bestaat, is automatisch voldaan aan de voorwaarde.
Om een relatieschema SR1 = <UR1 , FR1 > van 1NF naar 2NF te brengen, moet voor elk attribuut
A dat partieel functioneel afhankelijk is van een kandidaatsleutel K, het volgende gedaan worden:
1. Zoek een subset K 0 ⊂ K waarvan A volledig functioneel afhankelijk is.
2. Elimineer A uit UR1 .
3. Maak een nieuw relatieschema SR2 met als attributenverzameling UR2 = K 0 ∪ A.
Op die manier blijft alle informatie behouden, er wordt wel een nieuw relatieschema toegevoegd.
14.3.6
Third Normal Form
Definitie. Een functionele afhankelijkheid X → Y in R is een triviale functionele afhankelijkheid
a.s.a. Y ⊆ X.
Definitie. Een functionele afhankelijkheid X → Y is een transitieve functionele afhankelijkheid
a.s.a. er een Z bestaat zodat de volgende 3 voorwaarden voldaan zijn:
1. Z is volledig en niet-triviaal functioneel afhankelijk van X.
2. Z is geen (echte of onechte) deelverzameling van een kandidaatsleutel.
3. Y is niet-triviaal functioneel afhankelijk van Z.
We zeggen dat Y transitief functioneel afhankelijk is van X via Z.
Anders gezegd: X → Y en X → Z → Y .
Definitie. Een 2NF-relatieschema SR = <U, F > is in de derde normaalvorm (3NF) a.s.a. voor
geen enkel niet-sleutelattribuut A van U geldt dat:
A is transitief functioneel afhankelijk van een of andere kandidaatsleutel van R.
Alternatieve definitie. Een 1NF-relatieschema SR = <U, F > is in de derde normaalvorm (3NF)
a.s.a. voor elke niet-triviale functionele afhankelijkheid X → A van F + geldt dat:
A is een sleutelattribuut of X is een supersleutel voor R.
Om een relatieschema SR2 = <UR2 , FR2 > van 2NF naar 3NF te brengen, moet voor elk nietsleutelattribuut A dat transitief functioneel afhankelijk is van een kandidaatsleutel K via Z, het
volgende gedaan worden:
1. Elimineer A uit UR2 .
2. Maak een nieuw relatieschema SR3 met als attributenverzameling UR3 = Z ∪ A.
Een relatieschema voldoet niet aan de algemene definitie van 3NF als:
• een niet-sleutelattribuut een ander niet-sleutelattribuut determineert (transitieve afhankelijkheid).
• een echte deelverzameling van een sleutel in R een niet-sleutelattribuut functioneel determineert (parti¨ele afhankelijkheid).
Zie tabel 14.1 op pagina 509 voor een overzicht van de 3 normaalvormen die we tot nu bespraken.
70
14.4
General Definitions of Second & Third Normal Forms
Het zijn parti¨ele en transitieve afhankelijkheden die leiden tot de update-anomalie¨en die eerder
besproken werden. In het boek werden tot nu toe de parti¨ele en transitieve afhankelijkheden van de
primaire sleutel verboden door 2NF en 3NF. Er wordt echter geen rekening gehouden met eventuele
andere kandidaatsleutels.
In deze samenvatting werd wel al rekening gehouden met de parti¨ele en transitieve afhankelijkheden. 14.4 in het boek mag dus overgeslagen worden als je deze samenvatting strikt volgt. Het
lezen van 14.4 kan echter geen kwaad.
14.5
Boyce-Codd Normal Form
In de derde normaalvorm zijn er nog steeds functionele afhankelijkheden toegestaan binnen de
sleutels zelf. Deze worden weggewerkt in de Boyce-Codd normaalvorm.
Definitie. Een 3NF-relatieschema SR = <U, F > is in de Boyce-Codd normaalvorm a.s.a.
voor geen enkel sleutelattribuut A van U geldt dat:
A is partieel of transitief functioneel afhankelijk van een of andere kandidaatsleutel van R.
Alternatieve definitie. Een 1NF-relatieschema SR = <U, F > is in de Boyce-Codd normaalvorm a.s.a. voor elke niet-triviale functionele afhankelijkheid X → A in F + geldt dat X een
supersleutel is voor R.
Merk op dat deze 2 definities enorm veel lijken op de definities van 3NF, met maar kleine verschillen.
Om van 1NF naar BCNF over te gaan, volg je het pad van 1NF naar 3NF maar houd je rekening
met sleutelattributen.
BCNF werkt alle ongewenste functionele afhankelijkheden weg. Helaas is BCNF niet altijd
bereikbaar zonder andere problemen te cre¨eren. Daarenboven worden sommige functionele afhankelijkheden moeilijker te controleren.
71
Hoofdstuk 15
Database Design Theory: Normalization
Algorithms
15.1
Further Topics in Functional Dependencies: Inference
Rules, Equivalence, and Minimal Cover
15.1.1
Inference Rules for Functional Dependencies
Met F wordt de verzameling van alle gespecifi¨eerde functionele afhankelijkheden in een schema R
aangeduid. De afhankelijkheden die in F zijn opgenomen hebben een duidelijke betekenis. In het
schema R zullen echter nog functionele afhankelijkheden aanwezig zijn die niet in F zitten. Deze
afhankelijkheden kunnen van F afgeleid worden.
Definitie. Formeel wordt de verzameling van alle afhankelijkheden in F en al deze die kunnen
afgeleid worden uit F de sluiting van F genoemd. Aangeduid als F +
Een FD X → Y wordt ge¨ımpliceerd door een verzameling afhankelijkheden F als X → Y geldt
voor elke geldige extensie r van R. Het is te zeggen, als voor een geldige extensie r F geldt, dan
moet ook X → Y gelden. Om F + op te bouwen vanuit F hebben we afleidingsregels nodig, enkele
worden nu besproken. (F |= X → Y duidt aan de X → Y ge¨ımpliceerd wordt door F).
IR1 (Reflexiviteitsregel): Als X ⊇ Y, dan X → Y.
IR2 (Uitbreidingsregel) : {X → Y } |= XZ → Y Z
IR3 (Transitiviteitsregel) : {X → Y, Y → Z} |= X → Z
IR4 (Decompositieregel) : {X → Y Z} |= X → Y
IR5 (Verenigingsregel) : {X → Y, X → Z} |= X → Y Z
IR6 (Pseudo-transitiviteitsregel) : {X → Y, W Y → Z} |= W X → Z
Voor bewijzen van deze stellingen zie pagina (531 in de 6de editie van het handboek).
72
Het is bewezen, door Armstrong, dan de eerste drie afleidingsregels correct en volledig zijn.
Correct houdt in dat alle afhankelijkheden die afgeleid kunnen worden ook werkelijk ge¨ımpliceerd
worden. Volledig houdt in dat alle afhankelijkheden die ge¨ımpliceerd worden ook afgeleid kunnen
worden. Deze regels noemt men de afleidingsregels van Armstrong.
Definitie. Voor elke verzameling attributen X, die voorkomt als linkerlid in een functionele afhankelijkheid uit F, bepalen we de verzameling X + van attributen die functioneel afhankelijk
zijn van X gebaseerd op de afhankelijkheden F. X + noemen we de sluiting van X tov. F.
Voor het algoritme om X + te bepalen, zie pagina (532).
15.1.2
Equivalence of Sets of Functional Dependencies
Definitie. Een verzameling functionele afhankelijkheden F overdekt een andere verzameling afhankelijkheden E als voor elke FD in E ook in F + zit.
Definitie. Twee verzamelingen functionele afhankelijkheden F en E zijn equivalent als E + = F + .
Anders gezegd, elke FD in E kan worden afgeleid uit F en omgekeerd. Nog anders, E en F
zijn equivalent als geldt: F overdekt E en E overdekt F.
Om te kijken of F een verzameling E overdekt, berekenen we X + ten opzichte van F voor elke
X → Y in E en dan te kijken of deze X + Y bevat. Als dit zo is voor elke FD in E, dan wordt E
overdekt door F.
15.1.3
Minimal Sets of Functional Dependencies
Informeel is een minimale overdekking van een verzameling FD’s E een verzameling functionele
afhankelijkheden F waarvoor geldt dat elke afhankelijkheid uit E zit in sluiting F + van F. Hierbij
komt nog dat als een FD uit F verwijdert wordt, dit niet meer zou gelden. We zeggen dat een
verzameling afhankelijkheden F minimaal is als voldaan is aan volgende voorwaarden :
• Elke afhankelijk uit F heeft als rechterlid ´e´en enkel attribuut.
• Geen enkele afhankelijkheid X → A, kan vervangen worden door een afhankelijkheid Y → A,
waar Y een echte deelverzameling is van X. Gebeurt dit toch, dan is de bekomen verzameling
niet equivalent aan F.
• We kunnen geen enkele afhankelijkheid uit F verwijderen en toch nog een verzameling FD’s
uitkomen die equivalent is aan F.
Definitie. Een minimale overdekking van een verzameling functionele afhankelijkheden E is een
minimale verzameling afhankelijkheden die equivalent is aan E. Er bestaat altijd minstens ´e´en
zo’n overdekking. (zie algoritme 15.2 p. 534)
Een algoritme voor het vinden van een sleutel van een relatie, gegeven een verzameling FD’s
staat op pagina 535.
15.2
Properties of Relational Decompositions
Wanneer een relatie R door middel van decompositie opgedeeld wordt in een verzameling van relaties
D = {R1 , R2 , ...Rn } en hierdoor vervangen wordt, dan noemen we D en decompositie van R.
SmHierbij eisen we dat elk attribuut uit R ook vertegenwoordigt wordt in D. Het is te zeggen :
i=1 Ri = R.
73
15.2.1
Dependency Preservation Property of a Decomposition
Definitie. Gegeven een verzameling afhankelijkheden F op R, de projectie van F op Ri , πRi (F )
waar Ri een deelverzameling is van R, is de verzameling afhankelijkheden X → Y in F +
zodat de attributen in X ∪ Y vervat zitten in Ri . We zeggen dat een decompositie D =
{R1 , R2 , ..., Rn } van R afhankelijkheidsbewarend is ten opzichte van F, als de unie van de
projecties van F op elke Ri in D equivalent is aan F.
Bewering 1. Het is altijd mogelijk een decompositie D te vinden die afhankelijkheden bewaard
tov. F en waarbij elke relatie uit D in 3NF is.
15.2.2
Nonadditive (Lossless) Join Property of a Decomposition
Definitie. Een decompositie D van R heeft de lossless (nonadditive) join eigenschap ten opzichte
van een verzameling afhankelijkheden F op R als, voor elke relatie extensie r van R die voldoet
aan F, geldt dat : *(πR1 (r),...πRm (r)) = r, met * de natuurlijke join van alle relaties in D. (π
is hier de PROJECT operatie uit relationele algebra).
De nonadditive join eigenschap zorgt ervoor dat bij er bij een natuurlijke join van relaties geen
onechte tupels ontstaan. Voor een algoritme om te testen of een decompositie lossless is, zie pagina
538-539. (Zie oefenzitting 6 voor uitleg over het algoritme)
15.2.3
Testing Binary Decompositions for the Nonadditive Join Property
Property NJB: Een decomposite D = {R1 , R2 } van R heeft de lossless join eigenschap ten opzichte van een verzameling FD’s F op R als en slechts als
• De FD ((R1 ∩ R2 ) → (R1 − R2 )) in F + zit OF
• De FD ((R1 ∩ R2 ) → (R2 − R1 )) in F + zit.
15.2.4
Successive Nonadditive Join Decompositions
Bewering 2. Als een decompositie D = {R1 , R2 , ..., Rm } van R lossless is tov. F en een decompositie Di = {Q1 , Q2 , ...Qn } van Ri lossless is tov de projectie van F op Ri , dan is de decompositie
D2 = {R1 , R2 , ..., Ri−1 , Q1 , Q2 , ..., Qn , Ri+1 , ..., Rm } ook lossless tov. F.
15.3
Algorithms for Relational Database Schema Design
Er worden 3 belangrijke algoritme aangebracht en uitgelegd in het boek, heel deze sectie is belangrijk
en wordt bijgevolg niet echt samengevat.
15.3.1
Dependency-Preserving Decomposition into 3NF Schemas
Het algoritme dat vermeld werd bij bewering 1 staat uitgelegd op pagina 542 en bespreekt hoe een
relatie kan omgezet worden in een verzameling relaties die de functionele afhankelijkheden bewaren.
Bewering 3. Elk relationeel schema dat door dit algoritme gemaakt wordt is in 3NF
74
15.3.2
Nonadditive Join Decomposition into BCNF Schemas
Een algoritme dat een decompositie van een relationeel schema oplevert die de lossless join eigenschap heeft, wordt besproken op pagina 543 en 544.
15.3.3
Dependency-Preserving and Nonadditive (Lossless) Join Decomposition into 3NF Schemas
Een uitbreiding van het algoritme voor afhankelijkheidsbewarende decompositie zorgt ervoor dat
ook de lossless join eigenschap gegarandeert wordt. (zie p. 544-546)
15.4
About Nulls, Dangling Tuples, and Alternative Relational Designs
15.4.1
Problems with NULL Values and Dangling Tuples
Wanneer de waarde NULL voorkomt in een tupel, bij een attribuut dat gebruikt wordt om de relatie
te joinen met een andere, wordt dit tupel uit die join weggelaten. Dit levert vaak niet het gewenste
effect op en kan verholpen worden door een outer join te gebruiken in plaats van een inner join.
NULLs kunnen ook een effect hebben op functies als SUM en AVERAGE.
Verbonden hieraan is het concept van hangende tupels. Als een relatie te ver wordt opgedeeld
en ´e´en entiteit voorgesteld als samenstelling van verschillende relaties, dan is het mogelijk dat een
tupel dat behoord tot de entiteit, niet behoord tot ´e´en of meer van deze relaties. Wanneer deze
relaties vervolgens gejoined worden om de oorspronkelijke entiteit terug te krijgen verschijnt dit
tupel niet in het resultaat, we noemen dit tupel een (dangling) hangend tupel.
15.4.2
Discussion of Normalization Algorithms and Alternative Relational Designs
Een van de problemen van de normalisatie algoritmes die net besproken werden, is dat telkens alle
functionele afhankelijkheden geleverd moeten worden. Bij het weglaten van zelfs maar ´e´en of twee
afhankelijkheden kan een fout schema gegenereerd worden.
Deze algoritmen zijn ook niet deterministisch, het is te zeggen afhankelijk van de volgorde waarin
afhankelijkheden behandeld worden, kunnen verschillende schemas gemaakt worden. Sommige van
deze mogelijke schemas kunnen minder gewenst zijn dan anderen.
75
Hoofdstuk 16
Database File Organizations: Unordered,
Ordered, and Hashed Files of Records
16.1
Introduction
Er zijn 3 hoofdcategorie¨en in storage hierarchy.
• Primary storage staat rechtstreeks in contact met de CPU en wordt gebruikt voor verwerking en opslag, bv. cache memory (SRAM), main memory (DRAM), flash memory.
• Secondary storage is aan het systeem verbonden voor opslag, bv. magnetische schijven.
• Tertiary storage is verwijderbaar van het systeem en wordt gebruikt voor archivering en
backup, bv. optische media (CD, DVD) of magnetische banden.
16.1.1
Memory Hierarchies and Storage Devices
Als je van boven naar onder gaat in de storage hierarchy, daalt de snelheid (en prijs) en stijgt de
capaciteit. Opslagcapaciteit wordt gemeten in kilo-, mega-, giga-, tera- en petabytes (telkens
stappen van 103 beginnend met 1 Kbyte = 1000 bytes).
Main memory databases hebben al hun gegevens in het hoofdgeheugen (en backup op secundair geheugen). Deze zijn handig voor realtime toepassingen.
Een jukebox (zowel optisch als tape) kan automatisch tertiary storage binnen het systeem
brengen. Dit is belangrijk voor zeer grote archieven.
16.1.2
Storage of Databases
Persistent data blijft bewaard over langere periodes. Transient data bestaat tijdelijk tijdens de
executie van een programma. De meeste databases zijn opgeslagen als persistent data op magnetische schijven omdat databases te groot zijn voor main memory en omdat het goedkoop is.
Volatile storage is een categorie van opslag waaronder main memory valt, er is veel kans op
gegevensverlies (bv. door een stroompanne of een crash van het programma). Daarom worden
databases opgeslagen op nonvolatile storage waaronder secundaire en tertiaire opslag vallen.
Online storage kan op elk moment geraadpleegd worden. Offline storage kan niet op elk moment
geraadpleegd worden omdat het eerst geladen moet worden in het systeem. Dit gebeurt ofwel
automatisch (jukebox ) of handmatig. Offline storage wordt vaak gebruikt bij archivering van data
omdat tape heel goedkoop is en omdat de gegevens niet direct beschikbaar moeten zijn.
76
Bij het physical database design wordt bepaald hoe de organisatie van data wordt georganiseerd.
De data voor een database is opgeslagen als files of records. Als bepaalde data nodig is, wordt
deze van de disk naar main memory gekopieerd om te gebruiken.
Primary file organization bepaalt hoe records fysisch worden opgeslagen en dus hoe ze kunnen
worden aangesproken. Hier zijn meerdere keuzes zoals een heap file (ongesorteerd), een sorted file
(sequentieel), een hashed file of B-trees. Bij sorted files en bij hashed files wordt er gesorteerd of
gehasht op een bepaald veld: de sort key of de hash key.
Secondary organization of auxiliary access structure bepaalt hoe records via andere velden kunnen worden aangesproken, vaak gebeurt dit via indexen.
16.2
Secondary Storage Devices
De inhoud van deze sectie (pagina 569-575) is uitgebreid gezien in de cursussen Besturingssystemen
en SOCS. Het belangrijkste uit deze sectie is dat disks random access storage devices zijn en
dat het dus tijd kost om de juiste block te zoeken. Jaarlijks worden processoren 60% sneller maar
de toegangstijden van geheugen daalt maar met 7% per jaar. Het grote knelpunt bij databasetoepassingen is dus de tijd die nodig is om gegevens op schijven te lokaliseren en te schrijven.
Tapes zijn sequential access storage devices en hebben dus ook trage toegangstijden.
16.3
Buffering of Blocks
Het bufferen van (fysische) blokken van records is slechts effici¨ent indien er meerdere processen
verschillende delen van de database nodig hebben. Terwijl een proces wordt uitgevoerd kan de
buffer voor het andere proces gevuld worden en vice versa. Op deze manier heeft elk proces altijd
data klaar om te verwerken.
16.4
Placing File Records on Disk
16.4.1
Records and Record Types
In een database worden gegevens meestal opgeslagen in records. Elk record is een samenhorende
verzameling van data values of data items die elk tot een bepaald field behoren. Elk field heeft
een data type dat bepaalt welke mogelijke waarden er in dat field kunnen staan en hoe deze moeten
worden gelezen. Een verzameling van field names en de overeenkomstige data types specifi¨eren de
definitie van een record type of record format.
Om grote data-items in een record op te slaan (bv. video), gebruikt men pointers. Deze pointers
verwijzen naar BLOBs (Binary Large OBject) die meestal elders worden opgeslagen.
16.4.2
Files, Fixed-length Records, and Variable-Length Records
Een file in een databasecontext is meestal een opeenvolging van records. Er wordt onderscheid
gemaakt tussen 2 groepen records in files. Fixed-length records hebben allemaal dezelfde lengte
(hetzelfde aantal bytes). Variable-length records hebben verschillende lengtes. De records kunnen om volgende redenen van lengte verschillen:
• De records zijn allemaal van hetzelfde type maar ´e´en of meer velden hebben een variabele
lengte (variable-length fields).
In dit geval is er een separator nodig om de velden binnen een record te onderscheiden.
77
• De records zijn van hetzelfde type maar enkele velden zijn optioneel, niet alle records bevatten
deze optional fields dus.
In dit geval is er field type code nodig die aanduidt of een field in een record voorkomt.
• Repeating field: velden kunnen meerdere waarden hebben.
In dit geval is er een separator nodig die de meerdere waarden onderscheidt en een separator
die het einde van het veld aanduidt.
• Bij een mixed file zijn er verschillende recordtypes.
In dit geval is er een record type code nodig die bepaalt welk type record er behandeld
wordt.
16.4.3
Record Blocking and Spanned versus Unspanned Records
Als B de blokgrootte is en R de grootte van fixed-length records en als B > R, dan vinden we dat
de blocking factor gelijk is aan bfr = bB/Rc (aantal records per blok). Deze blocking factor bfr
kan gebruikt worden om het aantal blokken b te berekenen die nodig zijn voor een file van r records:
b = dr / bfre.
Spanned records worden verspreid over meerdere blokken. Aan het einde van een vol blok staat
dan een pointer naar het blok met het vervolg van het record. Deze techniek wordt gebruikt bij
variable-length records of als R > B. bfr is hier het gemiddeld aantal records per blok.
Unspanned records worden niet verspreid over meerdere blokken, 1 record past altijd volledig
in 1 blok. Hierbij is er vaak overschot aan het einde van een blok als B geen veelvoud van R is:
B − (bfr · R) vrije bytes. Deze techniek wordt gebruikt bij korte, fixed-length records. Elk record
begint dan op een vaste positie in het blok.
16.4.4
Allocating File Blocks on Disk
• Contiguous allocation: opeenvolgende bestandsblokken worden toegewezen aan aaneensluitende fysische blokken. Met 2 buffers kan het bestand snel overlopen worden, het invoegen
van blokken is echter moeilijk.
• Linked allocation: elk bestandsblok bevat een pointer naar het volgende blok. Het volledige
bestand overlopen gaat traag maar het bestand uitbreiden is heel simpel.
• Clustered allocation: clusters van aaneensluitende blokken worden geketend met pointers.
Het bestand kan snel overlopen en simpel uitgebreid worden.
• Indexed allocation: 1 of meer indexblokken bevatten pointers naar de bestandsblokken.
16.4.5
File Headers
De file header van een bestand bevat informatie voor het systeem waarop het bestand staat. Hierin
staat hoe een record eruit ziet, in welke blokken het bestand zich bevindt en de ordening van het
bestand.
Om een record te zoeken, worden meerdere blokken naar buffers geplaatst zodat het main
memory kan zoeken of het record in die blokken zit. Als het adres van een record niet gekend is,
moeten alle blokken van een bestand doorzocht worden om het record te vinden (linear search).
Om deze tijdverspilling tegen te gaan, is het belangrijk om informatie over de positie van records
bij te houden.
78
16.5
Operations on Files
Er zijn 2 soorten operaties op bestanden: retrieval operations (records lokaliseren en inlezen) en
update operations (records aanpassen, invoegen of verwijderen).
Met behulp van een simple selection condition kunnen records gezocht worden, deze worden
aangeboden door het besturingssysteem en zijn heel eenvoudig. Een DBMS moet een ingewikkelde
query omzetten in deze eenvoudige selectiecriteria.
• Open: het bestand wordt voorbereid op lezen en schrijven, 2 buffers worden aangesteld en
de file header wordt opgehaald. De pointer wijst naar het begin van het bestand.
• Close: de buffers worden opgeruimd.
Record-at-a-time operations behandelen 1 record per operatie.
• Reset: zet de file pointer terug naar het begin van het bestand.
• Find (locate): zoek het eerste record dat aan het criterium voldoet, kopieer het blok van
het record naar de buffer, zet de pointer naar dat record (het huidige record).
• Read (get): het huidige record wordt toegekend aan een programmavariabele, soms wordt
de pointer verplaatst (en moet misschien een nieuw blok ingelezen worden).
• FindNext: zoek het volgende record in de file dat aan de conditie voldoet. Laad het blok
van het record naar de buffer, zet de pointer naar dat record (het huidige record).
• Delete: verwijder het huidige record.
• Modify: verander het huidige record (eerst in de buffer, daarna wordt het record naar het
bestand geschreven).
• Insert: laad het juiste blok in de buffer, voeg het record toe aan dat blok en schrijf het blok
weg in het bestand.
Er bestaan ook operaties die andere operaties combineren.
• Scan: Find of FindNext en dan Read.
Set-at-a-time operations behandelt een set van records behandelen per operatie.
• FindAll: lokaliseert alle records die aan de conditie voldoen.
• Find n: lokaliseer n records die aan de conditie voldoen.
• FindOrdered: zoek alle records in een bepaalde volgorde.
• Reorganize: herorganiseer het bestand (bv. sortering).
Bij bestandsverwerking bij databases zijn er enkele belangrijke parameters waarmee rekening moet
worden gehouden. De file activity slaat op het aantal gebruikte records t.o.v. het totaal aantal
records in het bestand. De file volatility slaat op het aantal records dat in een periode veranderd
wordt t.o.v. het totaal aantal records in het bestand. De file turnover slaat op het aantal records
dat in een periode vervangen wordt t.o.v. het totaal aantal records in het bestand. De file growth
slaat op de toename van het aantal records in een bepaalde periode.
79
16.6
Files of Unordered Records (Heap Files)
Records worden in het bestand geplaatst in de orde waarin ze zijn toegevoegd. Een record toevoegen
kan zeer effici¨ent (achteraan toevoegen).
Zoeken in het bestand is ineffici¨ent (lineair). Het verwijderen van een record is ook ineffici¨ent
omdat het record eerst gezocht wordt, het blok naar het geheugen wordt verplaatst, het record
verwijderd wordt en uiteindelijk het blok teruggeschreven wordt.
Bovendien moet er af en toe een reorganization gebeuren om gaten in het bestand op te vullen.
16.7
Files of Ordered Records (Sorted Files)
Records worden fysisch geordend in een file volgens het ordering field. Als men de sleutel van het
record gebruikt om te sorteren noemt dat veld de ordering key voor het bestand.
Zoeken op ordering field is zeer effici¨ent met binary search (log2 b). Zoeken op nonordering
field blijft ineffici¨ent door linear search (b/2). Het invoegen, aanpassen (van het ordering field) en
verwijderen van records levert problemen op. Hieronder worden enkele oplossingen uitgelegd.
• Overflow file (transaction file): er wordt een ongeordend bestand gemaakt waar heel gemakkelijk records aan toegevoegd worden. Er is een periodieke reorganisatie nodig die de overflow
file met het echte bestand samenvoegt.
• Extra ruimte voorzien voor het toevoegen van records verspilt veel ruimte. Na een tijd is
er opnieuw meer ruimte nodig.
• Na elke operatie reorganiseren is ineffici¨ent aangezien dit veel tijd vraagt.
Sorted files worden niet vaak gebruikt in databases. Meestal gebruikt men een indexed-sequential
file met een primary index. Als er gesorteerd wordt op een veld dat geen sleutel is, dan wordt zo’n
bestand een clustered file genoemd.
16.8
Hashing Techniques
Hash files worden gebruikt om zeer snel de locatie van een record te bepalen. De zoekconditie
moet gebaseerd zijn op het hash field van het record. Als dit hash field de sleutel is van het record,
is het de hash key.
Een hash function h beeldt de waarde van het hash field af op het adres van de fysische blok
waarop het record zich bevindt. Een veelgebruikte hashfunctie is h(a) = a mod b, deze wordt vaak
in combinatie met andere berekeningen gebruikt.
16.8.1
Internal Hashing
De gegevens en de hashfunctie worden in het main memory voorgesteld (soms als een hash table).
Een collision komt voor als de hashwaarde van een in te voegen record al bestaat, er moet dan
een nieuwe positie gevonden worden (collision resolution). Dit kan op meerdere manieren.
• Open addressing probeert steeds volgende posities tot een lege positie is gevonden. Dit kan
echter zeer traag worden door het lineair zoeken naar een lege positie.
• Chaining voegt het nieuwe record toe in een overflow location. Op de plaats van de waarde
van de hashfunctie wordt dan een pointer bijgevoegd naar die overflow location.
• Multiple hashing: meerdere hashfuncties worden berekend tot men een lege positie vindt.
80
16.8.2
External Hashing for Disk Files
De gegevens (eventueel ook de hashfunctie) worden opgeslagen in het bestand zelf. Buckets bevatten pointers naar (groepen van opeenvolgende) fysische blokken. Verschillende records hebben
dezelfde hashwaarde als die in hetzelfde fysieke blok zitten. Als buckets volgeraken, worden er
gemeenschappelijke overflow buckets gebruikt.
Bij static hashing wordt er een vaste ruimte gereserveerd voor het bestand. Als het bestand
te groot is, is er verlies van ruimte. Als het bestand te klein is, zal er veel overloop en dus tijdverlies
optreden. Na een tijdje is er ook reorganisatie nodig.
Door het gebruiken van chaining is het moeilijk om een een record te zoeken via een veld dat
niet het sleutelveld is. Het doorlopen van het bestand in sleutelvolgorde is ook eerder traag.
16.8.3
Hashing Techniques That Allow Dynamic File Expansion
Extendible Hashing. Hier wordt gebruik gemaakt van een directory. Dit is een tabel waarin
de bucket van een record wordt bepaald met de eerste d bits (global depth) van de hashwaarde.
Deze bits zijn niet noodzakelijk uniek zodat er eenvoudig uitbreiding mogelijk is.
Voor elke bucket wordt ook de local depth d0 bijgehouden die bepaalt via welk aantal bits de
inhoud van de bucket is samengesteld. Er geldt altijd dat d0 6 d.
Bijvoorbeeld: in een directory (met d = 4) verwijzen de hashwaarden die beginnen met 1000 of
1001 naar dezelfde groep van buckets die beginnen met 100. Deze groep van buckets heeft dan een
lokale diepte d0 = 3. Na doorverwezen te worden naar deze groep buckets, wordt gekeken naar de
andere bits van de hashwaarde om te bepalen in welke bucket de hashwaarde behoort.
Bij overloop van een bucket moet maar 1 bucket in twee buckets gesplitst worden (met telkens
lokale diepte d0 + 1). Als er al geldt dat d0 = d, dan zal de waarde van d met 1 verhoogd worden,
hierdoor wordt de grootte van de directory verdubbeld.
Figuur 16.11 op pagina 595 maakt veel duidelijk.
Dynamic Hashing. Dit lijkt sterk op extendible hashing maar in plaats van een tabel (directory),
wordt een boomstructuur gebruikt. Afhangend van de nde bit van de hashwaarde, wordt op diepte
n bepaald welke wijzer naar de volgende knoop of bucket gekozen moet worden.
Ook hier moeten niet alle niveaus altijd bestaan en worden deze enkel gecre¨eerd indien nodig,
dus bij een volle bucket.
Zie figuur 16.12 op pagina 597.
Linear Hashing. Deze techniek probeert de veranderende grootte op te vangen zonder een extra
structuur. Om dit te bereiken houdt men een reeks hashfuncties en 1 extra variabele n bij.
Initieel is n = 0 en zijn er M buckets (0, 1, . . . , M − 1) met bijhorende initi¨ele hashfunctie
hi (K) = K mod M . Bij de eerste overloop wordt het record in zijn bucket gestopt met chaining.
De records in bucket 0 worden dan herverdeeld over bucket 0 en de nieuwe bucket M volgens
hi+1 (K) = K mod 2M . De waarde n wordt met 1 verhoogd.
Bij de volgende overlopen zullen buckets 1, 2, . . . gesplitst worden. De waarde van n wordt
gebruikt om te bepalen welke buckets al gesplitst zijn. Als hi (K) < N , is de bucket die hoort bij
hi (K) al gesplitst. Je moet dan voor dit record de functie hi+1 (K) gebruiken.
Uiteindelijk zal n = M , dit betekent dat de originele buckets 0, 1, . . . , M − 1 gesplitst zijn. Er
zijn dan 2M buckets, allen met de hashfunctie hi+1 . Op dit moment wordt n op 0 gezet en elke
nieuwe overloop zal leiden tot het gebruik van de hashfunctie hi+2 (K) = K mod 4M .
De file load factor l = r/(d · N ) kan het splitsen van buckets inperken, als l klein wordt, kan
je buckets weer samenvoegen. Hierbij is r het aantal aanwezige records, d de diepte van de buckets
en N het aantal buckets.
81
16.9
Other Primary File Organizations
16.9.1
Files of Mixed Records
In de eerdere secties gingen we telkens uit van hetzelfde type records binnen een file. In een
re¨eel systeem is dit echter zelden het geval aangezien er relaties tussen verschillende types moeten
weergegeven worden. Er zijn verschillende methodes om dit te implementeren.
Logical field references zijn verwijzingen naar een ander record, deze verwijzingen worden
geschreven in het veld dat verwijst naar andere records.
Een andere techniek die gebruikt wordt voor vaak opgevraagde relaties heet physically clustering on disk. Hierbij gaan we binnen een bestand de records clusteren per type.
16.10
Parallelizing Disk Access Using RAID Technology
Dit is gezien in het vak Besturingssystemen. Als je wil, kan je pagina 599-603 lezen.
16.11
New Storage Systems
16.11.1
Storage Area Networks
SANs lossen enkele problemen van de toenemende vraag naar opslagcapaciteit op.
• Flexibel toevoegen van zowel servers als opslagapparaten in een many-to-many model.
• Er zijn grote afstanden overbrugbaar: tot 10 km met fiber optic cables.
• Minder onderbrekingen of storingen bij het toevoegen van nieuwe randapparaten of servers.
Dit kan gerealiseerd worden door een combinatie van extreem snelle verbindingen, hubs en een
ingewikkeld organisatiesysteem binnen een lokaal netwerk van servers en opslagapparaten.
16.11.2
Network-Attached Storage
NAS-systemen bestaan uit NAS heads en standaard opslagmedia. De NAS head werkt als een
interface en kan via standaard data protocols benaderd worden (hoewel het eigenlijk een server is)
over een LAN. Hierdoor kan zeer eenvoudig extra media worden toegevoegd zonder dat de servers
die gebruikmaken van de NAS hier weet van hebben. Ook kan dit NAS-systeem verschillende
RAID-niveaus implementeren.
16.11.3
iSCSI Storage Systems
Internet SCSI (Small Computer System Interface) is een derde methode om opslag van veel
data eenvoudiger te maken. Concreet gebruikt iSCSI het standaard SCSI-protocol om data aan te
spreken, dit protocol wordt ingekapseld in een ander protocol.
Er zijn tegenwoordig 3 veelgebruikte methodes: IP, Fiber Channel over IP (FCIP) en Fiber
Channel over Ethernet (FCoE). De data kan zich zo over het internet (IP), fiber interface (FCIP) of
ethernet (FCoE) verplaatsen. Opnieuw kan zo de storage door een ander systeem beheerd worden en
uitgebreid worden indien nodig. Dit is goedkoper en er kunnen lange afstanden overbrugd worden.
82
Hoofdstuk 17
Database File Indexing Techniques,
B-Trees, and B+-Trees
We gaan ervan uit dat er al een primary access structure bestaat zoals beschreven in het vorig
hoofdstuk. In dit hoofdstuk hebben we het dan over indexes die secondary access paths voorzien
om het zoeken op verschillende criteria te vergemakkelijken. In tegenstelling tot de primary access
structure veranderen deze indices de fysische plaatsing van records of files niet. De indices maken
het zoeken op indexing fields van records gemakkelijker.
17.1
Types of Single-Level Ordered Indexes
Een index op een bestand is een gegevensstructuur die de toegang op dat bestand via een bepaald
veld (het indexing field) effici¨enter maakt. Het laat dus toe effici¨ent te zoeken naar een bepaalde
waarde van dat veld. De index is gesorteerd op dat veld waardoor binary search mogelijk wordt.
Een index kan opgeslagen zijn in het centraal geheugen of in een bestand in het externe geheugen.
17.1.1
Primary Indexes
Een primary index op een bestand is een gegevensstructuur met fixed-length records, fysisch
geordend volgens het eerste veld. Er is 1 index entry voor elk fysisch blok in het bestand:
<K(i), P (i)>. Het eerste veld bevat de ordering key van het eerste record uit dat blok (het anchor
record). Het tweede veld bevat een pointer naar dat blok.
Een primary index is een sparse index: het heeft entries voor sommige zoekwaarden. Een
dense index daarentegen heeft een entry voor elke zoekwaarde.
Het opbouwen van een primary index heeft grote voordelen in het aantal block accesses dat
moet gebeuren voor een zoekopdracht. Als dr / bfre = b (met r het aantal records en b het aantal
blokken), dan zijn er voor een primary index slechts log2 dri / bfri e = log2 (bi ) accesses nodig (met ri
het aantal entries, bfri de blocking factor van de index en bi het aantal blokken van de index).
Een primary index bevat kleinere en minder records dan het gegevensbestand. Het doorlopen van de
index gaat dus sneller dan het doorlopen van het gegevensbestand en er is dus minder schijftoegang
nodig.
Het toevoegen of weglaten van gegevens is echter veel ingewikkelder: we moeten het gegevensbestand en de index aanpassen (de ankerrecords). Overflow blocks zijn een oplossing voor het
toevoegen. Voor het weglaten van gegevens kan men de weggelaten records gewoon markeren. Na
een tijdje is er toch sowieso een reorganisatie nodig.
83
17.1.2
Clustering Indexes
Als een bestand geordend is op een non-key field (dat niet voor elk record uniek is), wordt dat
veld het clustering field genoemd en het gegevensbestand een clustered file. Voor zo’n bestand
kunnen we een clustering index opstellen.
Per unieke waarde van het clustering field is er 1 wijzer naar het blok waarin het eerste record
met die waarde voorkomt. Deze index is ook sparse.
Bij het toevoegen van een record, kan het gebeuren dat records fysisch 1 plaats opschuiven in de
blokken, hierdoor moeten soms ook blokadressen in de index veranderd worden. Dit kan opgelost
worden door aparte fysische blokken te gebruiken voor aparte waarden van het clustering field.
17.1.3
Secondary Indexes
Een secondary index is niet gebaseerd op het veld dat de ordening van het bestand bepaalt maar
wel op een ander veld. De index zelf is wel geordend op dat andere veld. Voor 1 gegevensbestand
kunnen er meerdere secondary indexes bestaan, telkens voor een ander veld.
Er zijn meerdere technieken mogelijk, afhankelijk van de situatie.
• Voor een veld met unieke waardes (secondary key), de index is gesorteerd op dat veld. De
index is tevens dense.
– Index met wijzers naar records: onmiddellijk vindbaar.
– Index met wijzers naar blokken: lineair zoeken binnen het blok.
• Voor een veld met niet-unieke waardes (deze mogen onsorteerbaar zijn).
– Dense index: elk record staat in de index, dubbele waardes zijn toegestaan in de index.
– Index met variable-length records: per unieke waarde een lijst wijzers naar de blokken
waarin de waarde voorkomt.
– Index met per unieke waarde een wijzer naar een blok met daarin wijzers naar de records.
17.2
Multilevel Indexes
Om nog minder block accesses bij elke zoekopdracht te behalen, kunnen we gebruik maken van
multilevel indexes. Dit betekent dat we de index zelf gaan indexeren. Een index kan immers
gezien worden als een geordend bestand waarop een index kan gebouwd worden. Dit kunnen we
blijven herhalen tot de top level index nog maar 1 blok groot is.
De first level index is de index van het geordend gegevensbestand. Dit kan elk type index zijn
zolang de index enkel unieke waardes heeft.
Een indexed sequential file heeft een multilevel primary index op de ordering key.
De blocking factor bfri van de index is even groot voor alle indices en wordt ook wel de fan-out
(fo) van de multilevel index genoemd. Om te berekenen hoeveel levels ernodig zijn als we weten
dat er r1 entries zijn in het eerste level, bestaat de volgende formule: t = logfo (r1 ) .
Bij het doorzoeken van een multilevel index gebeuren er ongeveer logfo (bi ) block accesses als bi
het aantal blocks van de first level index is. Dit is meestal beter dan de log2 (bi ) block accesses die
nodig zijn bij het binair zoeken in de index.
Het verwijderen van records gebeurt door ze te markeren, het toevoegen gebeurt met overloopgebieden. Zo’n overloop werkt vertragend en verkwist ruimte, er is ook af en toe een reorganisatie
nodig. Bij een reorganisatie wordt het hele bestand sequentieel doorlopen en herschreven naar een
nieuw bestand, daarna wordt een nieuwe index gebouwd op dat nieuwe bestand.
84
17.3
Dynamic Multilevel Indexes Using B-trees & B+-Trees
Het maken van indices met een statische structuur geeft vaak problemen bij het toevoegen of
weglaten van records. Elk niveau van de indexboom is fysisch geordend, daarom moet de hele
boom van indices aangepast worden als een record toegevoegd of verwijderd moet worden. Daarom
bekijken we nu indices die met dynamische structuren opgebouwd worden.
17.3.1
Search Trees and B-trees
Een search tree van orde p is een zoekboom met de volgende karakteristieken. Elke node in
de zoekboom bevat maximaal p − 1 zoekwaarden en p pointers naar child nodes. Elke node kan
voorgesteld worden als <P1 , K1 , P2 , K2 , . . . , Pq−1 , Kq−1 , Pq > met q 6 p. Hier is Pi een pointer naar
een child node en Ki een zoekwaarde.
Op de zoekboom moeten de volgende 2 voorwaarden te allen tijde gelden.
1. Binnen elke node geldt: K1 < K2 < · · · < Kq−1

 Ki−1 < X < Ki
X < Ki
2. Voor elke waarde X waarnaar Pi verwijst, geldt:

Ki−1 < X
als 1 < i < q
als i = 1
als i = q
Om nu een bepaalde waarde X te zoeken, volgen we recursief een reeks pointers Pi volgens de
tweede voorwaarde hierboven. Als Kr−1 < X < Kr , moeten we dus verder zoeken via pointer Pr .
Een zoekboom heeft echter enkele problemen als ze niet gebalanceerd is, in dat geval is het
zoeken vaak ineffici¨ent. Door het invoegen of verwijderen van nodes kan er ook veel plaats verspild
worden en zal de zoekboom nog meer ongebalanceerd worden.
Zie figuren 17.8 en 17.9 op pagina 630 voor voorbeelden.
Een oplossing voor deze problemen zijn B-trees. Zo’n zoekboom legt extra vereisten op aan zijn
nodes zodat de B-tree veel beter gebalanceerd is.
Een B-tree van orde p moet voldoen aan de volgende vereisten.
1. Interne nodes hebben < P1 , <K1 , P r1 >, P2 , <K2 , P r2 >, . . . , Pq−1 , <Kq−1 , P rq−1 >, Pq >
als vorm met q 6 p. Een Pi is een tree pointer en een P ri is een data pointer.
2. Binnen elke node geldt K1 < K2 < · · · < Kq−1 .

 Ki−1 < X < Ki
X < Ki
3. Voor elke waarde X waarnaar Pi verwijst, geldt:

Ki−1 < X
4. Elke node heeft hoogstens p tree pointers.
als 1 < i < q
als i = 1
als i = q
5. Elke node (behalve de wortel en de bladeren) heeft minstens dp/2e tree pointers. De wortel
heeft minstens 2 tree pointers (tenzij het de enige node is).
6. Een node met q tree pointers (met q ≤ p) heeft q − 1 zoekwaarden (Ki ).
7. Alle bladeren (leaf nodes) staan op hetzelfde niveau.
Bij het toevoegen van een waarde in een volle node (dus q = p), moet deze node in 2 gesplitst
worden. Bij het verwijderen van een waarde uit een node die half vol zit (dus dp/2e), moet deze
node samengevoegd worden met naburige nodes.
Deze twee operaties moeten af en toe gebeuren om ervoor te zorgen dat de B-tree aan de
vereisten voldoet. Ze kunnen meerdere malen na elkaar worden toegepast ze elders een nieuw
probleem veroorzaken. Als een probleem zich blijft voordoen in de wortel, kan er een nieuw niveau
toegevoegd of verwijderd worden.
85
Bij een willekeurig aantal invoegingen en verwijderingen, zit een B-tree gemiddeld 69% vol. Dit
is een beperkte verspilling van geheugen, een B-tree is ook redelijk gebalanceerd. B-trees worden
gebruikt als primaire bestandsorganisatie, dus van het bestand zelf en niet voor een index. Ze zijn
enkel goed bruikbaar als het bestand weinig records bevat en als deze records klein zijn.
Als er ge¨ındexeerd wordt op een niet-sleutelveld, wijst de data pointer naar een blok met adressen
zoals bij de secondary indexes. Dit zorgt dus voor een extra indirectie.
Een B-tree bevat op niveau i minstens 2 di−1 knopen, dit zijn dus 2 (d − 1) di−1 zoekwaarden
.
(met d = dp/2e). Dit betekent dat de hoogte h van een B-tree bepaald wordt door h 6 logd n+1
2
17.3.2
B+ -Trees
B+ -trees zijn een variatie van B-trees. Bij het doorlopen van een B-tree worden interne knopen
vaak opnieuw gelezen, terwijl ze in het centraal geheugen staan. Bij B+ -trees wordt dit opgelost
door de interne knopen enkel sleutels te laten bijhouden, geen wijzers naar records.
De adressen van records staan dus enkel in de bladeren (leaf nodes). De orde pi van de interne
knopen is hierdoor groter, dit zorgt voor betere prestaties. De orde van de bladeren kan hoger zijn
dan die van de interne knopen.
Voor de interne knopen gelden bijna dezelfde vereisten als bij de B-tree, enkel vereisten 1 en 3
zijn lichtjes anders. Vereiste 7 geldt hier uiteraard niet.
1. Elke interne knoop is van de vorm <P1 , K1 , P2 , K2 , . . . , Pq−1 , Kq−1 , Pq >

 Ki−1 < X 6 Ki
X 6 Ki
3. Voor elke waarde X waarnaar Pi verwijst, geldt:

Ki−1 < X
met q 6 p.
als 1 < i < q
als i = 1
als i = q
Voor de bladeren stellen we de volgende vereisten.
1. Elk blad is van de vorm < <K1 , P r1 >, <K2 , P r2 >, . . . , <Kq−1 , P rq−1 >, Pnext > met q 6 p.
Pnext verwijst naar het volgende blad in de B+ -tree. Hierdoor kan je de bladeren makkelijk in
volgorde doorlopen als een linked list.
2. Binnen elke node geldt K1 6 K2 6 · · · 6 Kq−1 .
3. Elke data pointer P ri wijst naar een record (wiens zoekwaarde gelijk is aan Ki ) of naar een
blok met daarin het record. Als het zoekveld geen sleutelveld is, kan P ri ook wijzen naar een
blok met adressen zoals bij de secondary indexes.
4. Elk blad heeft minstens dp/2e waarden.
5. Alle bladeren staan op hetzelfde niveau.
Om een record met sleutel K toe te voegen aan een B+ -tree, voeg je de sleutel toe aan het blad
waarbij de sleutel hoort. Als het blad al vol is, splits je het blad in 2 kinderen en verdeel je de
elementen over deze kinderen. Je voegt de sleutel toe aan het juiste blad en past de Pnext aan.
Daarna voeg je de laatste waarde (sleutel) van blad 1 toe aan de ouderknoop. Als deze ouderknoop vol is, herhaal je dit proces (maar dan met interne knopen).
Om een record met sleutel K te verwijderen, zoek je het blad met de sleutel en verwijder je de
sleutel daaruit. Als de sleutel in de interne knopen voorkomt, vervang je hem door de waarde er
net links van.
Als er onderloop (te weinig waarden) in een blad is, steel je enkele waarden van een naburig blad
(en pas je de ouderknoop aan). Eventueel kan je ook 2 bladeren samenvoegen. Als er onderloop in
een interne knoop is, kan je de waarden herverdelen of interne knopen samenvoegen.
86
Er bestaan ook B∗ -trees, het enige verschil met een B+ -tree is dat een knoop niet minstens halfvol
moet zijn maar minstens 32 vol. Er wordt dan pas gesplitst als 2 naburige knopen vol zijn.
Bij andere systemen wordt met een fill factor gewerkt die tussen 0.5 en 1.0 ligt. Nog andere
systemen laten toe dat een interne knoop leeg kan worden of hebben een andere beperking voor
interne knopen en bladknopen.
17.4
Indexes on Multiple Keys
We proberen nu op 2 velden (v1 en v2 ) tegelijk te selecteren met condities c1 en c2 . Eerst geven we
2 na¨ıeve oplossingen waarna we betere oplossingen gaan overlopen.
• Als er een index op v1 bestaat, selecteer daaruit de elementen die voldoen aan c1 . Uit die set
van kandidaten neem je dan enkel de records die voldoen aan c2 . Dit werkt uiteraard ook in
de andere richting (als er een index op v2 bestaat).
• Als er indices bestaan voor v1 en voor v2 , maak dan 2 sets die voldoen aan de condities c1 en
c2 . De oplossing wordt dan bepaald door de gemeenschappelijke records uit die 2 sets.
17.4.1
Ordered Index on Multiple Attributes
Als we vaak zoeken naar een combinatie van v1 en v2 , kan men een index maken die als key een
tupel <v1 , v2 > heeft. Hierbij wordt dan eerst op v1 en dan op v2 gesorteerd (in de tupel).
17.4.2
Partitioned Hashing
Als er geen range queries nodig zijn (als we dus enkel op gelijkheid checken), is partitioned
hashing een goede kandidaat. Hierbij wordt elk attribuut apart gehasht waarna de resultaten
van de hashfuncties samengevoegd worden: h(c1 )h(c2 ). De samengevoegde hash wijst dan naar de
bucket met records die aan beide voorwaarden voldoen.
Deze techniek kan ook met meerdere attributen toegepast worden.
Een extra voordeel is dat het ook redelijk gemakkelijk is om op 1 attribuut te selecteren (in dit
voorbeeld het eerste attribuut). Je moet dan namelijk alle buckets afgaan die beginnen met de hash
van de eerste conditie: h(c1 )h(∗).
17.4.3
Grid Files
Grid files zetten de twee attributen uit in een matrix. Per rij wordt er een specifiek interval van
v1 bepaald en per kolom ook een specifiek interval van v2 . Daarna zetten we wijzers naar buckets
op de juiste plaatsen in de matrix. Een wijzer wijst naar een bucket waarin alle records zitten die
behoren tot het interval van die rij (voor v1 ) en behoren tot het interval in die kolom (voor v2 ).
17.5
Other Types of Indexes
17.5.1
Hash Indexes
Zoals besproken in het vorige hoofdstuk, kunnen we ook hash indexes gebruiken als secundary
access structure. Dit werkt analoog aan de besprekingen hierboven, met als enige uitzondering dat
er een ander veld gekozen wordt als indexveld.
87
17.5.2
Bitmap Indexes
Een bitmap index maken gaat als volgt. Per mogelijke waarde van het attribuut maken we een
entry in de bitmap index en overlopen dan alle records in volgorde. Als bij een record de waarde
voor het attribuut gelijk is aan de waarde bij de entry, schrijven we een 1 bij die entry, in het
andere geval een 0. Zo krijgt men per mogelijke waarde (entry) een opeenvolging van bits die voor
elk record zeggen of dat record die waarde bevat.
Deze techniek is enkel effici¨ent als er v´e´el meer records dan mogelijke waarden bestaan. Het
verwijderen van een record zorgt voor overhead maar die kan beperkt worden door een existence
bitmap te maken die bijhoud of een record nog bestaat.
Op dezelfde manier kan voor de bladeren van een B+ -tree ook een bitmap worden gemaakt. Als
bepaalde zoekwaarden heel vaak voorkomen is de lijst met records bij die waarde zeer lang. Daarom
kan het dan dus handig zijn om bij zo’n zoekwaarde een bitmap op te slaan die weergeeft of records
bij die waarde horen.
17.5.3
Function-Based Indexing
In plaats van een index te maken van waarden van een attributen, passen we een functie toe op die
attributen en maken een index op basis van die functiewaarden.
17.6
Some General Issues Concerning Indexing
17.6.1
Logical versus Physical Indexes
Een physical index bevat bij elke verwijzing naar een record het fysische adres van dat record op
de schijf. Dit heeft als nadeel dat als het record wordt verplaatst, men de index moet aanpassen.
Om dit op te lossen wordt er vaak gebruik gemaakt van een logical ndex. Voor elke fysische
plaats van een record, is er in deze index een entry die een zekere code als index key heeft. In de
rest van het systeem wordt dan met de key van de logical index verwezen naar de records.
17.6.2
Discussion
Vaak worden indices dynamisch aangemaakt (dus als het nodig is), daarom wordt een index vaak
een access structure genoemd.
Met indices kan men ook key constraints op een attribuut controleren. Als er een nieuw record
wordt toegevoegd, dan wordt er meteen ook gecheckt of deze constraint geldt en kan het invoegen
worden verworpen.
Duplicaten kunnen voor problemen zorgen in een DBMS daarom wordt er soms aan de primaire sleutel ook het rijnummer van het record toegevoegd. Op die manier is elk record uniek te
identificeren en kunnen duplicaten bovendien makkelijk worden afgehandeld.
Een fully inverted file is een bestand dat op elk attribuut van de records is ge¨ındexeerd.
Virtual Storage Access Method (VSAM) is nog een systeem van IBM dat tegenwoordig
in veel commerci¨ele systemen terug te vinden is.
17.6.3
Column-Based Storage of Relations
Een ander systeem voor een DBMS is column-based storage. Voor sommige toepassingen is dit
veel effici¨enter dan row-based, meestal gebruiken deze toepassingen vooral read-only operaties. Men
kan dan beter indexeren op enkel de nodige informatie (dus met column-based storage).
88
Hoofdstuk 18
Introduction to Query Processing and
Query Optimization Techniques
In dit hoofdstuk worden de technieken uitgelegd die een DBMS gebruikt om een hoogniveau query
te verwerken, optimaliseren en uit te voeren. Een DBMS heeft heel wat onderdelen die met queries
te maken hebben.
De scanner identificeert de query tokens, in SQL zijn dit de keywords, attribuut- en relatienamen. De parser controleert of de query aan de regels van de query syntax voldoet. De validator
controleert of alle attribuut- en relatienamen geldig zijn. Een query tree of query graph is de
inwendige structuur waarin de query wordt bijgehouden.
De execution strategy (of query plan) wordt door het DBMS gebruikt om de resultaten van
de query uit de database te halen. Er zijn meestal meerdere strategie¨en, het proces om een geschikte
uitvoeringsstrategie te zoeken wordt query optimization genoemd. De query optimizer moet
een goede uitvoeringsstrategie kiezen.
De code generator genereert de code om de uitvoeringsstrategie uit te voeren. De runtime
database processor moet de de query code uitvoeren en hiermee de resultaten opvragen.
Op figuur 18.1 op pagina 660 staan de stappen van het verwerken van een query.
18.1
Translating SQL Queries into Relational Algebra
Een SQL query wordt eerst omgezet naar een equivalente extended relational algebra expression en
wordt dan geoptimaliseerd (omdat in SQL de volgorde van bewerkingen minder vastligt).
Meestal wordt een SQL query eerst onderverdeeld in query blocks. Een query block bestaat
uit een enkele select–from–where-uitdrukking. Group by en having zijn ook onderdeel van
de query block als deze voorkomen in de uitdrukking. Geneste SQL queries worden beschouwd als
aparte query blocks.
18.2
Algorithms for External Sorting
Sorteeralgoritmen worden vaak gebruikt bij het verwerken van queries. Ze moeten bijvoorbeeld
gebruikt worden bij een order by-clausule van een SQL query. Andere situaties waarbij sorteeralgoritmen gebruikt worden zijn join, union, intersection en project (om duplicaten te
verwijderen als distinct geslecteerd wordt).
External sorting: sorteeralgoritmes die gebruikt worden bij het sorteren van grote bestanden die
bestaan uit records (op een harde schijf). Voor deze algoritmes wordt de sort-merge strategy
gebruikt: eerst worden kleine subfiles gesorteerd, later worden deze samengevoegd (merge).
89
Er is een buffer space nodig om het sorteren en het mergen uit te voeren. De buffer space in het
main memory is onderdeel van de DBMS-cache. De buffer space is onderverdeeld in individuele
buffers die elk even groot zijn en elk juist 1 disk block kunnen bevatten.
In de sorteerfase worden runs (kleine delen van het bestand die in de buffer space passen) in
de buffer geladen, gesorteerd met een intern sorteeralgoritme en dan weer weggeschreven naar de
schijf als tijdelijk bestand. Dit wordt herhaald tot het volledige bestand is overlopen.
In de mergefase worden de runs samengevoegd in 1 of meer merge passes tot er maar 1
gesorteerd bestand overblijft. Elke merge pass kan bestaan uit verschillende merge steps. De
degree of merging wordt bepaald door het aantal runs dat samengevoegd wordt bij elke merge
step. Tijdens elke merge step is er een buffer nodig voor elke run (deze bevat dan een disk block
van de run). Er is ook nog een extra buffer nodig met het resultaat van de merge step.
Zij b het aantal blokken en nB het aantal vrije buffers, dan heeft het sort-merge algoritme exact
nR = db / nB e runs nodig.
In de mergefase is de degree of merging dM gelijk aan het aantal deelbestanden (runs) die ineens
samengevoegd kunnen worden, dus dM = nB − 1. Het aantal passes is gelijk aan dlogdM nR e. De
mergefase heeft dus een complexiteit van 2 · b · logdM (nR ).
In de sorteerfase wordt elk blok 1 keer ingelezen en 1 keer weggeschreven: 2 · b.
Dit geeft een totale complexiteit van 2 · b + 2 · b · logdM (nR ).
In figuur 18.2 op pagina 664 staat de pseudocode voor het sort-merge algoritme.
18.3
Algorithms for SELECT and JOIN Operations
18.3.1
Implementing the SELECT Operation
Search methods for simple selection
Deze zoekmethodes scannen alle records om records te vinden die aan het selectiecriterium voldoen.
S1 Lineair search (brute force). Doorloop elke record in de file op zoek naar matches.
S2 Binary search. Enkel mogelijk als de conditie een equality comparison (“=”) gebruikt op
een sleutelattribuut waarop het bestand geordend is.
S3 Using a primary index or a hash key. Enkel mogelijk als de conditie een equality
comparison gebruikt op een sleutelattribuut dat een primary index of een hashfunctie heeft.
Dit zoekalgoritme is effectief voor point queries. Er wordt altijd maar 1 record opgehaald.
S4 Using a primary index to retrieve multiple records. Dit wordt gebruikt als de conditie
een ongelijkheid uit {<, 6, >, >} gebruikt en als er gezocht wordt op een sleutelattribuut met
een primary index.
S5 Using a clustering index to retrieve multiple records. Enkel mogelijk als de conditie
een equality comparison gebruikt op een niet-sleutelattribuut dat de ordening bepaalt.
S6 Using a secondary (B+ -tree) index on an equality comparison. Dit geeft 1 record
terug als het indexing field een sleutelattribuut is (met “=”), bij niet-sleutelattributen geeft
het meerdere records terug. De conditie kan bestaan uit {=, <, 6, >, >}.
Index searches: methodes die een index gebruiken, dus S3, S4, S5 en S6.
Range queries: queries waarbij de conditie een vergelijking uit {<, 6, >, >} gebruikt.
90
Search methods for complex selection
Deze zoekalgoritmen zijn bedoeld voor queries met een conjunctieve conditie. Een conjunctieve
conditie bestaat uit simpele deelcondities die zijn samengevoegd met AND.
S7 Conjunctive selection using an individual index. Indien er voor 1 van de simpele deelcondities een van de methodes S2 – S6 bruikbaar is, selecteer dan eerst volgens die deelconditie.
Test hierna voor elk gevonden record de andere deelconditie(s).
S8 Conjunctive selection using a composite index. Dit is enkel mogelijk als er voor 2 of
meer attributen een “=”-deelconditie gebruikt wordt en als er een samengestelde index op die
attributen bestaat.
S9 Conjunctive selection by intersection of record pointers. Mogelijk met secundaire
indexen die recordpointers bevatten (geen blokpointers). Voor elke “=”-conditie op een secundair ge¨ındexeerd attribuut wordt de verzameling van recordpointers opgehaald. Uit de
doorsnede van al die verzamelingen worden enkele records opgehaald. De andere condities
worden dan getest op deze records om zo de records weg te filteren die niet aan de query
voldoen.
Deze methode werkt enkel voor attributen die geen sleutelattribuut zijn. Het grote voordeel
is dat een groot deel van het selectiewerk enkel op indices moet gebeuren.
Selectivy sl of a condition: de verhouding van het aantal records dat aan de conditie voldoen
tegenover het totaal aantal records in het bestand. Schattingen van deze waarden worden soms
bijgehouden in de DBMS en gebruikt door de optimizer.
Als er bij een selectie met een conjunctieve conditie (S7, S8 of S9) meerdere toegangspaden
beschikbaar zijn, moet de conditie met de laagste selectiviteit sl als eerste gekozen worden. Men
kan ook schattingen van sl uit de catalogus gebruiken.
Een selectie met een disjunctieve conditie is moeilijker te optimaliseren, elke deelconditie moet
volledig getest worden. Als een deelconditie geen toegangspad heeft, moet er lineair gezocht worden.
Het gebruiken van indexen voor de andere indexen is dan niet meer zinvol.
18.3.2
Implementing the JOIN Operation
De dure join-operatie kan op verschillende manieren ge¨ımplementeerd worden. De methodes hieronder zijn bedoeld voor een 2-way join (2 bestanden joinen) van de vorm R ./A=B S.
J1 Nested-loop join (or nested-block join). Dit is de brute force manier om een joinoperatie uit te voeren. Voor elk record t in R en voor elk record s in S wordt er gecontroleerd
of er voldaan is aan de join-conditie t[A] = s[B].
Als bestand in de buitenste lus kiest men best het bestand met het kleinste aantal fysische
blokken.
J2 Single-loop join (using an access structure to retrieve the matching records). Voor
1 van de 2 attributen bestaat er een index of hash key, stel attribuut B van S. Ga dan alle
records t in R af en gebruik de index of hash key van s (dus s[B]) als zoekwaarde om snel te
controleren of er voldaan is aan t[A] = s[B].
Als bestand in de buitenste lus kies men best het bestand met een hoge join-selectiefactor zodat
weinig onnodige records opgezocht worden. De join-selectiefactor van R m.b.t. R[A] = S[B]
is het aantal records van S dat gemiddeld overeenkomt met een record van R.
91
J3 Sort-merge join. Als R gesorteerd is volgens A en als S gesorteerd is volgens B, dan is een
join mogelijk door 1 keer A en B lineair te doorlopen. Dit is uiteraard zeer effici¨ent. Als de
bestanden niet geordend zijn, kan men ze best sorteren, dit is nog steeds effici¨ent.
Deze methode is ook mogelijk met secundaire indexen: A en B kunnen in volgorde doorlopen
worden dankzij de index. Het probleem is dat de records zelf verspreid zijn in het bestand, er
moeten dus voortdurend andere blokken ingelezen worden. Dit kan soms ineffici¨ent zijn.
J4 Partition-hash join. A en B worden gehasht volgens dezelfde hashfunctie. Stel R heeft het
kleinste aantal records. Er wordt een nieuw hashbestand aangemaakt en alle records van R
worden gehasht en in buckets geplaatst. Daarna wordt elk record van S overlopen en wordt
er gecontroleerd in welke bucket het record zou komen. In die bucket wordt dan naar de
overeenkomstige records van R gezocht.
In een uitgebreidere versie kan men eerst de bestanden partitioneren met de hashfunctie
zodat men bestanden krijgt die volledig in het intern geheugen passen. Die bestanden worden
dan per 2 aan elkaar gejoind met eender welke join-methode tot alle gejoinde bestanden aan
elkaar hangen. Als men voor het joinen de methode J4 wil gebruiken, moet men een andere
hashfunctie gebruiken.
De hybrid hash-join is een variant van de partition-hash join waarbij een deel van de join-fase
al tijdens de partitiefase gebeurt. E´en van de tijdelijke hashbestanden blijft permanent in het
geheugen, zo worden 2 tijdelijke bestanden uitgespaard.
18.4
Algorithms for PROJECT and Set Operations
Project – Als de attributenlijst van de projectie π<attributenlijst> (R) een sleutel van R bevat, bevat
het resultaat evenveel tupels als R. In het andere geval moeten eventuele dubbels verwijderd worden
door sortering (dubbels komen dan achter elkaar voor) of hashing. In het laatste geval voeg je een
tupel toe aan het resultaat als diens hashwaarde niet voorkomt in de hashtabel
Cartesian product – De operatie om het Carthesisch product te berekenen is zeer duur. Voor
elke combinatie van 2 records moet er namelijk een nieuw record worden aangemaakt. Deze operatie
wordt best vermeden, ze kan het best vervangen worden door equivalente operaties tijdens de
optimalisatie.
Union, intersection en set difference – Deze operaties zijn enkel van toepassing op type
compatible relaties, deze relaties hebben hetzelfde aantal attributen met bovendien dezelfde domeinen voor elk attribuut. Deze operaties worden ge¨ımplementeerd door een aangepaste versie van
het sort-merge algoritme. De 2 relaties worden eerst gesorteerd volgens dezelfde attributen. Hierna
kan elke relatie 1 keer lineair doorlopen worden om het gewenste resultaat te bepalen.
Er kan ook hashing gebruikt worden voor deze operaties. De eerste relatie wordt gehasht naar een
in-memory hashtable van buckets. De records van de andere relatie worden dan 1 voor 1 doorlopen,
de hashwaarde van zo’n record bepaalt dan in welke bucket je moet zoeken naar overeenkomstige
records uit de eerste relatie.
In SQL worden er varianten van de hierboven beschreven methoden gebruikt voor de operaties
op verzamelingen: union all, intersection all en except all.
92
18.5
Implementing Aggregate Operations and
OUTER JOINs
18.5.1
Implementing Aggregate Operations
De aggregatie-operaties min en max kunnen simpel berekend worden als er een dense index
bestaat voor het te controleren attribuut. Het resultaat kan dan uit de index berekend worden. Bij
min wordt telkens de meest linkse pointer in de B + -boom gevolgd, bij max steeds de meest rechtse.
Voor de operaties average, sum en count moet de index wel een dense index zijn, de
bladeren van de boom worden dan doorlopen en het resultaat wordt berekend.
De count(*)-operatie kan ook uit de catalogus gehaald worden, de catalogus houdt namelijk
bij hoeveel records een relatie heeft.
Voor een group by-operatie moeten de aggregatie-operaties apart worden toegepast voor elke
groep. Het partitioneren van het bestand in de juiste groepen kan gedaan worden door de records
eerst te sorteren of te hashen en daarna voor elke groep apart de operatie berekenen. Als er
een clustering index bestaat voor de attributen waarop gegroepeerd moet worden, moet er niet
gesorteerd of gehasht worden.
18.5.2
Implementing OUTER JOINs
Outer joins kunnen berekend worden door 1 van de join-algoritmen aan te passen. Als er
bijvoorbeeld een left outer join berekend moet worden, dan worden niet enkel de records
bijgehouden die een match vormen, maar ook de records van de linkse relatie. De records die niet
matchen worden dan aangevuld met NULL-waarden.
Men kan ook eerst een inner join berekenen en het resultaat aanvullen met de tupels die niet
in de inner join voorkomen (aangevuld met NULL-waarden).
18.6
Combining Operations Using Pipelining
Omdat een query meestal uit meerdere relationele operaties bestaat, zullen er veel tijdelijke bestanden aangemaakt worden voor elke opeenvolgende relationele operatie.
Bij pipelining of stream-based processing worden meerdere operaties in 1 algoritme gecombineerd. Zo wordt het resultaat van operatie 1 niet naar een tijdelijk bestand geschreven maar
wordt het resultaat direct doorgegeven als invoer aan operatie 2. Zo ontstaat er een stroom van
gegevens tussen de operaties (algoritmen): een pijplijn.
18.7
Using Heuristics in Query Optimization
Om de prestaties van het uitvoeren van queries te verbeteren, worden er heuristieken toegepast om
de interne weergave van de query (de query tree) aan te passen. De initial query representation
wordt aangepast met heuristieken tot de optimized query representation, deze komt overeen
met de query excecution strategy. Hiermee wordt een query excecution plan opgesteld die groepen
operaties uitvoert, gebaseerd op de beschikbare toegangspaden.
Een belangrijke heuristieke regel stelt dat select- en project-operaties uitgevoerd moeten
worden voordat de binaire operaties uitgevoerd worden. Dit komt omdat select en project de
grootte van het te controleren bestand sterk verminderen.
93
18.7.1
Notation for Query Trees and Query Graphs
In een query tree worden relaties uit de query voorgesteld als bladeren en operaties als interne
knopen. Bij het uitvoeren van een query wordt een interne knoop uitgevoerd van zodra diens
operanden beschikbaar zijn. De interne knoop wordt dan vervangen door de uitvoer van de operatie.
De uitvoer begint bij de bladeren en eindigt bij de wortel.
Een query graph is een neutralere voorstelling van een query omdat er geen specifieke volgorde
is waarin de operaties moeten worden uitgevoerd. In een query graph worden relaties voorgesteld
als relation nodes (enkele rand). Constante waarden (meestal van de selectiecondities) worden
voorgesteld door constant nodes (dubbele rand). Selectie- en join-condities worden voorgesteld als
edges. Attributen die moeten worden opgevraagd, zijn weergegeven tussen vierkante haakjes.
Uit studies is gebleken dat query trees een betere voorstelling zijn dan query graphs omdat de query
optimizer de volgorde van de operaties moet kunnen weergeven.
Figuur 18.4 op pagina 682 geeft voorbeelden van query trees en een query graph.
18.7.2
Heuristic Optimization of Query Trees
Een query kan door verschillende query trees voorgesteld worden. Al deze query trees worden
equivalent genoemd. De query parser maakt meestal de initial query tree die zelden direct
uitgevoerd wordt. Eerst zal de heuristic query optimizer de tree optimaliseren naar een final
query tree die veel effici¨enter is om uit te voeren.
General transformation rules for relational algebra operations
Hieronder staan enkele algemene regels om transformaties op queries uit te voeren die gebruikt
worden bij het optimaliseren van de query tree.
1. Cascade of σ. Een conjunctieve selectieconditie kan omgezet worden in een cascade (opeenvolging) van individuele σ-operaties.
σc1 ∧ c2 ∧ ... ∧ cn (R) ≡ σc1 (σc2 ( . . . ( σcn (R) ) . . . ) )
2. Commutativity of σ.
σc1 ( σc2 (R) ) ≡ σc2 ( σc1 (R) )
3. Cascade of π. In opeenvolgende projecties moet enkel de laatste projectie behouden worden.
πlist1 (πlist2 ( . . . ( πlistn (R) ) . . . ) ) ≡ πlist1 (R)
4. Commuting σ with π. Dit geldt enkel als het selectiecriterium c enkel slaat op attributen
A1 , A2 , . . . , An uit de projectielijst.
πA1 , A2 , ..., An ( σc (R) ) ≡ σc ( πA1 , A2 , ..., An (R) )
5. Commutativity of ./ (and ×).
R ./c S ≡ S ./c R
R×S ≡S×R
6. Commuting σ with ./ (or ×). Deze regels gelden ook voor ×.
Als c enkel slaat op attributen van R, dan geldt er dat:
σc (R ./ S) = σc (R) ./ S
Als c = c1 ∧ c2 en als c1 en c2 condities zijn die enkel slaan op attributen van R en S, dan
geldt er dat:
σc (R ./ S) = σc1 (R) ./ σc2 (S)
94
7. Commuting π with ./ (or ×). Als alle join-attributen voorkomen in de projectielijst
L = {A1 , . . . , An , B1 , . . . , Bm }, kan de projectie naar binnen geschoven worden.
πL (R ./c S) = ( πA1 , ..., An (R) ) ./c ( πB1 , ..., Bm (S) )
In het andere geval moeten R en S geprojecteerd worden op de join-attributen en de attributen
in de projectielijst. Op het einde moet er dan nogmaals geprojecteerd worden op de gevraagde
attributen. Bijvoorbeeld:
πA (R ./B=C S) ≡ πA ( πA,B (R) ./B=C πA,C (S) )
8. Commutativity of set operations. ∪ en ∩ zijn commutatief, − niet.
9. Associativity of ∪, ∩, ×, and ./. Deze 4 operaties zijn individueel associatief.
10. Commuting σ with set operations. Als θ een operatie uit {∪, ∩, −} voorstelt, geldt er:
σc (R θ S) ≡ σc (R) θ σc (S)
11. The π operation commutes with ∪.
πL (R ∪ S) ≡ πL (R) ∪ πL (S)
12. Converting a (σ, ×) sequence into ./. Dit geldt enkel als de selectieconditie c overeenkomt
met een join-conditie.
σc (R × S) ≡ (R ./c S)
Andere transformaties (zoals de wetten van de Morgan) zijn te vinden in hoofdstukken 4, 5 en 6.
In het algemeen proberen we dus de bladeren en knopen van de query tree te herschikken zodat
de query effici¨enter wordt. We proberen eerst de bewerkingen uit te voeren die de grootte van de
tijdelijke relaties verminderen. Een voorbeeld van een optimalisatie-algoritme met heuristieken zou
er dus als volgt uitzien.
1. Splits complexe selectie-operaties in simpele selecties (meer flexibiliteit bij het herschikken).
2. Schuif selectie-operaties zo ver mogelijk naar beneden (minder relaties).
3. Schuif bladeren waarop een strenge selectie gebeurt, meer naar links (kleinere relaties).
4. Combineer meermaals een Carthesisch product met een selectie-operatie tot een join-operatie.
5. Schuif projecties zo ver mogelijk naar beneden (geen onnodige attributen).
6. Identificeer deelbomen die door 1 algoritme kunnen uitgevoerd worden.
18.7.3
Converting Query Trees into Query Execution Plans
Het uitvoeringsplan wordt voorgesteld als een query tree. Dit plan bevat informatie over de verschillende access methods voor elke relatie en welke algoritmen er gebruikt worden bij het berekenen
van de verschillende operaties.
Bij een materialized evaluation wordt het resultaat van een operatie bewaard als een tijdelijke
relatie, het resultaat wordt dus fysisch gematerialiseerd. Dit is dus het tegenovergestelde van een
pipelined evaluation.
95
18.8
Using Selectivity and Cost Estimates in Query Optimization
Bij compiled queries wordt de optimalisatie gedaan bij het compileren van de query. De strategy
code kan dan direct worden uitgevoerd als het opgeroepen wordt (at runtime).
Als de optimalisatie pas at runtime gebeurt, worden de queries interpreted queries genoemd.
De query optimizer gebruikt niet enkel heuristieken. Het schat ook de kost in voor verschillende
uitvoeringsstrategie¨en. De optimizer moet er wel op toezien dat er niet te veel tijd verloren gaat
bij het inschatten en vergelijken van deze uitvoeringsstrategie¨en.
Cost-based optimalization: er wordt met de traditionele optimalisatietechnieken een oplossing gezocht voor een probleem waarbij de kost om tot die oplossing te komen, is verkleind.
18.8.1
Cost components for Query Execution
1. Het inlezen en wegschrijven van blokken naar het secundair geheugen.
2. Het tijdelijk opslaan van tussenresultaten op het secundair geheugen.
3. Het berekenen van de query in de CPU.
4. Het aantal buffers in het main memory die nodig zijn.
5. De communicatiekosten van het versturen van data tussen de cli¨ent en de server.
Bij grote systemen wordt de nadruk gelegd op het minimaliseren van kosten voor toegang tot het
hulpgeheugen. Bij kleine systemen ligt de nadruk eerder op het verminderen van het rekenwerk.
Bij zeer grote systemen moet er ook rekening gehouden worden met de communicatiekosten.
18.8.2
Catalog Information Used in Cost Functions
Om de kost van een uitvoeringsstrategie te bepalen, moet er bepaalde informatie bijgehouden worden
in de catalog. De volgende eigenschappen worden bijgehouden voor elk bestand: het aantal records
r, de gemiddelde recordlengte R, het aantal bestandsblokken b en de blocking factor bfr.
Er wordt ook bijgehouden op welke manier de bestanden zijn opgesteld (bv. geordend, met een
primary index, . . . ). Als er multilevel indexen gebruikt worden, worden het aantal levels van elk
multilevel index (primary, secondary of clustering) bijgehouden.
Het aantal (d) verschillende waarden dat een attribuut kan hebben en de attribute selectivity
sl (zie 18.3.1) worden ook bijgehouden. Met sl kan een schatting gemaakt worden voor de selection
cardinality s = sl · r van een attribuut. Dit is het gemiddeld aantal records dat voldoet aan een
“=”-selectieconditie op dat attribuut.
De optimizer houdt ook een histogram bij voor attributen waarvan de waarden niet evenwichtig
verdeeld zijn over de records.
18.8.3
Examples of Cost Functions for SELECT
Hieronder staan de functies opgesomd om de kost te bepalen voor de algoritmen uit 18.3.1. De kost
wordt uitgedrukt in het aantal block transfers.
S1 Linear search (brute force) approach. Alle file blocks moeten doorlopen worden, het
aantal block transfers is dan gemiddeld CS1a = b. Als er een “=”-conditie gebruikt wordt op
een sleutelattribuut, is dit gemiddeld CS1b = b/2.
96
S2 Binary search. Er worden ongeveer CS2 = log2 (b) + ds/bfre − 1 file block transfers gedaan.
S3 Using a primary index or hash key to retrieve a single record.
Bij het gebruik van een primary key, haalt het algoritme 1 bestandsblok op per index level
plus nog 1 bestandsblok. Dit geeft dus CS3a = x + 1 blocks met x het aantal index levels.
Bij het gebruik van een hash key, wordt er meestal maar 1 blok opgehaald (voor static en linear
hashing), dus CS3b = 1. Bij extendible hashing (zie 17.8) worden er 2 blokken opgehaald.
S4 Using an ordering index to retrieve multiple records. Als gemiddeld de helft van de
records voldoet aan de conditie, dan is de kost ongeveer CS4 = x + (b/2). Deze schatting kan
sterk verschillen naargelang de verdeling van de waarden voor een bepaald attribuut.
S5 Using an clustering index to retrieve multiple records. Als s de selection cardinality
van het ge¨ındexeerde attribuut is, zullen er ds/bfr e bestandsblokken opgeroepen worden.
Bovendien wordt er ook 1 blok opgehaald voor elk index level. Het totaal aantal opgehaalde
blokken is dan CS5 = x + ds/bfr e.
S6 Using a secondary (B+ -tree) index. Als er een secondary index gebruikt wordt op een
sleutelattribuut, zijn er CS6a = x + 1 bloktoegangen nodig.
Als dit niet voor een sleutelattribuut gebeurt, is het aantal block transfers CS6b = x + 1 + s,
dit is in het slechtste geval waarbij elke record in een aparte blok zit.
Als de operaties {<, 6, >, >} gebruikt worden in de conditie, zal ongeveer de helft van de
first-level index blokken ingelezen worden. Ook de helft van de file records zullen via de index
ingelezen worden. Dit komt dan neer op CS6c = x + (bI1 /2) + (r/2)
S7 Conjunctive selection. De methoden S1 tot en met S6 kunnen hiervoor gebruikt worden.
S8 Conjunctive selection using a composite index. Hiervoor kunnen we de methoden S3a,
S5 of S6b gebruiken, afhankelijk van het type index.
18.8.4
Examples of Cost Functions for JOIN
Om een idee te krijgen van de kost van een join-operatie, wordt er meestal geschat hoeveel records er
zullen zijn na een join-operatie. Deze waarde wordt meestal als de join selectivity js bijgehouden.
Dit is de verhouding van het aantal tupels na een join-operatie tegenover het aantal tupels na een
berekening van het Carthesisch product, kortom:
sl =
|R ./c S|
|R ./c S|
=
|R × S|
|R| · |S|
Als er geen join-conditie c is, geldt er dat sl = 1. In dit geval is de join hetzelfde als het berekenen
van het Carthesisch product.
18.8.5
Multiple Relation Queries and JOIN Ordening
Een left-deep tree is een binaire boom waarin het rechtse kind van elke inwendige knoop altijd
een base relation is. Deze bomen worden gebruikt voor queries met veel join-operaties.
De optimizer kan niet van alle mogelijke query trees voor queries met veel join-operaties, de
kosten inschatten. Dit zou namelijk te veel tijd in beslag nemen. De structuur van de query tree
wordt dan beperkt tot dat van een left-deep tree. Het aantal mogelijke query trees is dan veel
kleiner. De optimizer neemt de left-deep tree met de laagste kost.
Een voorbeeld van een left-deep tree vind je op figuur 18.7 op pagina 698.
97
18.8.6
Example to Illustrate Cost-Based Query Optimization
Op pagina 699-701 wordt er een voorbeeld gegeven om de theorie te illustreren.
18.9
Overview of Query Optimization in Oracle
De Oracle DBMS kent 2 verschillende query optimalisatietechnieken:
• De rule-based optimalisatietechniek kiest een uitvoeringsplan gebaseerd op operaties die
geordend zijn op heuristiek.
• Bij de cost-based optimalisatietechniek kiest de optimizer het toegangspad met de laagste
kost.
De Oracle query optimizer kan ook hints van de gebruiker gebruiken bij de optimalisatie van queries.
18.10
Semantic Query Optimization
Bij deze techniek worden de constraints gebruikt die toegepast worden op het databaseschema.
Indien er bijvoorbeeld gezocht wordt naar werknemers die meer verdienen dan hun baas, kan de
optimizer zien dat er een constraint is die dit voorkomt. Het zou dus niet zinvol zijn om deze query
uit te voeren omdat er toch geen oplossingen zijn. Een nadeel bij deze methode is dat het doorlopen
van alle constraints veel tijd in beslag kan nemen.
98
Hoofdstuk 20
Foundations of Database Transaction
Processing
Een transactie is de uitvoering van een programma dat de database raadpleegt of wijzigt.
Transaction processing systems zijn systemen van grote databases met honderden gebruikers
die gelijktijdig transacties uitvoeren. Zo’n database moet altijd beschikbaar zijn en moet een snelle
responstijd hebben voor alle gebruikers.
20.1
Introduction to Transaction Processing
20.1.1
Single-User versus Multiuser Systems
Een DBMS is single-user als slechts 1 gebruiker per keer het systeem kan gebruiken, meestal op
persoonlijke computers.
Een DBMS is multiuser als meerdere gebruikers het systeem gelijktijdig kunnen gebruiken, dit
is mogelijk dankzij multiprogramming (het OS voert meerdere processen tegelijk uit).
Bij interleaved processing behandelt 1 processor afwisselend verschillende transacties, dit
model gebruiken wij. Bij parallel processing werken meerdere processoren in parallel.
20.1.2
Transactions, Database Items, Read and Write Operations,
and DBMS Buffers
Een transactie is een uitvoerend programma dat een logische eenheid vormt. Het bevat 1 of meerdere
database operaties: insertion, deletion, modification of retrieval.
Een read-only transaction is een transactie die de database niet verandert. In het andere
geval praat men over een read-write transaction (of update transaction).
We bespreken het database model bij transaction processing. De database wordt voorgesteld
als een verzameling van named data items. Een data item kan een record, een disk block of de
waarde van een attribuut van een record zijn. De granularity stelt de grootte van een data item
voor. Elk data item heeft een unieke naam om de data items van elkaar te onderscheiden.
Een transactie kan bestaan uit de volgende basic database operaties.
• read item(X) leest een data item X in en stopt deze in een variabele (meestal ook X).
1. Vind het adres van het fysisch blok dat item X bevat.
2. Kopieer dat blok naar een buffer in main memory (als het er nog niet in zit).
3. Kopieer item X van de buffer naar een programma variabele.
99
• write item(X) schrijft de waarde van een variabele X weg naar een database item X.
1. Vind het adres van het fysisch blok dat item X bevat.
2. Kopieer dat blok naar een buffer in main memory (als het er nog niet in zit).
3. Kopieer de programma variabele X naar de juiste plaats in de buffer.
4. Schrijf het aangepaste blok terug op de schijf (onmiddellijk of later).
Het DBMS houdt een buffer cache bij waarin enkele data buffers zitten. De data buffers zitten in
het main memory en houden elk een database disk block bij. Hierin zitten een aantal database items
die verwerkt worden. Buffers worden vervangen volgens een bepaalde buffer replacement policy.
De read-set van een transactie is de verzameling van alle items die gelezen worden. Items die
weggeschreven worden behoren tot de write-set van een operatie.
20.1.3
Why Concurrency Control Is Needed
Er kunnen verschillende problemen optreden bij het gelijktijdig uitvoeren van transacties.
• The Lost Update Problem. Een database item wordt door meerdere transacties tegelijkertijd gelezen en aangepast waardoor de waarde van het data item niet meer klopt.
• The Temporary Update (or Dirty Read) Problem. Transactie T1 verandert een data
item maar de schrijfoperatie faalt, de waarde van dit data item is nu niet meer correct. Voordat
dit hersteld kan worden, leest transactie T2 de foute waarde in.
• The Incorrect Summary Problem. In transactie T1 wordt een aggregatiefunctie berekend
van een aantal items. Als deze items worden aangepast door een transactie T2 tijdens de
berekening van de aggregatiefunctie, dan zal de uitkomst fout zijn.
• The Unrepeatable Read Problem. De waarde van een data item wordt twee keer kort na
elkaar ingelezen. Tussen deze 2 read-operaties wordt de waarde van het data item aangepast
door een andere transactie. De 2 read-operaties lezen dus verschillende waarden.
Zie figuur 20.3 op pagina 727 voor schematische voorstellingen van deze problemen.
20.1.4
Why Recovery Is Needed
Het DBMS moet ervoor zorgen dat een transactie ofwel volledig wordt uitgevoerd (commited),
ofwel helemaal niet wordt uitgevoerd (aborted). Als een transactie faalt, mag de transactie geen
veranderingen aanbrengen in de database of een effect hebben op andere transacties.
• A computer failure (system crash). Een hardware, software of netwerk fout tijdens de
uitvoering van de transactie.
• A transaction or system error. De transactie faalt door een verkeerde parameter, een
integer overflow, een logische programmeerfout of dergelijke in een operatie.
• Local errors or exception conditions detected by the transaction. Een bepaalde
toestand zorgt ervoor dat de transactie moet worden tegengehouden.
• Concurrency control enforcement. De currency control method stopt een transactie vanwege schending van serializability of om een deadlock op te lossen.
• Disk failure. Een disk block verliest data vanwege een fout bij het lezen of schrijven. Een
head crash of een beschadigd spoor is ook mogelijk.
• Physical problems and catastrophes. Stroom- of koelingsproblemen, brand, diefstal, . . .
100
20.2
Transaction and System concepts
20.2.1
Transaction States and Additional Operations
De recovery manager van het DBMS houdt de toestand van de transacties bij. Op die manier kan
de database hersteld worden als een transactie faalt. De volgende operaties worden bijgehouden.
• begin transaction: het begin van de transactie.
• read of write: alle lees- en schrijfoperaties van een transactie.
• end transaction: de uitvoering van de transactie is gedaan. Er moet nog gecontroleerd
worden dat de wijzigingen ook definitief kunnen worden toegepast op de database (committed )
of dat de transactie gestopt moet worden vanwege concurrency control.
• commit transaction: de transactie is succesvol be¨eindigd, de wijzigingen kunnen worden
toegepast op de database (commit) en kunnen niet ongedaan gemaakt worden.
• rollback (of abort): de transactie is gefaald, alle wijzigingen worden ongedaan gemaakt.
Een transactie kan zich in verschillende toestanden bevinden: active (bij het begin van de transactie), partially committed (na het uitvoeren van de lees- en schrijfoperaties), committed (als
de transactie gelukt is), failed of terminated.
Figuur 20.4 op pagina 730 geeft deze verschillende staten schematisch weer.
20.2.2
The System Log
Het systeem houdt een logbestand bij met daarin alle transacties die invloed hebben op items in
de database. Dit bestand is een sequentieel append-only file zodat het geen last kan hebben van
een of andere failure. Het laatste deel van het bestand wordt in de log buffer in het main memory
gehouden voordat het weggeschreven wordt naar het logbestand op de schijf.
De log records zijn de entries van het logbestand, hierbij is T een transaction-id om elke
transactie een unieke naam te geven, X duidt een database item aan.
• [start transaction, T ]
• [write item, T , X, old value, new value]
• [read item, T , X]
• [commit, T ]
• [abort, T ]
Ofwel wordt de transactie dan volledig ongedaan gemaakt: het logbestand wordt achterwaarts
doorlopen en alle write-operaties worden ongedaan gemaakt (undo).
Ofwel wordt de transactie volledig afgewerkt en proberen we de write-operaties te herstellen: het
logbestand wordt voorwaarts doorlopen en alle write-operaties worden opnieuw uitgevoerd (redo).
20.2.3
Commit Point of a Transaction
Een transactie bereikt een commit point als alle operaties succesvol zijn uitgevoerd en als alle bewerking naar het logbestand zijn geschreven. Na het commit point is het resultaat van de transactie
definitief, ze kan niet meer worden ongedaan gemaakt.
Eerst wordt de commit op het logbestand in de log buffer genoteerd. Daarna wordt het deel in
de log buffer definitief op de schijf geschreven, dit proces heet force-writing. Hierna bereikt de
transactie het commit point.
101
20.3
Desirable Properties of Transactions
Transacties moeten een aantal eigenschappen bevatten, de ACID properties.
• Atomicity. Transacties moeten ofwel volledig worden uitgevoerd, ofwel helemaal niet.
• Consistency preservation. Een enkele transactie moet de database van de ene naar de
andere consistente toestand brengen, zonder interferentie van andere transacties.
• Isolation. Het moet lijken alsof het de enige transactie is die wordt uitgevoerd (terwijl er
eigenlijk toch meerdere transacties tegelijk worden uitgevoerd).
• Durability or permanency. De veranderingen door een transactie moeten persistent zijn.
20.4
Characterizing Schedules Based on Recoverability
In een schedule (of transactierooster) worden de operaties van meerdere transacties in chronologische volgorde opgeschreven.
20.4.1
Schedules (Histories) of Transactions
Een schedule S bestaande uit de transacties T1 , T2 , . . . , Tn is een ordening van de volgorde waarin
de operaties van de transacties worden uitgevoerd. De operaties van de verschillende transacties
kunnen door elkaar voorkomen. De volgorde waarin operaties voorkomen in een transactie, moet
wel behouden worden. De volgorde van de operaties in S wordt de total ordening genoemd.
Twee operaties zijn met elkaar in conflict als ze aan de volgende 3 voorwaarden voldoen.
1. Ze behoren tot verschillende transacties.
2. Ze behandelen hetzelfde data item X.
3. Minstens 1 van de operaties is een operatie van de vorm write item(X). Er bestaan readwrite conflicten en write-write conflicten.
Een complete schedule is een schedule S = T1 , T2 , . . . , Tn die aan de volgende condities voldoet.
• De operaties in S zijn exact die in T1 , T2 , . . . , Tn met telkens ofwel een commit-operatie, ofwel
een abort-operatie aan het einde van elke transactie Ti .
• Elke 2 operaties van dezelfde transactie Ti komen (ten opzichte van elkaar) in S in dezelfde
volgorde voor als in de volgorde waarin die 2 operaties in Ti voorkomen.
• Voor elke 2 conflicterende operaties, geldt dat hun volgorde eenduidig vastligt.
De committed projection C(S) van een schedule S bevat enkel de operaties in S die behoren tot
committed transacties, dit zijn transacties Ti wiens commit-operatie ci tot S behoort.
20.4.2
Characterizing Schedules Based on Recoverability
Een schedule S is een recoverable schedule a.s.a. een transactie die gecommit is nooit meer ongedaan gemaakt moet worden. Dus als geen enkele transactie T in S commit voordat alle transacties
T 0 , die een item X hebben beschreven dat door T wordt gelezen, zijn gecommit.
Als dit niet geldt, is S een nonrecoverable schedule.
102
Een recoverable schedule is niet altijd simpel herstelbaar. Soms moet er een cascading rollback
gebeuren, dit kan tijdrovend zijn. In een recoverable schedule S gebeurt een cascading rollback als
een uncommitted transaction een rollback moet ondergaan omdat het een item las van een gefaalde
transactie. Hierdoor kan dan weer een andere uncommitted transaction last hebben.
Een schedule S is een cascadeless schedule als elke transactie in S enkel items leest committed
transactions. Een cascadeless schedule is automatisch ook recoverable.
Een schedule S is een strict schedule als elke transactie T een item X enkel leest of schrijft
als de laatste transactie die X heeft beschreven, gecommit is. Deze schedules zijn gemakkelijk te
herstellen aangezien men gewoon het oorspronkelijke item dat de gefaalde transactie schreef, moet
terugzetten. Een strict schedule is automatisch ook cascadeless.
20.5
Characterizing Schedules Based on Serializability
Een serializable schedule is altijd correct als de transacties concurrent uitgevoerd worden.
20.5.1
Serial, Nonserial, and Conflict-Serializable Schedules
Een schedule wordt serial genoemd als de transacties na elkaar worden uitgevoerd, dus zonder interferentie. Bij een nonserial schedule zijn er meerdere transacties tegelijk actief. Als de transacties
onderling onafhankelijk zijn, dan is een serial schedule altijd correct.
Bij serial schedules moeten transacties soms lang wachten als een voorgaande transactie wacht
op I/O of als die voorgaande transactie te lang duurt. Dit grote nadeel weegt niet op tegen het
voordeel van de correctheid, serial schedules worden dus niet gebruikt.
Een nonserial schedule S met n transacties is serializable a.s.a. het equivalent is met een serial
schedule met dezelfde n transacties. Zo’n nonserial schedule is dus ook altijd correct.
Twee schedules zijn result equivalent als ze dezelfde finale toestand van de database veroorzaken. Deze equivalentie is echter te zwak.
Twee schedules zijn conflict equivalent als ze de conflicterende operaties in dezelfde volgorde
uitvoeren. Een schedule is conflict serializable als het conflict equivalent is met een serial schedule.
20.5.2
Testing for Conflict Serializability of a Schedule
Het volgende algoritme test of een schedule serializable is m.b.v. een precedence graph.
1. Maak een knoop voor elke transactie Ti in S en label die knoop Ti .
2. Maak een boog van Ti naar Tj voor elke situatie in S waarbij:
• Tj een leesoperatie uitvoert nadat Ti een schrijfoperatie uitvoert.
• Tj een schrijfoperatie uitvoert nadat Ti een leesoperatie uitvoert.
• Tj een schrijfoperatie uitvoert nadat Ti een schrijfoperatie uitvoert.
3. Het schedule S is serializable als er geen lussen voorkomen in de graaf.
20.5.3
How Serializability Is Used for Concurrency Control
Er kunnen protocols ontworpen worden om ervoor te zorgen dat alle schedules serializable zijn. In
deze protocols worden regels vastgelegd die elke transactie moet volgen. Ze kunnen ook opgelegd
worden door het DBMS currency control subsysteem. Dit wordt besproken in hoofdstuk 22.
103
20.5.4
View Equivalence and View Serializability
Twee schedules S en S 0 zijn view equivalent als er voldaan wordt aan de volgende voorwaarden.
• Dezelfde verzameling transacties zit in S en in S 0 en de schedule S en S 0 bevatten dezelfde
operaties als die transacties.
• Voor elke leesoperatie ri (X) van Ti in S geldt: als de waarde van X (gelezen door ri ) weggeschreven is door een schrijfoperatie wj (X) van Tj (of als het de originele waarde van X is),
dan moet dezelfde conditie gelden voor de waarde van X, gelezen door ri (X) van Ti in S 0 .
• Als de schrijfoperatie wk (Y ) van Tk de laatste operatie is die het item Y wegschrijft in S, dan
moet wk (Y ) van Tk ook de laatste operatie zijn die Y wegschrijft in S 0 .
Een schedule S is view serializable als het view equivalent is met een serial schedule.
De definities van conflict serializability en view serializability zijn hetzelfde als de voorwaarde
constrained write assumption (of no blind writes) geldt voor alle transacties in het schedule.
Deze voorwaarde stelt dat elke schrijfoperatie wi (X) in Ti voorgegaan moet worden door een leesoperatie ri (X) in Ti en dat de waarde weggeschreven door wi (X) in Ti enkel afhangt van de waarde
X, ingelezen door ri (X).
Een blind write is een schrijfoperatie in een transactie T op een item X dat niet afhangt van
de waarde van X en dus niet voorafgegaan wordt door een leesoperatie van X in T .
De definitie van view serializability is minder strikt dan die van conflict serializability onder voorwaarde van de conditie unconstrained write assumption. Hierbij zijn blind writes wel toegestaan. Testen voor view serializability is NP-hard, er bestaat dus geen effici¨ent algoritme voor.
20.5.5
Other Types of Equivalence of Schedules
Debit-credit transactions zijn transacties die voldoen aan minder strenge voorwaarden dan serializability omdat dit in sommige situaties niet nodig is. Zo zijn bijvoorbeeld de bewerkingen open aftrekken van geld bij een balans commutatief en dus maakt de volgorde van de operaties niet
uit. Deze extra informatie over de transacties wordt de semantics genoemd.
20.6
Transaction Support in SQL
Een SQL instructie wordt als altijd atomisch beschouwd en wordt dus volledig uitgevoerd als er
geen fout voorkomt. Als er wel een fout optreedt, dan blijft de gegevensbank ongewijzigd.
In SQL is er geen Begin Transaction-statement, alle instructies moeten echter wel een end statement hebben: commit of rollback. Het is mogelijk enkele eigenschappen toe te kennen aan
een transactie die met het commando set transaction kunnen gespecificeerd worden.
De optie access mode kan read only (default) of read write zijn.
De optie diagnostic area size specificeert hoeveel condities er tegelijk worden bijgehouden in
de diagnostic area. Deze condities geven informatie over de n meest recente SQL instructies.
De optie isolation level kan gezet worden op read uncommitted, read committed, repeatable read of serializable (default).
Als een transactie uitgevoerd wordt op een lager niveau dan serializable, kunnen er zich verschillende
failures voordoen. Een dirty read bijvoorbeeld maakt gebruik van een tijdelijke aanpassing, deze
aanpassing werd eerder uitgevoerd door een nog niet gecommitte transactie.
Een nonrepeatable read gebeurt als transactie T1 een bepaald item leest, een andere transactie
T2 dit item aanpast, als T1 dan opnieuw dat item leest, zal die een andere waarde hebben.
Een phantom is een record dat zichtbaar wordt de tweede keer dat de tabel gelezen wordt.
104
Hoofdstuk 21
Introduction to Protocols for
Concurrency Control in Databases
21.1
Two-Phase Locking Techniques for Concurrency Control
Een lock is een variabele geassocieerd met een data-item dat de status weergeeft wat betreft de
mogelijke operaties die erop kunnen worden uitgevoerd.
´ en lock per data-item in de database
• E´
• Gebruikt voor synchronisatie bij gelijktijdige toegang
21.1.1
Types of Locks and System Lock Tables
Hieronder worden enkele soorten locks besproken.
Binary Locks
Status Variabele heeft slechts twee toestanden voor data-item X:
• Locked (1): variabele heeft waarde 1 en X is niet toegankelijk
• Unlocked (0): variabele heeft waarde 0 en X is toegankelijk. Indien het item wordt gebruik
wordt de waarde op 1 (Locked) gezet.
We refereren vanaf nu naar de status van lock geassocieerd met X als de booleaanse waarde lock(X)
Operaties Er zijn twee operaties gedefinieerd:
• lock item(X)
Idien een transactie X wil benaderen wordt deze operatie uitgevoerd. Er zijn twee mogelijkheden:
– lock(x) = 1: De transactie moet wachten.
– lock(x) = 0: De waarde van lock(x) wordt op 1 gezet en de transactie kan worden
uitgevoerd.
• unlock item(X)
Wanneer de transactie voltooid is wordt X terug vrijgegeven. De waarde van lock(x) wordt
terug op 0 gezet.
(Exact algoritme zie pagina 757)
105
Critische secties Bovenstaande operaties moeten ondeelbaar of atomair worden uitgevoerd. Dergelijke stukken code worden critische secties genoemd.
Gegevensstructuur Voor de implementatie van een binary lock volstaan twee gegevensstructuren:
• Een queue waarin transacties worden geplaatst die wachten om de lock te bemachtigen.
• Een gegevensstructuur met 3 velden: Data item name, LOCK, Locking transaction >.
Dit zou bijvoorbeeld ook een hash-tabel kunnen zijn waarbij er wordt vanuit gegaan dat items
die niet in de tabel zitten niet gelock zijt.
Regels bij Binary Lock
1. Een transactie moet een operatie lock item(X) uitvoeren alvorens een operatie read item(X)
of write item(X) uit te voeren.
2. Een transactie moet een operatie unlock item(x) uitvoeren nadat alle read item(X) of write item(X)
operaties zijn afgerond.
3. Een transactie mag geen operatie lock item(X) uitvoeren wanneer hij de lock reeds bezit.
4. Een transactie mag geen operatie unlock item(X) uitvoeren wanneer hij de lock niet bezit.
Conclusie
• Zeer eenvoudig
• Slechts 1 transactie kan een lock vasthouden
Shared/Exclusive (or Read/Write) Locks
Bepaalde operaties kunnen gelijktijdig worden uitgevoerd op X. Daarvoor zijn er nu 3 operaties
met bijhorende status:
• read lock(X) → read-locked
Deze lock kan door meerdere transacties tegelijk worden verkregen.
• write lock(X) → write-locked
Deze lock kan exclusief aan ´e´en transactie worden toegewezen.
• unlock(X) → unlocked
Geef X terug vrij.
Deze locks worden ook multiple-mode locks genoemd.
Gegevensstructuur We moeten nu bijhouden hoeveel transacties in het bezit zijn van een read
lock.
< Data item name, LOCK, N o of reads, Locking transaction(s) >
Afhankelijk van het type bevat de lijst met transacties slechts ´e´en element bij een write lock of
meerdere bij een read lock.
106
Regels Read/Write Locks
1. Een transactie moet een operatie read lock(X) of write lock(X) uitvoeren alvorens een operatie
read item(X) uit te voeren.
2. Een transactie moet een operatie write lock(X) uitvoeren alvorens een operatie write item(X)
uit te voeren.
3. Een transactie moet een operatie unlock item(x) uitvoeren nadat alle read item(X) of write item(X)
operaties zijn afgerond.
4. Een transactie mag geen operatie write lock(X) uitvoeren wanneer deze al een read lock of
write lock bezit. (Dit kan worden versoepeld)
5. Een transactie mag geen operatie unlock item(X) uitvoeren wanneer hij de lock niet bezit.
Conversion of Locks
We kunnen regel 4 en 5 versoepelen om lock conversion toe te laten. Hierdoor kan de transactie
zijn lock
• Upgraden: Wanneer deze een read lock bezit kan hij deze upgraden tot een write lock.
• Downgraden: Wanneer deze een write lock bezit kan hij deze downgraden tot een read lock.
Serializability
1. Werkwijze garandeert geen serializability
2. Protocol nodig dat bepaalt wanneer we locken en unlocken
(zie voorbeeld pagina 761)
21.1.2
Guaranteeing Serializability by Two-Phase Locking
Om te voldoen aan het two-phase locking protocol moeten alle locks voorafgaan aan de eerste
unlock-operatie. Hiermee kan een transactie worden opgedeeld in twee fases:
1. Expanding / Growing Phase
Locks kunnen worden bemachtigd maar niet worden vrijgegeven. Bij lock conversion mag
worden geupgrade.
2. Shrinking Phase
Locks kunnen worden vrijgegeven maar niet worden bemachtigd. Bij lock conversion mag
worden gedowngrade.
Indien elke transactie het two-phase locking protocol volgt is de planning
gegarandeerd serializable.
Eigenschappen
• Limiteert de hoeveelheid parallelisme
• Garandeert serializability
• Mogelijk zijn er andere schema’s die ook voldoen, maar niet worden toegelaten met dit principe
107
Basic, Conservative, Strict, and Rigorous Two-Phase Locking
Verschillende varianten op Two-Phase Locking
• Basic
Beschreven in vorige paragraaf
• Conservative of static
–
–
–
–
Vereist dat alles gelockt is alvorent de transactie van start gaat
Predeclareren van een write-set en read-set
Geeft nooit aanleiding tot deadlock
Soms onmogelijk
• Strict
– Meest populair
– Garandeert stricte schema’s
– Vrijgeven van exclusieve locks gebeurt pas helemaal op het einde
• Regorous
–
–
–
–
Nog stricter
Garandeert eveneens stricte schema’s
Vrijgeven van elke lock gebeurt pas helemaal op het einde
Eenvoudiger te implementeren dan strict
Concurrency Control Subsystem
• Verantwoordelijk voor toekennen locks
• Houdt gegevensstructuren bij
21.1.3
Dealing with Deadlock and Starvation
Twee mogelijke problemen die voorkomen bij het gebruik van locks.
Deadlock
Treedt op wanneer elke transactie T in een set van minstens twee transacties wacht op een item dat
locked is door een andere transactie T 0
• Elke transactie in de wachtrij
• Lock kan nooit worden vrijgegeven
Deadlock Prevention Protocols
Protocols voor het verhinderen van deadlocks.
• Lock in advance
Zoals gebruikt bij conservative locking
• Ordering
Bepaal een soort van ordening zodat transacties die meerdere items nodig hebben ze in de
juiste volgorde locken.
108
Timestamp Methodes Alternatieve methodes maken gebruik van een Transaction Timestamp,
genoteerd als T S(T ).
• Kent uniek ID toe aan elke transactie
• Gebaseerd op orde van transactie
• T S(T1 ) < T S(T2 ) ⇒ T1 startte voor T2
Hiermee kunnen volgende regels worden ingesteld ter preventie van deadlocks.
• Wait-die
Als T S(Ti ) < T S(Tj ) dan mag Ti wachten. Indien T S(Ti ) > T S(Tj ) wordt Ti onderbroken
en later herstart met zelfde timestamp.
• Wound-wait
Als T S(Ti ) < T S(Tj ) dan wordt Tj onderbroken en later herstart met zelfde timestamp.
Indien T S(Ti ) > T S(Tj ) mag Ti wachten.
Met deze protocols worden geen circulaire wachtrijen gevormd en zijn deadlocks niet mogelijk.
Wait Methods
• No Waiting
– Transactie wordt onmiddellijk onderbroken als geen lock kan worden bemachtigd
– Geen controle op daadwerkelijke deadlock
– Herstart na zekere periode
• Cautious Waiting
– Ti wilt lock voor X maar deze is in het bezit van Tj
– Als Tj op dat moment zelf ook wacht wordt Ti onderbroken
Beide methodes garanderen dat er geen deadlocks optreden.
Deadlock Detection
Protocols voor het opmerken van deadlocks.
• Interessant indien kans op deadlocks klein is
• Minder interessant indien hoge intensiteit transacties
Wait-for graph
• Knoop voor elke transactie die aan het uitvoeren is
• Gerichte boog van wachtende transactie naar transactie die lock momenteel heeft
• Boog wordt verwijderd indien lock wordt vrijgegeven door eindpunt
In geval van deadlock → vinctim selection
109
Timeouts
• Transactie gelimiteerd in tijd
• Eenvoudig te implementeren
• Weinig overhead
Starvation
• Transactie moet wachten voor onbepaalde duur terwijl andere wel kunnen uitvoeren
• Treedt op bij prioriteiten (bv ter preventie van deadlocks)
• Treedt op wanneer steeds hetzelfde victim wordt gekozen.
Hoe oplossen?
• Eerlijk wachtschema (→ Firs-come-first-served)
• Prioriteit verhogen met wachtduur
Wait-Die en Wound-Wait kunnen geen aanleiding geven tot starvation gezien de transactie herstart
wordt met de originele timestamp.
21.2
Concurrency Control Based on Timestamp Ordering
Alternatief dat eveneens serializability garandeert.
21.2.1
Timestamps
• Unieke identifier, toegekend bij begin van transactie
• Kan gezien worden als de starttijd van de transactie
• Ordening op basis van timestamps voorkomt deadlocks
Implementatie van een timestamp
• Teller die wordt verhoogd bij aanmaak nieuwe timestamp
(Waarde kan niet oneindig toenemen!)
• Huidige tijd waarbij slechts 1 timestamp gegenereeerd kan worden tijdens 1 klik van de klok
21.2.2
The Timestamp Ordering Algorithm
Centraal idee: Sorteren transacties op hun timestamp Verschil met 2PL
• Schema is equivalent met een schema dat voldoet aan 2PL protocol
• Schema is equivalent met schema met dezelfde volgorde van transacties
Het algoritme garandeert dat voor elk item dat wordt benaderd door conflicterende operaties de
volgorde van benadering gelijk is als die van de timestamps. Met elk item worden twee Timestampwaarden geassocieerd:
110
• Read Timestamp: read TS(X)
read TS(X) ← TS(T) waarbij T de jongste transactie is die X heeft gelezen.
• Write Timestamp: write TS(X)
write TS(X) ← TS(T) waarbij T de jongste transactie is die X heeft weggeschreven.
Basic Timestamp Ordering (TO)
• Transactie T probeert een operatie write item(X) uit te voeren. Algoritme controleert of
de timestamp van T kleiner is dan die van X: Boolean b ← write TS(X) > TS(T) ∨
read TS(X) > TS(X)
– If(b=TRUE): Jongere operatie (met grote TS(T’)>TS(T)) heeft waarde reeds veranderd → stop de transactie, herstel eventueel gewijzigde items (roll back) en weiger de
operatie.
– If(b=FALSE): Geen probleem → voer de operatie uit en zet write TS(X) op TS(T)
• Transactie T probeert een operatie read item(X) uit te voeren. Algoritme controleert of de
timestamp van T kleiner is dan die van X: Boolean b ← write TS(X) > TS(T)
– If(b=TRUE): Jongere operatie (met grote TS(T’)>TS(T)) heeft waarde reeds veranderd → stop de transactie, herstel eventueel gewijzigde items (roll back) en weiger de
operatie.
– If(b=FALSE): Geen probleem → voer de operatie uit en zet read TS(X) op max(T S(T ), read T
Samengevat: Wanneer twee conflicterende operaties in verkeerde volgorde worden uitgevoerd,
wordt de laatste van de twee geweigerd door het be¨eindigen van bijhorende transactie .
Strict Timestamp Method
Variant op Basic TO Algoritme die ganradeert dat de schema’s ook strict en conflict serializable
zijn.
Idee: Transactie T die operatie uitvoert zodat TS(T) > write TS(X) moet wachten todat transactie T’ dat de huidige waarde van X schreef (write TS(X) = TS(T’)) voltooid en be¨eindigd is.
→ Geen aanleiding tot deadlock: kan niet circulair worden gewacht door ordering in timestamp.
Thomas’s Write Rule
Variant op Basic TO Algoritme die geen conflic serializabilty garandeert maar minder schrijfoperaties weigert.
• If(read TS(X) > TS(T)): Stop en herstel (roll back)
• Else If(write TS(X) > TS(T)): Voer schrijfoperatie niet uit maar blijf uitvoeren. De
huidige schrijfoperatie van T is reeds verouderd.
• Else: voer de schrijfoperatie uit en zet write TS(X) op TS(T).
111
21.3
Multiversion Concurrency Control Techniques
Hierbij worden oudere versies van de data bijgehouden wanneer de waarde van een item wordt
gewijzigd.
• Leesoperaties die anders geweigerd zouden worden toch nog een oudere versie lezen.
• Door het kiezen van de juiste versie blijft serializabilty gegarandeerd
• Vraagt meer ruimte (maar kan soms sowieso het geval zijn voor herstel)
21.3.1
Multiversion Technique Based on Timestamp Ordering
Opnieuw twee timestmaps
• read TS(Xi ): grootste timestamp (= jongste) van alle transacties die Xi hebben gelezen.
• write TS(Xi ): grootste timestamp (= jongste) van alle transacties die Xi hebben weggeschreven.
Dit leidt tot
• T mag item X schrijven → Versie Xk+1 van X wordt aangemaakt en read TS(Xk+1 ) en write
TS(Xk+1 ) worden op TS(T) gezet.
• T mag item Xi lezen → read TS(Xi ) en write TS(Xi ) worden op TS(T) gezet.
Regels Regels om serializability te garanderen:
1. Als transactie T een write (X) operatie wil uitvoeren en versie i van X heeft de hoogste
write TS(Xi ) waarde van alle versies van X die kleiner of gelijk is aan TS(T) en read TS(Xi )
> TS(T)
→ Be¨eindig en herstel transactie T
(Deze situatie komt voor als T een versie van X probeert te schrijven die gelezen zou moeten
zijn door een transactie T’ met timestamp read TS(T’))
Anders: Vorm een nieuwe versie Xj van X met read TS(Xj ) = write TS(Xj ) = TS(T)
2. Als transactie T een read (X) operatie wil uitvoeren, vind versie i van X met de hoogste
write TS(Xi ) van alle X die kleiner zijn van TS(X)
→ Geef de waarde van Xi terug aan transactie T en zet de waarde van read TS(Xi op
max(T S(T ), readT S(Xi ))
→ Lezen is altijd succesvol.
→ Herstellen kan aanleiding geven tot cascading rollback
21.3.2
Multiversion Two-Phase Locking Using Certify Locks
Drie soorten locking
• Read: Onveranderd
• Write: Twee versies → een transactie T’ mag X lezen terwijl T hierop een writ lock bezit.
´ en versie weggeschreven door voltooide transactie
– E´
– Andere versie aangemaakt bij verkrijgen write lock voor T
• Certify : Exclusief en nodig voor het voltooien van transactie → nodig voor elk object waarop
write lock is verkregen
112
Eigenschappen
• Lezen kan gelijktijdig met enkelvoudig write lock
• Voltooien transactie kan uitgesteld worden door wachten op certify lock
• Deadlocks kunnen voorkomen bij het upgraden van read naar write lock
21.4
Validation (Optimistic) Concurrency Control Techniques
Voorgaande technieken checken voor de uitvoer van de operaties → overhead en vertraging.
Validation of Certification doet geen controle tijdens de uitvoer van de transactie.
Protocolfasen
1. Read Phase: Een transactie kan waarden lezen van gecommiteeerde items in de database.
Updates worden enkel toegewezen aan lokale kopie¨en.
2. Validation Phase: Controle wordt uitgevoerd om te verzekeren dat geen updates de serializability schenden.
3. Write Phase: Als de validatie succesvol was worden de updates weggeschreven naar de
database.
Centraal idee
• Controle in ´e´en keer op het einde
• Uitvoer met een minimum aan overhead tot de validatie wordt bereikt
Optimistisch
• Als er veel interferentie is zullen vele transacties moeten herstarten na validatiefase
• Optimischtisch veronderstelt weinig interferentie
Protocol
Maakt gebruik van transaction timestamps en moet daarnaast bijhouden:
• write sets en read sets (= alle items die respectievelijk geschreven en gelezen worden)
• Begin- en eindtijden van fases
→ Bij de validatiefase voor Ti wordt nagegaan of deze niet interfereert met gecommiteerde transacties of transacties momenteel ook in de validatiefase zitten.W
113
Protocol regels Tijdens de validatie wordt gecontroleerd of, voor elke transactie Tj dat deze
ofwel gecommitteerd is ofwel in zijn validatiefase is geldt:
1. Transactie Tj voltooid zijn schrijffase voordat Ti zijn leesfase begint.
2. Ti start zijn leesfase na de schrijffase van Tj en de read set van Ti heeft geen elementen
gemeenschappelijk met de write set van Tj
3. Zowel de read set als de write set van Ti hebben geen elementen gemeenschappelijk met de
write set van Tj en Tj voltooit zijn leesfase Ti zijn leesfase voltooit.
21.5
Granularity of Data Items and Multiple Granularity
Locking
We gingen er steeds van uit dat de database gevormd werd door een aantal data-items, bijvoorbeeld:
• Een record
• Een veld van een record
• Een disk block
• Volledig bestand
• De volledig database
De granularity of granulariteit bepaalt de performatie van bovenvermelde technieken.
21.5.1
Granularity Level Considerations for Locking
Data item granularity
• Fijne granulariteit: kleine items
• Grove granulariteit: grote items
Voor- en nadelen
• Grove granulariteit
– Minder parallellisme
– Lange wachttijden
• Fijne granulariteit
– Groter aantal items in de database
– Meer overhead
→ Beste grootte hangt af van situatie
114
21.5.2
Multiple Granularity Level Locking
Ondersteunen van locks voor verschillende groottes van items → multiple granularity level 2PL
(Probleem: voorbeeld probleem zie pagina 775)
Nieuw type lock nodig: intention lock → toont pad vanaf root tot gewenste knoop in granulariteitshierarchie.
1. Itention-shared (IS): ´e´en of meer gedeelde locks op onderliggende kno(o)p(en).
2. Intention-exclusive (IX) ´e´en of meer exclusieve locks op onderliggende kno(o)p(en).
3. Shared-intention-exclusive (SIX) Op huidige knoop rust een gedeeld lock maar ´e´en of
meer exclusieve locks zullen worden aangevraagd op onderliggende knopen.
Protocol regels Multiple Granularity Locking (MLG)
1. Compatibiliteit locks moet aangehouden worden. (zie pagina 776)
2. De root moet altijd als eerste worden gelockt.
3. Een knoop N kan gelockt zijn door transactie T in S of in IS mode als en slechts als de vader
van de knoop N reeds gelockt is door transactie T in IS ofwel IX.
4. Een knoop N kan gelockt zijn door transactie T in X, IX of in SIX mode als en slechts als
de vader van de knoop N reeds gelockt is door transactie T in IX ofwel SIX.
5. Een transactie T kan een knoop enkel een lock aanvragen als het geen knopen heeft geunlockt.
6. Een transactie T kan een knoop N enkel vrijgegven als geen van de kinderen van N momenteel
gelockt zijn door T.
Regel 1 → geen conflicten toelaten
Regel 5,6 → forceren 2PL protocol
Toepassing Vooral geschikt voor een mix tussen
• Korte transacties die slechts een beperk aantal items vereisen
• Grote transacties die volledige bestanden vereisen
21.6
Using Locks for Concurrency Control in Indexes
Locking gebruiken voor indexen (cfr. hoofdstuk 17)
Probleem: Index begint steeds in root → grote hoeveelheid blocking
• Root zou gelockt worden in exclusive mode
• Alle conflicterende transacties moeten wachten
Oplossing: Uitbuiten boomstructuur → zoeken via index betekent boom doorlopen
• Bovenliggende knoop niet meer nodig eens gepasseerd
• Lock op parent mag opgeheven worden eens lock op kind is toegewezen
115
Conservatieve benadering invoegen
1. Lock root in exclusive mode
2. Bereik kindknoop
3. Als het kind niet vol is → geef root vrij
→ Kan toegepast worden op elk niveau van de boom
→ Exlusieve lock worden snel vrijgegeven
Optimistische benadering
• Shared lock voor de knopen leidend naar doelknoop
• Exclusive lock op bladknoop
• Indien invoeging leidt tot splitsing → propageer opwaarts → upgrade locks naar exclusive
locks
Benadering met variant B + -tree: B-link tree Hierbij zijn alle broderknopen op hetzelfde
niveau gelinkt.
• Zoeken
– Shared lock bij opvragen pagina
– Lock moet vrijgegeven worden alsvorens kind te benaderen
• Invoegen
– Upgrade shared lock tot exclusive lock
– Bij splitsing moet vaderknoop opnieuw gelockt worden in exclusive mode
• Complicatie
– Veronderstel invoegoperatie volgt zelfde pad als zoekoperatie
– Wordt nieuw item ingevoegd in bladknoop die zorgt voor een splitsing
– Wanneer zoektoch daarna wordt voorgezet wordt een foute bladknoop gevonden
– Kan toch gevonden worden door link te volgen naar broederknoop
21.7
Other Concurrency Control Issues
21.7.1
Insertion, Deletion, and Phantom Records
Insertion
Nieuwe record dat wordt ingevoerd → kan uiteraard niet benderd worden tot het bestaat
• Locking environment: Write lock (exlusief)
• Timestmap environment: Timestamp = die van transactie die aanmaakt
116
Deletion
• Locking environment: Write lock (exlusief)
• Timestmap environment: Latere transacties mogen item niet schrijven of lezen alvorens
het verwijderd is
Phantom Records
Veronderstel volgende situatie
• Transactie T: voegt record toe met Dno=5
• Transactie T’: selecteert alle records met Dno=5
Mogelijke volgorde van uitvoer:
• T’ na T: Moet nieuwe record omvatten
• T na T’: Mag nieuwe record niet omvatten
Als T’ alle records met Dno=5 al heeft gelockt zijn er geen gemeenschappelijke records tussen beide
transacties → nieuwe record is phantom record
Index Locking Oplossing voor phantom records
• Locken van index alvorens invoegen record
• Conflict index lock → phantom record wordt opgemerkt
21.7.2
Interactive Transactions
Lezen van invoer en schrijven van uitvoer naar een interactief apparaat alvorens gegevens gecommit zijn.
• Eventuele afhankelijkheid tussen transacties is niet gekend door systeem
• Afhankelijkheid kan niet worden afgedwongen door concurrency control
→ Uitstellen van weergeven tot alles is gecommit.
21.7.3
Latches
Locks die slechts voor korte duur bestaan.
• Volgens niet standaard protocol
• Bijvoorbeeld bij wegschrijven pagina naar schijf
117
Hoofdstuk 22
Introduction to Database Recovery
Protocols
22.1
Recovery Concepts
22.1.1
Recovery Outline and Categorization of Recovery Algorithms
Recovery from transaction
• Restore to the most recent consistent state
• Information is kept by system log
Typical Strategy for Recovery
1. Extensive damage due to catastrophic failure
• Recover form last archived backup
• Reconstruct current state by redoing operations of commited transaction
• Commited transactions are kept by backed up log
2. No physical damage is done
• Identify changes causing inconsistencies
• Undo transactions that weren’t committed
• Redo transactions that were committed but not properly finished
(e.g. not yet written to disk)
Deffered Update
No physical update on disk until after a transaction is complete.
• Updates are recorded by database until committed
• Either in main memory or transaction workspace
• Written to disk once committed
Failures before commit do no harm
• no UNDO necessary
118
• REDO might be necessary: writing may not have finished after commit
→ NO-UNDO/REDO Algorithm
Immediate Update
Operation may update the database on disk before a transaction is complete.
• Operations have to write log on disk before executing
• In case of failure before committed: UNDO from log on disk (Rollback)
• Both UNDO and REDO
→ UNDO/REDO Algorithm
UNDO/REDO Operations
• Required to be idempotent
• Executing an operations multiple times has to be equivalent to executing it once
• Whole recovery process should be idempotent
→ The result of recovery from a system crash during recovery should be the same as the result of
recovering when there is no crash during recovery!
22.1.2
Caching (Buffering) of Disk Blocks
Buffering
• Disk pages are kept in main memory
• Updates are written to copies in memory instead onto disk
• Usually handled by OS, but database do it themselves
Directory
• In-memory buffers controlled by DBMS
• Directoy is used to keep track of what’s in those buffers
• If requested file is not in the cache, fetch in from disk and copy it cache
• If cache is full
– Replace a page
– Flush a cache buffer
• Page replacement strategy used
– Least recently used (LRU)
– First-in-first-out (FIFO)
– Least-likely-to use
119
Additional information in directory
• Dirty bit
– Indicates whether of not buffer has been modified
– Possibly additional information (such as modifying transaction)
– Only pages with dirty bit = 0 have to be written do disk when flushed
• Pin-unpin bit
– Pinned page cannot be written back to disk
– May be necessary for implementing recovery protocol
Strategies for Flushing
• In-place updating
– Writes buffer to same original location on disk
– Overwrites the old value of changed data
• Shadowing
– Different disk location
– Multiple versions of same data exists
– Not typically used in practice
We have to types of values
• Before image (BFIM): value before updating
• After image (AFMI): value after updating
22.1.3
Write-Ahead Logging, Steal/No-Steal, and Force/No-Foce
Write-Ahead Logging
• Use of a log is necessary for in-place updating
• BFIM must be recorded in log entry and flushed to disk
• BFIM is flushed before AFIM is written to disk
= Write-Ahead Logging
Log entries Distinguish between two types of log entry information
• REDO-type log
– Includes the new value (AFIM)
– Needed to redo the operation
• UNDO-type log
– Includes the old value (BFIM)
– Needed to undo the operation
→ Combined for UNDO/REDO-Algorithm
120
Log Buffering
• Log is stored in log buffer in main memory
• Log consists of append-only file
• Last n block of that file are in cache
→ Must first be written to disk before the data block itself can be written back!
Steal/No-steal
• No-steal approach
– Cache buffer page update cannot be written to disk before transaction commits
– Indicated by pin-bit
• Steal approach
– Allows writing an updated buffer before the transaction commits
– Used when buffer manager needs a buffer frame and replaces an existing page that had
been updated but whose transaction had not committed.
Force/No-force
• Force approach
– Updated pages are written to disk before transaction commits
– REDO will never be needed
• No-force approach
– The opposite, obviously
Typically a steal/no-force approach is used.
• Advantage is a page of a committed transaction may still be in the buffer
• Eliminates expensive IO
Recovery Lists
To facilitate recovery: the DBMS may need to maintain a number of lists
• Active transactions: have started but not committed
• Committed transactions
• Aborted transactions: since last checkpoint
→ Maintaining those lists makes recovery more efficient!
121
22.1.4
Checkpoints in the System Log and Fuzzy Checkpoints
Checkpoints
A checkpoint is a list of active transactions that is periodically written into the log when all
changed buffers are written to disk.
• All transactions have their commit-entries in the log before a checkpoint
• Do not have to have their write operation redone after checkpoint
• List of active transactions is included in checkpoint → easily redone
DBMS decides on what intervals to take a checkpoint. This consists of:
1. Suspending execution of transactions temporarily
2. Force-writing all changed main memory buffers to disk
3. Writing checkpoint-record to log and force-writing it to disk
4. Resuming execution
→ Additional info may be included, facilitating undoing in case of a rollback.
Fuzzy Checkpoints
Transactions may be delayed due to checkpoint taking → fuzzy checkpointing reduces this.
• Transactions resumes after writing of begin-checkpoint
• After step 2 → write end-checkpoint to disk
• Previous checkpoint should remain valid
• Pointer on disk points to previous checkpoint until end-checkpoint is reached
22.1.5
Transaction Rollback and Cascading Roll back
A rollback is needed when a transaction fails before committing. Changed data must be changed
back to its original state.
Cascading Rollback
1. Transaction T fails and rolls back
2. Transaction S had read data changed by T
→ S has to be rolled back also.
This can process can continue for a long time and is called cascading roll back. This can be
complex and time consuming → systems are designed so that this is never needed.
For an example: check page 792 in Database Systems (Sixth Edition)
122
22.1.6
Transactions Actions That Do Not Affect the Database
In general, there are actions that do not affect the database
• Should not execute multiple times in case of recovery
• Execute after transaction committed
• Create a batch job which is executed afterwards
22.2
NO-UNDO/REDO Recovery Base on Deffered Update
→ Postpone updates until the transaction completes and reaches its commit point.
• Updates are recorded to a log
• Log is force-written to disk when committing
• Only REDO-entries needed
• Only applicable if transactions change few items
→ Buffers will run out of space!
Protocol
1. A transaction cannot change the database on disk until it reaches its commit point.
2. A transaction does not reach its commit point untill all its REDO-type log entries are recorded
in the log and the log buffer is written to disk.
Same properties as listed above.
Multiuser Systems
Concurrency control and recovery are interrelated. Consider a system with concurrency control
using 2PL. We call a possible algorithm RDU M or Recovery used Deferred Update in a Multiuser
environment.
Procedure RDU M (NO-UNDO/REDO with checkpoints)
• Two lists of transactions
– Committed transaction T since last checkpoint: commit list
– Active transactions T’: active list
• REDO all write operations of the committed transaction list from the log, in the order they
were written to the log
• Active transactions did not commit hence no action is required
Procedure REDO (WRITE OP)
• Examin the log entry
• Set item to the AFIM
For an example: check page 794 in Database Systems (Sixth Edition)
123
Efficiency improvements
If a data item X has been updated more than once by committed transactions since the last
checkpoint, it is only necessary to REDO the last update of X from the log during recovery!
→ Start from the end of the log
Aborted Transactions
If a transaction is aborted it is simply resubmitted since it has not changed the database. This has
drawbacks:
• Limits concurrent execution
• All write-locked items remain locked until commit-point is reached
• Requires excessive buffer space to hold items
The main benefit is that a transaction operation never has to be undone for two reasons:
1. A transaction does not record any changes until commit-point → never rolled back
2. A transaction will never read the value of an item that is written by an uncommitted transaction
22.3
Recovery Rechniques Based on Immediate Update
→ Updates are immediately written to disk. Though this is not a requirement!
Handling Failed Transactions
• Undoing the effect of updates
• Rolling back transactions
• UNDO-type log entries are used which contain the old value (BFIM)
• Require steal strategy
We can distinguish two main types of algorithms:
• Updates recorded on disk before transaction commits
– Never need to REDO
– Called UNDO/NO-Redo recovery algorithm
– Used Force-Strategy for deciding when buffers are written to disk
• Transaction is allowed to commit before updates are written to disk
– UNDO/REDO recovery algorithm
– Steal/No-force strategy
124
Concurrent execution
Recovery process depends on concurrency control protocol
• RIU M: Recovery using Immediate Updates for a Multiuser environment
• We assume checkpoints and a strict schedules
• Deadlocks may occur thus requires abort and UNDO-operations
Procedure RIU M (UNDO/REDO with checkpoints)
1. Use two lists maintained by the system
• Committed transactions
• Active transactions
2. Undo all write item operations of active, uncommitted transactions using UNDO (in reverse order of log)
3. Redo all write item operations of committed transactions from the log in regular order
Whenever an operation is redone, it’s added to a list so it is not redone again.
Procedure REDO (Write OP)
1. Examine log entry and set value of X back to old value (BFIM)
2. Undo write item in reverse order
Only one UNDO operation is needed → scan list in forward direction and apply earliest UNDO.
22.4
Shadow Paging
• Does not require use of a log in single-user environment
• Log may be used in multiuser environment
22.4.1
Before Transaction
• Database consists of fixed size pages
• Directory with n entries with ith entry the ith page on disk
• Directory is kept in main memory
• When transaction begins executing the current directory is copied into a shadow directory
• Shadow directory is saved on disk while active is used
125
22.4.2
During Transaction
• Shadow directory is not touched during transaction
• In case of write item, new page is created
• Old page is not overwritten
• Current directory points to new page, whereas the old one points to the previous
•
→ For every updates page, there are two version. One referenced to by the shadow directory, and
one by the active directory.
22.4.3
Recovery Process
• Free the modified database page → discard current directory
• Previous state is available trough the shadow directory
• Committing corresponds to discarding shadow directory
→ No UNDO/REDO necessary!
22.4.4
Disadvantages
• Logs and checkpoints need to be incorporated into page for multiuser envornment
• Changing location on disk → less efficient
• Large directories may exist
• Overhead of writing shadow directories to disk
• Old page must be released → Garbage collection
• Migration between directories has to be atomic!
22.5
The Aries Recovery Algorithm
• Used in database related IBM products
• Uses a steal/no-force approach
Based on 3 concepts:
1. Write-ahead logging
2. Repeating history during REDO
• Retrace all actions prior to the crash
• Uncommitted transactions at the time of the crash are omitted
3. Logging changes during UNDO
• Prevents from repeating the completed UNDO operations
• In case of restart during recovery
126
22.5.1
Analysis Phase
• Identifies dirty buffer pages in buffer
• Appropriate location from where REDO should start is determined
22.5.2
REDO Phase
• Reads start point for REDO
• From there REDO operations are applied until end of log is reached
• Only necessary REDO operations are applied
22.5.3
UNDO Phase
• Log is scanned backwards
• Operations are undone in reverse order
22.5.4
Structures
• Log
• Transaction Table
• Dirty Page Table
• Checkpoints
22.5.5
Log Sequence Number (LSN)
• Monotonically increasing
• Indicates the address of the log record on disk
• Corresponds to specific change of some transaction
• Each page will store LSN of the last record corresponding to a change for that page
• Log is written when
–
–
–
–
–
Updating a page (write)
Committing a transaction (commit)
Aborting a transaction (abort)
Undoing an update (undo) → compensation log record
Ending a transaction (end)→ end log record
Fields in log
• Previous LSN: Links the log records in reverse order for each transaction
• For write record
– Page ID
– Length of the updated item
– Offset from the beginning of the page
127
22.5.6
Tables
• Transaction Table
– Entry for each active transaction
– Information such as ID, status and the LSN of the most recent log record
• Dirty Page Table
– Entry for each dirty page in buffer
– Includes page ID, LSN of the earliest update to that page
→ Mainly used by transaction manager
22.5.7
Checkpoints
• Writing a begin checkpoint record
• Writing an end checkpoint record
– Content of both the transaction table and Dirty Page Table are appended tot the log
– Fuzzy checkpointing is used
• Writing LSN of the begin checkpoint to a special file
– Accessed during recovery
– Used to locate last checkpoint information
22.5.8
Recovery from crash
• Information from the last checkpoint is first accessed trough the special file
•
For the detailed exaplanation of the ARIES Algorithm, refer to page 799 in Database
Concepts (6th edition)
22.6
Recovery in Multidatabse Systems
• Single transaction may need acces to multiple databases
• May even be different types of databases
• Recovery techniques may differ between databases
→ Global Recovery Manager of Coordinator is needed.
→ Follows two-phase commit protocol
• Phase 1
– All participation database signal coordinator that their part has concluded
– Coordinator sends message prepare for commit
128
– Every receiving database will force-write all log records etc to disk
– Answer coordinator with ready to commit
– If write fails send cordinator cannot commit
– Assumes a not OK reply if no response after a time interval
• Phase 2
– All participants reply OK
– Coordinators vote is also OK
– Transaction is successful
– Coordinator sends a commit signal
– In case of failure: roll back message
→ Either all databases commit or all database roll back.
22.7
Database Backup and Recovery from Catastrophic
Failures
• Techniques so far focussed on non-catastrophic failures
• Entries from log or shadow directories are used
22.7.1
Handling more Catastrophic Failures
• Databse Backup
• Whole database and log are periodically copied to cheap storage medium
• The latest backup can be reloaded
• Such backups may be locked in a vault for critical information
– Stock markets
– Banking and insurance
22.7.2
Increase frequency
• Create customary backups
• Start where last complete backup ended
• Smaller thus possible to create more frequently
• After full recovery, redo operations noted in this backup
129

Catalogus Professorum Academie Groninganae

BOB TAKKEN - Bourgondische Triathleten

PWS 1000-125 - Bosch-do

Vomar Voordeelmarkt B.V. respecteert uw privacy en behandelt uw

Aanmeldingsformulier U3L 2014

Les 12 : database koppeling, opmaken van template, webstructuur

šAT979250753–œ

Meer informatie

Amsterdam Swim Cup 2014 Amsterdam, 12- - 14-12

Klik dan hier!