CO22001 Database SystemsStudent Notes

NapierUniversity

Edinburgh

Database Systems

Student Notes

CO22001/CO72010

Version 1.22.0

School Of Computing

Dr G. RussellCopyright © 2001 Napier UniversityPage 1

CO22001 Database SystemsStudent Notes

This Document

Unit 1.1 - Introduction

Database System

Data

Hardware

Software

Users

Database Architecture

External View

Conceptual View

Internal View

Mappings

DBMS

Database Administrator

DBA Tools

Facilities and Limitations

Data Independence

Data Redundancy

Data Integrity

Unit 1.2 - SQL

Database Models

Relational Databases

Relational Data Structure

Domain and Integrity Constraints

Menu Example

External vs Logical

Columns or Attributes

Rows or Tuples

Primary Keys

Employee Table - Columns

Jobhistory Table - Columns

Foreign Keys

SQL

SQL Basics

CREATE table employee

CREATE Table Jobhistory

SQL SELECT

Comparison

SELECT with BETWEEN

Pattern Matching

ORDER and DISTINCT

Unit 1.3 - Logical Operators

IN

Other SELECT capabilities

Simple COUNT examples

Grouped COUNTs

Joining Tables

SELECT - Order of Evaluation

One-to-Many Relationships

Many-to-Many Relationships.

Aliases

Aliases with Self Joins

Unit 1.4 - Subqueries

Simple Example

Subqueries with ANY, ALL

Subqueries with IN, NOT IN

Subqueries with EXISTS

UNION of Subqueries

Views

View Manipulation

VIEW update, insert and delete

Other SQL Statements

INSERT

DELETE

UPDATE

Unit 2.1: Database Analysis

Entity Relationship Modelling

Database Analysis Life Cycle

Three-level Database Model

Entity Relationship Modelling

Entities

Attribute

Keys

Relationships

Degree of a Relationship

Degree of a Relationship

Replacing ternary relationships

Cardinality

Optionality

Entity Sets

Confirming Correctness

Deriving the relationship parameters

Redundant relationships

Redundant relationships example

Splitting n:m Relationships

Splitting n:m Relationships - Example

Constructing an ER model - Entities

Constructing an ER model - Attributes

Constructing an ER model - Relationships

Unit 2.2 - Entity Relationship Modelling - 2

Country Bus Company

Entities

Relationships

Draw E-R Diagram

Attributes

Problems with ER Models

Fan traps

Chasm traps

Enhanced ER Models (EER)

Specialisation

Generalisation

Unit 2.3 - Mapping ER Models into Relations

What is a relation?

Foreign keys

Preparing to map the ER model

Mapping 1:1 relationships

Mandatory at both ends

When not to combine

If not combined...

Example

Mandatory Optional

Mandatory Optional - Subsume?

Summary...

Optional at both ends...

Mapping 1:m relationships

Mapping n:m relationships

Summary

Unit 2.4 - Advanced ER Mapping

Mapping parallel relationships

Mapping 1:m in unary relationships

Mapping superclasses and subclasses

Example

Unit 3.1 - Normalisation

What is normalisation?

Integrity Constraints

Understanding Data

Student - an unnormalised table with repeating groups

Student #2 - Flattened Table

First Normal Form

Flatten table and Extend Primary Key

Decomposing the relation

Second Normal Form

Third Normal Form

Summary: 1NF

Summary: 2NF

Summary: 3NF

Unit 3.2 - Normalisation Continued

Boyce-Codd Normal Form (BCNF)

Normalisation to BCNF - Example 1

Summary - Example 1

Example 2

Problems BCNF overcomes

Fourth Normal Form

Example

Fifth Normal Form

Join Dependency Decomposition

Spurious results

Returning to the ER Model

Unit 3.3 - Relational Algebra

Terminology

Operators - Write

Operators - Retrieval

Relational SELECT

Relational PROJECT

SELECT and PROJECT

Set Operations - semantics

SET Operations - requirements

UNION Example

INTERSECTION Example

DIFFERENCE Example

CARTESIAN PRODUCT

CARTESIAN PRODUCT example

JOIN Operator

JOIN Example

Natural Join

OUTER JOINs

OUTER JOIN example 1

OUTER JOIN example 2

Unit 3.4 - Relational Algebra - Example

Symbolic Notation

Usage

Rename Operator

Derivable Operators

Equivalence

Equivalences

Comparing RA and SQL

Comparing RA and SQL

Unit 4.1 - Concurrency using Transactions

Transactions

Transaction Schedules

Lost Update scenario.

Uncommitted Dependency

Inconsistency

Serialisability

Precedence Graph

Precedence Graph : Method

Example 1

Example 2

Unit 4.2 - Concurrency

Locking

Locking - Uncommitted Dependency

Deadlock

Deadlock Handling

Deadlock Resolution

Two-Phase Locking

Other Database Consistency Methods

Timestamping rules

Unit 4.3 – Storage Structures

The Physical Store

Why not all Main Memory?

Secondary Storage - Blocks

Hard Drives

DBMS Data Items

File Organisations

Storage Scenario

Serial Organisation

Sequential Organisation

Hash Organisation

Indexed Sequential Access Method

ISAM Example

B+ Tree Index

B+ Tree Example

Building a B+ Tree

B+ Tree Build Example

Index Structure and Access

Costing Index and File Access

Use of Indexes

Unit 4.4 - Recovery

Recovery: the dump

Recovery: the transaction log

Deferred Update

Example

Immediate Update

Example

Rollback

Unit 5.1 - Embedded SQL

Interactive SQL

Embedded SQL

SQL Precompiler

Sharing Variables

Connecting to the DBMS

Queries producing a single row

SELECT with a single result

Cursors - SELECT many rows

Fetching values

Declaring and Opening a Cursor

Program Example

Summary

Unit 5.2a - Database Administrator

DBA Tools

DBMS Product Evaluation

Data Structures Supported

Performance

Tools

Unit 5.2b - Security

Granularity of DBMS Security

DBMS-level Protection

User-level Security for SQL

Naming Hierarchy

The GRANT command

Unit 5.3 - Data Dictionary

Benefits of a DDS

DDS Facilities

DD Information

DD Management

Management Objectives

Advanced Facilities

Management Advantages

Management Disadvantages

Tutorial - ER Diagram Examples 1-2

Example 1

Example 2

Tutorial - ER Diagram Examples 3-5

Example 3

Example 4

Example 5

Multiple Choice - HOWTO

The Answer Sheet

Entering an answer

Reason/Assertion

Example

Unit 1.1 - Introduction7

Database System7

Data7

Hardware8

Software8

Users8

Database Architecture8

External View10

Conceptual View10

Internal View11

Mappings11

DBMS12

Database Administrator12

DBA Tools13

Facilities and Limitations13

Data Independence14

Data Redundancy14

Data Integrity15

Unit 1.2 - SQL16

Database Models17

Relational Databases17

Relational Data Structure17

Domain and Integrity Constraints18

Menu Example18

External vs Logical19

Columns or Attributes19

Rows or Tuples19

Primary Keys19

Employee Table - Columns20

Jobhistory Table - Columns20

Foreign Keys20

SQL20

SQL Basics21

CREATE table employee21

CREATE Table Jobhistory21

SQL SELECT22

Comparison22

SELECT with BETWEEN22

Pattern Matching23

ORDER and DISTINCT23

Unit 1.3 - Logical Operators24

IN24

Other SELECT capabilities24

Simple COUNT examples25

Grouped COUNTs25

Joining Tables25

SELECT - Order of Evaluation26

One-to-Many Relationships26

Many-to-Many Relationships.26

Aliases27

Aliases with Self Joins27

Unit 1.4 - Subqueries29

Simple Example29

Subqueries with ANY, ALL29

Subqueries with IN, NOT IN29

Subqueries with EXISTS30

UNION of Subqueries30

Views30

View Manipulation31

VIEW update, insert and delete31

Other SQL Statements32

INSERT33

DELETE33

UPDATE33

Unit 2.1: Database Analysis35

Entity Relationship Modelling35

Database Analysis Life Cycle36

Three-level Database Model37

Entity Relationship Modelling38

Entities39

Attribute39

Keys40

Relationships40

Degree of a Relationship40

Degree of a Relationship41

Replacing ternary relationships41

Cardinality42

Optionality43

Entity Sets44

Confirming Correctness44

Deriving the relationship parameters44

Redundant relationships45

Redundant relationships example45

Splitting n:m Relationships45

Splitting n:m Relationships - Example46

Constructing an ER model - Entities46

Constructing an ER model - Attributes46

Constructing an ER model - Relationships47

Unit 2.2 - Entity Relationship Modelling - 248

Country Bus Company48

Entities48

Relationships48

Draw E-R Diagram49

Attributes49

Problems with ER Models50

Fan traps51

Chasm traps51

Enhanced ER Models (EER)52

Specialisation52

Generalisation53

Unit 2.3 - Mapping ER Models into Relations53

What is a relation?53

Foreign keys54

Preparing to map the ER model54

Mapping 1:1 relationships54

Mandatory at both ends55

When not to combine55

If not combined...55

Example55

Mandatory Optional56

Mandatory Optional - Subsume?57

Summary...57

Optional at both ends...57

Mapping 1:m relationships58

Mapping n:m relationships58

Summary59

Unit 2.4 - Advanced ER Mapping59

Mapping parallel relationships59

Mapping 1:m in unary relationships60

Mapping superclasses and subclasses61

Example61

Unit 3.1 - Normalisation63

What is normalisation?63

Integrity Constraints64

Understanding Data64

Sometimes the starting point for understanding data is given in the form of relations and functional dependancies. This would be the case where the starting point in the process was a detailed specification of the problem. We already know what relations are. Functional dependancies are rules stating that given a certain set of attributes (the determinant) determines a second set of attributes. Consider this example: 64

Student - an unnormalised table with repeating groups65

Student #2 - Flattened Table66

First Normal Form67

Flatten table and Extend Primary Key67

Decomposing the relation68

Record69

Student69

Second Normal Form70

Third Normal Form72

Summary: 1NF74

Summary: 2NF74

Summary: 3NF75

Unit 3.2 - Normalisation Continued75

Boyce-Codd Normal Form (BCNF)75

Normalisation to BCNF - Example 176

Summary - Example 179

Example 280

Problems BCNF overcomes81

Fourth Normal Form82

Example82

Fifth Normal Form83

Join Dependency Decomposition83

Spurious results84

Returning to the ER Model84

Unit 3.3 - Relational Algebra85

Terminology85

Operators - Write85

Operators - Retrieval86

Relational SELECT86

Relational PROJECT86

SELECT and PROJECT86

Set Operations - semantics86

SET Operations - requirements87

UNION Example87

INTERSECTION Example88

DIFFERENCE Example88

CARTESIAN PRODUCT88

CARTESIAN PRODUCT example89

JOIN Operator89

JOIN Example89

Natural Join89

OUTER JOINs90

OUTER JOIN example 190

OUTER JOIN example 291

Unit 3.4 - Relational Algebra - Example91

Symbolic Notation91

Usage92

Rename Operator92

Derivable Operators93

Equivalence93

Equivalences93

Comparing RA and SQL94

Comparing RA and SQL94

Unit 4.1 - Concurrency using Transactions95

Transactions95

Transaction Schedules95

Lost Update scenario.97

Uncommitted Dependency97

Inconsistency98

Serialisability98

Precedence Graph98

Precedence Graph : Method98

Example 199

Example 299

Unit 4.2 - Concurrency100

Locking100

Locking - Uncommitted Dependency101

Deadlock101

Deadlock Handling102

Deadlock Resolution103

Two-Phase Locking103

Other Database Consistency Methods103

Timestamping rules104

Unit 4.3 – Storage Structures105

The Physical Store105

Why not all Main Memory?105

Secondary Storage - Blocks105

Hard Drives106

DBMS Data Items106

File Organisations106

Storage Scenario107

Serial Organisation107

Sequential Organisation108

Hash Organisation108

Indexed Sequential Access Method109

ISAM Example109

B+ Tree Index109

B+ Tree Example110

Building a B+ Tree110

B+ Tree Build Example111

Index Structure and Access111

Costing Index and File Access112

Use of Indexes112

Unit 4.4 - Recovery113

Recovery: the dump113

Recovery: the transaction log114

Deferred Update114

Example114

Immediate Update115

Example116

Rollback117

Unit 5.1 - Embedded SQL118

Interactive SQL118

Embedded SQL118

SQL Precompiler118

Sharing Variables119

Connecting to the DBMS119

Queries producing a single row119

SELECT with a single result120

Cursors - SELECT many rows120

Fetching values120

Declaring and Opening a Cursor121

Program Example121

Summary121

Unit 5.2a - Database Administrator122

DBA Tools123

DBMS Product Evaluation123

Data Structures Supported123

Performance124

Tools124

Unit 5.2b - Security125

Granularity of DBMS Security126

DBMS-level Protection127

User-level Security for SQL127

Naming Hierarchy127

The GRANT command128

Unit 5.3 - Data Dictionary129

Benefits of a DDS129

DDS Facilities129

DD Information130

DD Management130

Management Objectives131

Advanced Facilities131

Management Advantages131

Management Disadvantages132

Tutorial - ER Diagram Examples 1-2133

Example 1133

Example 2133

Tutorial - ER Diagram Examples 3-5133

Example 3133

Example 4134

Example 5134

Multiple Choice - HOWTO135

The Answer Sheet135

Entering an answer136

Reason/Assertion136

Example136

Unit 1.1 - Introduction7

Database System7

Data7

Hardware8

Software8

Users8

Database Architecture8

External View10

Conceptual View10

Internal View11

Mappings11

DBMS12

Database Administrator12

DBA Tools13

Facilities and Limitations13

Data Independence14

Data Redundancy14

Data Integrity15

Unit 1.2 - SQL16

Database Models17

Relational Databases17

Relational Data Structure17

Domain and Integrity Constraints18

Menu Example18

External vs Logical19

Columns or Attributes19

Rows or Tuples19

Primary Keys19

Employee Table - Columns20

Jobhistory Table - Columns20

Foreign Keys20

SQL20

SQL Basics21

CREATE table employee21

CREATE Table Jobhistory21

SQL SELECT21

Comparison23

SELECT with BETWEEN23

Pattern Matching23

ORDER and DISTINCT23

Unit 1.3 - Logical Operators26

IN26

Other SELECT capabilities26

Simple COUNT examples26

Grouped COUNTs27

Joining Tables27

SELECT - Order of Evaluation29

One-to-Many Relationships29

Many-to-Many Relationships.29

Aliases30

Aliases with Self Joins30

Unit 1.4 - Subqueries32

Simple Example32

Subqueries with ANY, ALL32

Subqueries with IN, NOT IN32

Subqueries with EXISTS33

UNION of Subqueries33

Views33

View Manipulation34

VIEW update, insert and delete34

Other SQL Statements35

INSERT36

DELETE36

UPDATE36

Unit 2.1: Database Analysis38

Entity Relationship Modelling38

Database Analysis Life Cycle39

Three-level Database Model40

Entity Relationship Modelling41

Entities42

Attribute42

Keys43

Relationships43

Degree of a Relationship43

Degree of a Relationship44

Replacing ternary relationships44

Cardinality45

Optionality46

Entity Sets47

Confirming Correctness47

Deriving the relationship parameters47

Redundant relationships48

Redundant relationships example48

Splitting n:m Relationships48

Splitting n:m Relationships - Example49

Constructing an ER model - Entities49

Constructing an ER model - Attributes49

Constructing an ER model - Relationships50

Unit 2.2 - Entity Relationship Modelling - 251

Country Bus Company51

Entities51

Relationships51

Draw E-R Diagram52

Attributes52

Problems with ER Models53

Fan traps54

Chasm traps54

Enhanced ER Models (EER)55

Specialisation55

Generalisation56

Unit 2.3 - Mapping ER Models into Relations56

What is a relation?56

Foreign keys57

Preparing to map the ER model57

Mapping 1:1 relationships57

Mandatory at both ends58

When not to combine58

If not combined...58

Example58

Mandatory Optional59

Mandatory Optional - Subsume?60

Summary...60

Optional at both ends...60

Mapping 1:m relationships61

Mapping n:m relationships61

Summary62

Unit 2.4 - Advanced ER Mapping62

Mapping parallel relationships62

Mapping 1:m in unary relationships63

Mapping superclasses and subclasses64

Example64

Unit 3.1 - Normalisation66

Integrity Constraints66

What is normalisation?66

Student - an unnormalised table67

First Normal Form68

Student - Flattened Table70

Extend Primary Key70

Anomalies71

Decomposing the relation71

Record72

Student72

Functional dependency73

Second Normal Form73

Third Normal Form75

Summary: 1NF77

Summary: 2NF77

Summary: 3NF78

Unit 3.2 - Normalisation Continued78

Boyce-Codd Normal Form (BCNF)78

Normalisation to BCNF - Example 179

Summary - Example 182

Example 283

Problems BCNF overcomes84

Fourth Normal Form85

Example85

Fifth Normal Form86

Join Dependency Decomposition86

Spurious results87

Returning to the ER Model87

Unit 3.3 - Relational Algebra88

Terminology88

Operators - Write88

Operators - Retrieval89

Relational SELECT89

Relational PROJECT89

SELECT and PROJECT89

Set Operations - semantics89

SET Operations - requirements90

UNION Example90

INTERSECTION Example91

DIFFERENCE Example91

CARTESIAN PRODUCT91

CARTESIAN PRODUCT example92

JOIN Operator92

JOIN Example92

Natural Join92

OUTER JOINs93

OUTER JOIN example 193

OUTER JOIN example 294

Unit 3.4 - Relational Algebra - Example94

Symbolic Notation94

Usage95

Rename Operator95

Derivable Operators96

Equivalence96

Equivalences96

Comparing RA and SQL97

Comparing RA and SQL97

Unit 4.1 - Concurrency using Transactions98

Transactions98

Transaction Schedules98

Lost Update scenario.99

Uncommitted Dependency100

Inconsistency101

Serialisability101

Precedence Graph101

Precedence Graph : Method102

Example 1102

Example 2102

Unit 4.2 - Concurrency103

Locking103

Locking - Uncommitted Dependency103

Deadlock104

Deadlock Handling105

Deadlock Resolution106

Two-Phase Locking106

Other Database Consistency Methods106

Timestamping rules107

Unit 4.3 – Storage Structures108

The Physical Store108

Why not all Main Memory?108

Secondary Storage - Blocks108

Hard Drives109

DBMS Data Items109

File Organisations109

Storage Scenario110

Serial Organisation110

Sequential Organisation111

Hash Organisation111

Indexed Sequential Access Method112

ISAM Example112

B+ Tree Index112

B+ Tree Example113

Building a B+ Tree113

B+ Tree Build Example114

Index Structure and Access114

Costing Index and File Access115

Use of Indexes115

Unit 4.4 - Recovery116

Recovery: the dump117

Recovery: the transaction log117

Deferred Update117

Example118

Immediate Update119

Example119

Rollback120

Unit 5.1 - Embedded SQL121

Interactive SQL121

Embedded SQL121

SQL Precompiler121

Sharing Variables122

Connecting to the DBMS122

Queries producing a single row122

SELECT with a single result123

Cursors - SELECT many rows123

Fetching values123

Declaring and Opening a Cursor123

Program Example124

Summary124

Unit 5.2a - Database Administrator125

DBA Tools126

DBMS Product Evaluation126

Data Structures Supported126

Performance127

Tools127

Unit 5.2b - Security128

Granularity of DBMS Security129

DBMS-level Protection130

User-level Security for SQL130

Naming Hierarchy130

The GRANT command131

Unit 5.3 - Data Dictionary132

Benefits of a DDS132

DDS Facilities132

DD Information133

DD Management133

Management Objectives134

Advanced Facilities134

Management Advantages134

Management Disadvantages135

Tutorial - ER Diagram Examples 1-2136

Example 1136

Example 2136

Tutorial - ER Diagram Examples 3-5136

Example 3136

Example 4137

Example 5137

Multiple Choice - HOWTO138

The Answer Sheet138

Entering an answer139

Reason/Assertion139

Example139

This Document

This document is for use with a variety of Napier University modules, and forms a good introduction to the basics of database systems for university students. The modules at Napier which use this module include:

  • CO22001 – Database Systems. This is a 2nd year module for computing students.
  • CS22010 – Database Systems 2. This is the old name for CO22001.
  • CO72010 – Database Systems. This is a postgraduate module taught on some of our postgraduate conversion courses.

The notes are for use with both locally taught modules and those affiliated to Napier University. If you wish to use these notes for other purposes please let me know. Suggestions and corrections welcomed.

Dr Gordon Russell ( )

Acknowledgments:

Andrew Cumming
Ken Chisholm
Colin Hastie
Jim Murray
Alison Varey

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0//EN" "

/ Unit 1.1 - Introduction

Unit 1.1 - Introduction

Relational database systems have became increasingly popular single the late 1970's. They offer a powerful method for storing data in an application-independent manner. This means for many enterprises the database is at the core of the I.T. strategy. Developments can progress around a relatively stable database structure which is secure, reliable, efficient, and transparent.

In early systems, each suite of application programs had its own independent master file. The duplication of data over master files could lead to inconsistent data.

Efforts to use a common master file for a number of application programs resulted in problems of integrity and security. The production of new application programs could require amendments to existing application programs ­ `unproductive maintenance'.

Data structuring techniques, developed to exploit random access storage devices, increased the complexity of the insert, delete and update operations on data. As a first step towards a DBMS, packages of subroutines were introduced to reduce programmer effort in maintaining these data structures. However, the use of these packages still requires knowledge of the physical organization of the data.

Database System

A database system is a computer-based system to record and maintain information. The information concerned can be anything of significance to the organisation for whose use it is intended. A database system involves four major components: data, hardware, software and users.

Data

A database is a repository for data which, in general, is both integrated and shared. Integration means that the database may be thought of as a unification of several otherwise distinct files, with any redundancy among those files partially or wholly eliminated. The sharing of a database refers to the sharing of data by different users, in the sense that each of those users may have access to the same piece of data and may use it for different purposes. Any given user will normally be concerned with only a subset of the whole database.

Simplified view of a Database System

Hardware

The hardware involved consists of secondary storage devices (disks) on which the data resides, together with a processor, control units, channels and so forth. The database is assumed to be too large to be held in its entirety in the computer's primary storage, therefore there is a need for software to manage that data.

Software

The software that allows one or many persons to use and/or modify data stored in this database is a database management system (DBMS). A DBMS allows the user to deal with the data in abstract terms (logical data structure).

Users

There are three broad classes of user:

  1. the application programmer, responsible for writing programs in some high-level language such as COBOL, C++, etc.
  2. the end-user, who accesses the database via a query language
  3. the database administrator (DBA), who controls all operations on the database

Database Architecture

DBMSs do not all confirm to the same architecture.

  • The three-level architecture forms the basis of modern database architectures.
  • this is in agreement with the ANSI/SPARC study group on Database Management Systems.
  • ANSI/SPARC is the American National Standards Institute/Standard Planning and Requirement Committee).
  • The architecture for DBMSs is divided into three general levels:
  1. external
  2. conceptual
  3. internal

Three level database architecture

  1. the external level : concerned with the way individual users see the data
  2. the conceptual level : can be regarded as a community user view ­ a formal description of data of interest to the organisation, independent of any storage considerations.
  3. the internal level : concerned with the way in which the data is actually stored

External View

  • A user is anyone who needs to access some portion of the data. They may range from application programmers to casual users with ad­hoc queries. Each user has a language at his/her disposal.
  • The application programmer may use a high level language ( e.g. COBOL) while the casual user will probably use a query language.
  • Regardless of the language used, it will include a data sub­language DSL which is that subset of the language which is concerned with storage and retrieval of information in the database and may or may not be apparent to the user.
  • A DSL is a combination of two languages:
  1. a data definition language (DDL) - provides for the definition or description of database objects
  2. a data manipulation language (DML) - supports the manipulation or processing of database objects.
  • Each user sees the data in terms of an external view:
  • Defined by an external schema, consisting basically of descriptions of each of the various types of external record in that external view, and also a definition of the mapping between the external schema and the underlying conceptual schema.

Conceptual View

  • An abstract representation of the entire information content of the database.
  • It is in general a view of the data as it actually is, that is, it is a `model' of the `real­world'.
  • It consists of multiple occurrences of multiple types of conceptual record, defined in the conceptual schema.
  • To achieve data independence, the definitions of conceptual records must involve information content only.
  • storage structure is ignored
  • access strategy is ignored
  • The conceptual schema, as well as definitions, contains authorisation and validation procedures.

Internal View