pdf

1
Database Concepts
© Leo Mark
2
Database Concepts
© Leo Mark
DATABASE CONCEPTS
Leo Mark
College of Computing
Georgia Tech
(January 1999)
3
Database Concepts
© Leo Mark
Course Contents
● Introduction
● Database Terminology
● Data Model Overview
● Database Architecture
● Database Management System Architecture
● Database Capabilities
● People That Work With Databases
● The Database Market
● Emerging Database Technologies
● What You Will Be Able To Learn More About
4
Database Concepts
© Leo Mark
INTRODUCTION
● What a Database Is and Is Not
● Models of Reality
● Why use Models?
● A Map Is a Model of Reality
● A Message to Map Makers
● When to Use a DBMS?
● Data Modeling
● Process Modeling
● Database Design
● Abstraction
5
Database Concepts
© Leo Mark
What a Database Is and Is Not
● your personal address book in a Word document
● a collection of Word documents
● a collection of Excel Spreadsheets
● a very large flat file on which you run some
statistical analysis functions
● data collected, maintained, and used in airline
reservation
● data used to support the launch of a space shuttle
The word database is commonly used to refer
to any of the following:
6
Database Concepts
© Leo Mark
Models of Reality
REALITY
• structures
• processes
DATABASE SYSTEM
DATABASE
DML
DDL
● A database is a model of structures of reality
● The use of a database reflect processes of reality
● A database system is a software system which
supports the definition and use of a database
● DDL: Data Definition Language
● DML: Data Manipulation Language
7
Database Concepts
© Leo Mark
Why Use Models?
● Models can be useful when we want to
examine or manage part of the real world
● The costs of using a model are often
considerably lower than the costs of using or
experimenting with the real world itself
● Examples:
– airplane simulator
– nuclear power plant simulator
– flood warning system
– model of US economy
– model of a heat reservoir
– map
8
Database Concepts
© Leo Mark
A Map Is a Model of Reality
9
Database Concepts
© Leo Mark
A Message to Map Makers
● A model is a means of communication
● Users of a model must have a certain amount
of knowledge in common
● A model on emphasized selected aspects
● A model is described in some language
● A model can be erroneous
● A message to map makers: “Highways are
not painted red, rivers don’t have county lines
ruing down the middle, and you can’t see
contour lines on a mountain” [Kent 78]
10
Database Concepts
© Leo Mark
Use a DBMS when
this is important
● persistent storage of data
● centralized control of data
● control of redundancy
● control of consistency and
integrity
● multiple user support
● sharing of data
● data documentation
● data independence
● control of access and
security
● backup and recovery
Do not use a
DBMS when
● the initial investment in
hardware, software, and
training is too high
● the generality a DBMS
provides is not needed
● the overhead for security,
concurrency control, and
recovery is too high
● data and applications are
simple and stable
● real-time requirements
caot be met by it
● multiple user access is not
needed
11
Database Concepts
© Leo Mark
Data Modeling
REALITY
• structures
• processes
DATABASE SYSTEM
MODEL
data modeling
● The model represents a perception of structures of
reality
● The data modeling process is to fix a perception of
structures of reality and represent this perception
● In the data modeling process we select aspects and
we abstract
12
Database Concepts
© Leo Mark
Process Modeling
REALITY
• structures
• processes
DATABASE SYSTEM
MODEL
process modeling
● The use of the model reflects processes of reality
● Processes may be represented by programs with
embedded database queries and updates
● Processes may be represented by ad-hoc database
queries and updates at run-time
DML DML
PRO
G
13
Database Concepts
© Leo Mark
Database Design
● is a model of structures of reality
● supports queries and updates modeling
processes of reality
● runs efficiently
The purpose of database design is to create a
database which
14
Database Concepts
© Leo Mark
Abstraction
● Classification
● Aggregation
● Generalization
It is very important that the language used for
data representation supports abstraction
We will discuss three kinds of abstraction:
15
Database Concepts
© Leo Mark
Classification
In a classification we form a concept in a way
which allows us to decide whether or not a
given phenomena is a member of the extension
of the concept.
CUSTOMER
Tom Ed Nick ... Liz Joe Louise
16
Database Concepts
© Leo Mark
Aggregation
In an aggregation we form a concept from existing
concepts. The phenomena that are members of
the new concept’s extension are composed of
phenomena from the extensions of the existing
concepts
AIRPL
ANE
COCKP
IT
ENGIN
E
WING
17
Database Concepts
© Leo Mark
Generalization
In a generalization we form a new concept by
emphasizing common aspects of existing concepts,
leaving out special aspects
CUSTO
MER
ECONO
MY
CLASS
BUSIN
ESS
CLASS
1
STCLA
SS
18
Database Concepts
© Leo Mark
Generalization (cont.)
CUSTO
MER
BUSIN
ESS
CLASS
1
STCLA
SS
Subclasses may overlap
Subclasses may have multiple superclasses
MOTORIZED
VEHICLES
AIRBORNE
VEHICLES
TRUCKS HELICOPTERS GLIDERS
19
Database Concepts
© Leo Mark
Relationships Between Abstractions
T T T
O O O
aggregation generalization classification
Abstraction Concretization
classification exemplification
aggregation decomposition
generalization specialization
intension
extension
20
Database Concepts
© Leo Mark
DATABASE TERMINOLOGY
● Data Models
● Keys and Identifiers
● Integrity and Consistency
● Triggers and Stored Procedures
● Null Values
● Normalization
● Surrogates - Things and Names
21
Database Concepts
© Leo Mark
Data Model
● data structures
● integrity constraints
● operations
A data model consists of notations for
expressing:
22
Database Concepts
© Leo Mark
Data Model - Data Structures
● attribute types
● entity types
● relationship types
FLIGHT# AIRLINE WEEKDAY PRICE
FLIGHT-SCHEDULE
101 delta mo 156
545 american we 110
912 scandinavian fr 450
242 usair mo 231
DEPT-AIRPORT
FLIGHT# AIRPORT-CODE
101 atl
912 cph
545 lax
All data models have notation for defining:
23
Database Concepts
© Leo Mark
Data Model - Constraints
● Static constraints apply to database state
● Dynamic constraints apply to change of database state
● E.g., “All FLIGHT-SCHEDULE entities must have precisely
one DEPT-AIRPORT relationship
FLIGHT# AIRLINE WEEKDAY PRICE
FLIGHT-SCHEDULE
101 delta mo 156
545 american we 110
912 scandinavian fr 450
242 usair mo 231
Constraints express rules that caot be expressed
by the data structures alone:
DEPT-AIRPORT
FLIGHT# AIRPORT-CODE
101 atl
912 cph
545 lax
242 bos
24
Database Concepts
© Leo Mark
Data Model - Operations
● insert FLIGHT-SCHEDULE(97, delta, tu, 258);
insert DEPT-AIRPORT(97, atl);
● select FLIGHT#, WEEKDAY
from FLIGHT-SCHEDULE
where AIRLINE=‘delta’;
Operations support change and retrieval of data:
FLIGHT# AIRLINE WEEKDAY PRICE
FLIGHT-SCHEDULE
101 delta mo 156
545 american we 110
912 scandinavian fr 450
242 usair mo 231
97 delta tu 258
DEPT-AIRPORT
FLIGHT# AIRPORT-CODE
101 atl
912 cph
545 lax
242 bos
97 atl
25
Database Concepts
© Leo Mark
Data Model - Operations from Programs
declare C cursor for
select FLIGHT#, WEEKDAY
from FLIGHT-SCHEDULE
where AIRLINE=‘delta’;
open C;
repeat
fetch C into :FLIGHT#, :WEEKDAY;
do your thing;
until done;
close C;
FLIGHT# AIRLINE WEEKDAY PRICE
FLIGHT-SCHEDULE
101 delta mo 156
545 american we 110
912 scandinavian fr 450
242 usair mo 231
97 delta tu 258
26
Database Concepts
© Leo Mark
Keys and Identifiers
● A key on FLIGHT# in FLIGHT-SCHEDULE will force all
FLIGHT#’s to be unique in FLIGHT-SCHEDULE
● Consider the following keys on DEPT-AIRPORT:
Keys (or identifiers) are uniqueness constraints
FLIGHT# AIRPORT-CODE FLIGHT# AIRPORT-CODE FLIGHT# AIRPORT-CODE FLIGHT# AIRPORT-CODE
DEPT-AIRPORT
FLIGHT# AIRPORT-CODE
101 atl
912 cph
545 lax
242 bos
FLIGHT# AIRLINE WEEKDAY PRICE
FLIGHT-SCHEDULE
101 delta mo 156
545 american we 110
912 scandinavian fr 450
242 usair mo 231
27
Database Concepts
© Leo Mark
Integrity and Consistency
● Integrity: does the model reflect reality well?
● Consistency: is the model without internal conflicts?
● a FLIGHT# in FLIGHT-SCHEDULE caot be null because it
models the existence of an entity in the real world
● a FLIGHT# in DEPT-AIRPORT must exist in FLIGHT-SCHEDULE
because it doesn’t make sense for a non-existing
FLIGHT-SCHEDULE entity to have a DEPT-AIRPORT
DEPT-AIRPORT
FLIGHT# AIRPORT-CODE
101 atl
912 cph
545 lax
242 bos
FLIGHT# AIRLINE WEEKDAY PRICE
FLIGHT-SCHEDULE
101 delta mo 156
545 american we 110
912 scandinavian fr 450
242 usair mo 231
28
Database Concepts
© Leo Mark
Triggers and Stored Procedures
● Triggers can be defined to enforce constraints on a
database, e.g.,
● DEFINE TRIGGER DELETE-FLIGHT-SCHEDULE
ON DELETE FROM FLIGHT-SCHEDULE WHERE FLIGHT#=‘X’
ACTION DELETE FROM DEPT-AIRPORT WHERE FLIGHT#=‘X’;
DEPT-AIRPORT
FLIGHT# AIRPORT-CODE
101 atl
912 cph
545 lax
242 bos
FLIGHT# AIRLINE WEEKDAY PRICE
FLIGHT-SCHEDULE
101 delta mo 156
545 american we 110
912 scandinavian fr 450
242 usair mo 231
29
Database Concepts
© Leo Mark
Null Values
123-45-6789
234-56-7890
345-67-8901
CUSTOMER
Lisa Smith
George Foreman
unknown
Lisa Jones
inapplicable
Mary Blake
inapplicable
drafted
inapplicable
CUSTOMER# NAME MAIDEN NAME DRAFT STATUS
● Null-value unknown reflects that the attribute does
apply, but the value is currently unknown. That’s ok!
● Null-value inapplicable indicates that the attribute does
not apply. That’s bad!
● Null-value inapplicable results from the direct use of
“catch all forms” in database design.
● “Catch all forms” are ok in reality, but detrimental in
database design.
30
Database Concepts
© Leo Mark
Normalization
FLIGHT# AIRLINE PRICE
FLIGHT-SCHEDULE
101 delta 156
545 american 110
912 scandinavian 450
FLIGHT# AIRLINE WEEKDAY PRICE
FLIGHT-SCHEDULE
101 delta mo
545 american mo 110
912 scandinavian fr 450
156
101 delta fr 156
545 american we 110
545 american fr 110
FLIGHT# AIRLINE WEEKDAYS PRICE
FLIGHT-SCHEDULE
101 delta mo,fr 156
545 american mo,we,fr 110
912 scandinavian fr 450
FLIGHT# WEEKDAY
FLIGHT-WEEKDAY
101 mo
545 mo
912 fr
101 fr
545 we
545 fr
uormalized
redundant
just
right!
31
Database Concepts
© Leo Mark
Surrogates - Things and Names
name custom#
addr customer
name custom#
addr customer
reality
reality
customer
customer
custom# name addr
custom# name addr
customer
name-based representation
surrogate-based representation
● name-based: a thing is what we know about it
● surrogate-based: “Das ding an sich” [Kant]
● surrogates are system-generated, unique, internal identifiers
32
Database Concepts
© Leo Mark
DATA MODEL OVERVIEW
● ER-Model
● Hierarchical Model
● Network Model
● Inverted Model - ADABAS
● Relational Model
● Object-Oriented Model(s)
33
Database Concepts
© Leo Mark
ER-Model
● Data Structures
● Integrity Constraints
● Operations
● The ER-Model is extremely successful as a
database design model
● Translation algorithms to many data models
● Commercial database design tools, e.g., ERwin
No generally accepted query language
● No database system is based on the model
34
Database Concepts
© Leo Mark
ER-Model - Data Structures
entity type
relationship
type
attribute
multivalued
attribute
derived
attribute
composite
attribute
subset
relationship
type
35
Database Concepts
© Leo Mark
ER-Model - Integrity Constraints
A
E
E1 E2 E3
E1 R E2 1 n
E1 R E2
E1 R E2
(min,max)
E1 R E2
cardinality: 1:n for E1:E2 in R
(min,max) participation of E2 in R
total participation of E2 in R
weak entity type E2; identifying
relationship type R
key attribute
d
x
p
disjoint
exclusion
partition
36
Database Concepts
© Leo Mark
ER Model - Example
de
pt
air
por
t
date
internation
al
flight
domestic
flight
p
flight
instance
flight
schedule
ins
tan
ce
of
arr
iv
air
por
t
airport
1


1
street
dept
time
airport
code
arriv
time
city zip
airport
addr
airport
name
res
erv
atio

n n
1

customer
flight#
custom
er
name
custom
er#
seat#
week
days
visa
requir
ed
37
Database Concepts
© Leo Mark
ER-Model - Operations
● Several navigational query languages have
been proposed
● A closed query language as powerful as
relational languages has not been developed
● None of the proposed query languages has
been generally accepted
38
Database Concepts
© Leo Mark
Hierarchical Model
● Data Structures
● Integrity Constraints
● Operations
● Commercial systems include IBM’s IMS, MRI’s
System-2000 (now sold by SAS), and CDC’s
MARS IV
39
Database Concepts
© Leo Mark
Hierarchical Model - Data Structures
● record types: flight-schedule, flight-instance, etc.
● field types: flight#, date, customer#, etc.
● parent-child relationship types (1:n only!!):
(flight-sched,flight-inst), (flight-inst,customer)
● one record type is the root, all other record types is
a child of one parent record type only
● substantial duplication of customer instances
● asymmetrical model of n:m relationship types
flight-sched
customer
customer# customer name
flight-inst
date
dept-airp
airport-code
arriv-airp
airport-code
flight#
40
Database Concepts
© Leo Mark
Hierarchical Model - Data Structures
- virtual records
● duplication of customer instances avoided
● still asymmetrical model of n:m relationship types
customer
customer# customer name
flight-inst
flight-sched
date
dept-airp
airport-code
arriv-airp
airport-code
flight#
customerpointer
P
41
Database Concepts
© Leo Mark
Hierarchical Model
- Operations
flight-sched
customer
customer# customer name
flight-inst
date
dept-airp
airport-code
arriv-airp
airport-code
flight#
GET UNIQUE flight-sched (flight#=‘912’) [search flight-sched; get first such flight-sched]
GET UNIQUE flight-sched [for each flight-sched
flight-inst (date=‘102298’) for each flight-inst with date=102298
customer (name=‘Jensen’) for each customer with name=Jensen, get the first one]
GET UNIQUE flight-sched [for each flight-sched
flight-inst (date=‘102298’) for each flight-inst with date=102298, get the first
GET NEXT flight-inst get the next flight-inst, whatever the date]
GET UNIQUE flight-sched [for each flight-sched
flight-inst (date=102298’) for each flight-inst get the first with date=102298
customer (name=‘Jensen’) for each customer with name=Jensen, get the first one
GET NEXT WITHIN PARENT customer get the next customer, whatever his name, but only
on that flight-inst]
42
Database Concepts
© Leo Mark
Network Model
● Data Structures
● Integrity Constraints
● Operations
● Based on the CODASYL-DBTG 1971 report
● Commercial systems include, CA-IDMS and
DMS-1100
43
Database Concepts
© Leo Mark
Network Model - Data Structures
reservation
flight# date customer#
flight-schedule
flight#
customer
customer# customer name
FR
CR
R1 R2 R3 R4 R5 R6
F1 F2
C1 C4
Type diagram
Bachman Diagram
Occurrence diagram
The Spaghetti Model
● owner record types: flight-schedule, customer
● member record type: reservations
● DBTG-set types: FR, CR
● n-m relationships caot be modeled directly
● recursive relationships caot be modeled directly
44
Database Concepts
© Leo Mark
Network Model - Integrity
Constraints
● set retention options:
– fixed
– mandatory
– optional
● set insertion options:
– automatic
– manual
reservation
flight# date customer#
flight-schedule
flight#
customer
customer# customer name
FR
CR
flight-schedule
flight#
● keys
● checks reservation
flight# date customer# price
check is price>100
FR and CR are fixed and automatic
45
Database Concepts
© Leo Mark
Network Model - Operations
● The operations in the Network Model are
generic, navigational, and procedural
(1) find flight-schedule where flight#=F2
(2) find first reservation of FR
(3) find next reservation of FR
(4) find owner of CR
R1 R2 R3 R4 R5 R6
F1 F2
C1 C4
FR
CR
(F2)
(R4)
(R5)
(C4)
query: currency indicators:
46
Database Concepts
© Leo Mark
Network Model - Operations
● navigation is cumbersome; tuple-at-a-time
● many different currency indicators
● multiple copies of currency indicators may be
needed if the same path is traveled twice
● external schemata are only sub-schemata
47
Database Concepts
© Leo Mark
Inverted Model - ADABAS
● Data Structures
● Integrity Constraints
● Operations
48
Database Concepts
© Leo Mark
Relational Model
● Data Structures
● Integrity Constraints
● Operations
● Commercial systems include: ORACLE, DB2,
SYBASE, INFORMIX, INGRES, SQL Server
● Dominates the database market on all
platforms
49
Database Concepts
© Leo Mark
Relational Model - Data Structures
● domains
● attributes
● relations
flight-schedule
flight#:
integer
airline:
char(20)
weekday:
char(2)
price:
dec(6,2)
relation name
attribute names
domain names
50
Database Concepts
© Leo Mark
Relational Model - Integrity
Constraints
● Keys
● Primary Keys
● Entity Integrity
● Referential Integrity
reservation
flight# date customer#
flight-schedule
flight#
p
customer
customer# customer name
p
51
Database Concepts
© Leo Mark
Relational Model - Operations
● Powerful set-oriented query languages
● Relational Algebra: procedural; describes how
to compute a query; operators like JOIN,
SELECT, PROJECT
● Relational Calculus: declarative; describes
the desired result, e.g. SQL, QBE
● insert, delete, and update capabilities
52
Database Concepts
© Leo Mark
Relational Model - Operations
● tuple calculus example (SQL)
select flight#, date
from reservation R, customer C
where R.customer#=C.customer#
and customer-name=‘LEO’;
● algebra example (ISBL)
((reservation join customer) where
customer-name=‘LEO’) [flight#, date];
● domain calculus example (QBE)
customer
customer# customer-nam
e _c LEO
date
reservation
flight# customer#
.P .P _c
53
Database Concepts
© Leo Mark
Object-Oriented Model(s)
● based on the object-oriented paradigm,
e.g., Simula, Smalltalk, C++, Java
● area is in a state of flux
● object-oriented model has object-oriented
repository model; adds persistence and database
capabilities; (see ODMG-93, ODL, OQL)
● object-oriented commercial systems include
GemStone, Ontos, Orion-2, Statice, Versant, O2
● object-relational model has relational repository
model; adds object-oriented features; (see SQL3)
● object-relational commercial systems include
Starburst, POSTGRES
54
Database Concepts
© Leo Mark
Object-Oriented Paradigm
● object class
● object attributes, primitive types, values
● object interface, methods; body, implementations
● messages; invoke methods; give method name and
parameters; return a value
● encapsulation
● visible and hidden attributes and methods
● object instance; object constructor & destructor
● object identifier, immutable
● complex objects; multimedia objects; extensible
type system
● subclasses; inheritance; multiple inheritance
● operator overloading
● references represent relationships
● transient & persistent objects
55
Database Concepts
© Leo Mark
class flight-schedule {
type tuple (flight#: integer,
weekdays: set ( weekday: enumeration {mo,tu,we,th,fr,sa,su})
dept-airport: airport, arriv-airport: airport)
method reschedule(new-dept: airport, new-arriv: airport)}
class international-flight inherit flight-schedule {
type tuple (visa-required:string)
method change-visa-requirement(v: string): boolean}
/* the reschedule method is inherited by international-flight; */
/* when reschedule is invoked in international-flight it may */
/* also invoke change-visa-requirement */
Object-Oriented Model - Structures
O2
-like syntax
56
Database Concepts
© Leo Mark
class flight-instance {
type tuple (flight-date: tuple ( year: integer, month: integer, day: integer);
instance-of: flight-schedule,
passengers: set (customer) inv customer::reservations)
method add-passenger(new-passenger:customer):boolean,
/*adds to passengers; invokes customer.make-reservation */
remove-passenger(passenger: customer):boolean}
/*removes from passengers; invokes customer.cancel-reservation*/
class customer {
type tuple (customer#: integer,
customer-name: tuple ( fname: string, lname: string)
reservations: set (flight-instance) inv flight-instance::passengers)
method make-reservation(new-reservation: flight-instance): boolean,
cancel-reservation(reservation: flight-instance): boolean}
57
Database Concepts
© Leo Mark
Object-Oriented Model - Updates
class customer {
type tuple (customer#: integer,
customer-name: tuple ( fname: string, lname: string)
reservations: set (flight-instance) inv flight-instance::passengers)
main () {
transaction::begin();
all-customers: set( customer); /*makes persistent root to hold all customers */
customer c= new customer; /*creates new customer object */
c= tuple (customer#: “111223333”,
customer-name: tuple( fname: “Leo”, lname: “Mark”));
all-customers += set( c); /*c becomes persistent by attaching to root */
transaction::commit();}
O2
-like syntax
58
Database Concepts
© Leo Mark
Object-Oriented Model - Queries
“Find the customer#’s of all customers with first name Leo”
select tuple (c#: c.customer#)
from c in customer
where c.customer-name.fname = “Leo”;
“Find passenger lists, each with a flight# and a list of customer names, for
flights out of Atlanta on October 22, 1998”
select tuple(flight#: f.instance-of.flight#,
passengers: select( tuple( c.customer#, c.customer-name.lname)))
from f in flight-instance, c in f.passengers
where f.flight-date=(1998, 10, 22)
and f.instance-of.dept-airport.airport-code=“Atlanta”;
O2
-like syntax
59
Database Concepts
© Leo Mark
DATABASE ARCHITECTURE
● ANSI/SPARC 3-Level DB Architecture
● Metadata - What is it? Why is it important?
● ISO Information Resource Dictionary System
(ISO-IRDS)
60
Database Concepts
© Leo Mark
ANSI/SPARC 3-Level DB
Architecture - separating concerns
database system
schema
data
database
database system
DDL
DML
● a database is divided into schema and data
● the schema describes the intension (types)
● the data describes the extension (data)
● Why? Effective! Efficient!
61
Database Concepts
© Leo Mark
ANSI/SPARC 3-Level DB
Architecture - separating concerns
schema
data
schema
conceptual
schema internal schema
data
internal schema
data
external schema
62
Database Concepts
© Leo Mark
ANSI/SPARC 3-Level DB Architecture
external
schema1
external
schema2
external
schema3
conceptual
schema
internal
schema
database
• external schema:
use of data
• conceptual schema:
meaning of data
• internal schema:
storage of data
63
Database Concepts
© Leo Mark
Conceptual Schema
● Describes all conceptually relevant, general,
time-invariant structural aspects of the universe
of discourse
● Excludes aspects of data representation and
physical organization, and access
NAME ADDR SEX AGE
CUSTOMER
● An object-oriented conceptual schema would
also describe all process aspects
64
Database Concepts
© Leo Mark
External Schema
● Describes parts of the information in the
conceptual schema in a form convenient to a
particular user group’s view
● Is derived from the conceptual schema
NAME ADDR SEX AGE
CUSTOMER
NAME ADDR
MALE-TEEN-CUSTOMER
TEEN-CUSTOMER(X, Y) =
CUSTOMER(X, Y, S, A)
WHERE SEX=M AND 1265
Database Concepts
© Leo Mark
Internal Schema
● Describes how the information described in the
conceptual schema is physically represented to
provide the overall best performance
NAME ADDR SEX AGE
CUSTOMER
NAME ADDR SEX AGE
CUSTOMER
B
+
-tree on
AGE NAME PTR
index on
NAME
66
Database Concepts
© Leo Mark
Physical Data Independence
external
schema1
external
schema2
external
schema3
conceptual
schema
internal
schema
database
Physical data independence
is a measure of how much
the internal schema can
change without affecting the
application programs
67
Database Concepts
© Leo Mark
Logical Data Independence
external
schema1
external
schema2
external
schema3
conceptual
schema
internal
schema
database
Logical data independence is
a measure of how much the
conceptual schema can
change without affecting the
application programs
68
Database Concepts
© Leo Mark
Schema Compiler
compiler
metadata
schemata
The schema compiler compiles
schemata and stores them in the
metadatabase
• Catalog
• Data Dictionary
• Metadatabase
69
Database Concepts
© Leo Mark
Query Transformer
metadata
query
transformer
DML
query
data
Uses metadata to transform a
query at the external schema
level to a query at the storage
level
70
Database Concepts
© Leo Mark
ANSI/SPARC DBMS Framework
enterprise
administrator
database
administrator
application
system
administrator
conceptual
schema
processor
internal
schema
processor
external
schema
processor
storage
internal
transformer
internal
conceptual
transformer
conceptual
external
transformer
metadata
data user
1
3 3
13 2 4
14 5
34 36 38
21 30 31 12
schema compiler query transformer
71
Database Concepts
© Leo Mark
Metadata - What is it?
● System metadata:
– Where data came from
– How data were changed
– How data are stored
– How data are mapped
– Who owns data
– Who can access data
– Data usage history
– Data usage statistics
● Business metadata:
– What data are available
– Where data are located
– What the data mean
– How to access the data
– Predefined reports
– Predefined queries
– How current the data are
Metadata - Why is it important?
● System metadata are critical in a DBMS
● Business metadata are critical in a data warehouse
72
Database Concepts
© Leo Mark
ISO-IRDS - Why?
● Are metadata different from data?
● Are metadata and data stored separately?
● Are metadata and data described by different
models?
● Is there a schema for metadata? A
metaschema?
● Are metadata and data changed through
different interfaces?
● Can a schema be changed on-line?
● How does a schema change affect data?
73
Database Concepts
© Leo Mark
ISO-IRDS Architecture
DL
metaschema
data dictionary
schema
data dictionary
data raw formatted application data
data dictionary data; schema for
application data; data about
application data
data dictionary schema; contains copy
of metaschema; schema for format
definitions; schema for data about
application data
metaschema; describes all schemata
that can be defined in the data model
data
74
Database Concepts
© Leo Mark
ISO-IRDS - example
metaschema
data dictionary
schema
data dictionary
data
relations
access-rights
relations
supplier
rel-name
rel-name
att-name
att-name
dom-name
dom-name
(u1, supplier, insert)
(u2, supplier, delete)
user relation operation
s# sname location
(s1, smith, london)
(s2, jones, boston)
75
Database Concepts
© Leo Mark
DATABASE MANAGEMENT
SYSTEM ARCHITECTURE
● Teleprocessing Database
● File-Sharing Database
● Client-Server Database - Basic
● Client-Server Database - w/Caching
● Distributed Database
● Federated Database
● Multi-Database
● Parallel Databases
76
Database Concepts
© Leo Mark
Teleprocessing Database
OSTP
AP1 AP2 AP3
DBMS
OSDB
DB
dumb
terminal
dumb
terminal
dumb
terminal
communication
lines
mainframe
database
77
Database Concepts
© Leo Mark
Teleprocessing Database -
characteristics
● Dumb terminals
● APs, DBMS, and DB reside on central computer
● Communication lines are typically phone lines
● Screen formatting transmitted via communication
lines
● User interface character oriented and primitive
● Dumb terminals are gradually being replaced by
micros
78
Database Concepts
© Leo Mark
File-Sharing Database
OSNET
AP1 AP2 AP3
DBMS
OSDB
DB
LAN
database
OSNET OSNET
DBMS
file server
micro
micros
79
Database Concepts
© Leo Mark
File-Sharing Database -
characteristics
● APs and DBMS on client micros
● File-Server on server micro
● Clients and file-server communicate via LAN
● Substantial traffic on LAN because large files
(and indices) must be sent to DBMS on
clients for processing
● Substantial lock contention for extended
periods of time for the same reason
● Good for extensive query processing on
downloaded snapshot data
● Bad for high-volume transaction processing
80
Database Concepts
© Leo Mark
Client-Server Database - Basic
AP1 AP2 AP3
DBMS
OSDB
DB
micro(s) or
mainframe
database
OSNET
OSNET OSNET
LAN
micros
81
Database Concepts
© Leo Mark
Client-Server Database - Basic -
characteristics
● APs on client micros
● Database-server on micro or mainframe
● Multiple servers possible; no data replication
● Clients and database-server communicate via
LAN
● Considerably less traffic on LAN than with
file-server
● Considerably less lock contention than with
file-server
82
Database Concepts
© Leo Mark
Client-Server Database - w/Caching
AP1 AP2 AP3
DBMS
OSDB
DB
micro(s) or
mainframe
database
OSNET
OSNET OSNET
LAN
micros
DBMS DBMS
DB DB
83
Database Concepts
© Leo Mark
Client-Server Database -
w/Caching - characteristics
● DBMS on server and clients
● Database-server is primary update site
● Downloaded queries are cached on clients
● Change logs are downloaded on demand
● Cached queries are updated incrementally
● Less traffic on LAN than with basic
client-server database because only initial
query result is downloaded followed by
change logs
● Less lock contention than with basic
client-server database for same reason
84
Database Concepts
© Leo Mark
Distributed Database
AP1 AP2 AP3
OSNET&DB OSNET&DB
micros(s) or
mainframes DDBMS DDBMS
DB DB DB
network
conceptual
internal
external external external
85
Database Concepts
© Leo Mark
Distributed Database -
characteristics
● APs and DDBMS on multiple micros or mainframes
● One distributed database
● Communication via LAN or WAN
● Horizontal and/or vertical data fragmentation
● Replicated or non-replicated fragment allocation
● Fragmentation and replication transparency
● Data replication improves query processing
● Data replication increases lock contention and
slows down update transactions
86
Database Concepts
© Leo Mark
Distributed Database - Alternatives
D
C
B
A
B
A
D
C
B
A
D
C
B
A C
D
C
partitioned
non-replicated
non-partitioned
replicated
partitioned
replicated
+ - increasing parallelism, independence, flexibility, availability increasing cost, complexity, difficulty of control, security risk
87
Database Concepts
© Leo Mark
Federated Database
AP1 AP2 AP3
OSNET&DB OSNET&DB
micros(s) or
mainframes DDBMS DDBMS
DB DB DB
network
internal1
conceptual1
conceptual2
internal2
conceptual3
internal3
export
schema1
export
schema3
export
schema2
federation
schema
88
Database Concepts
© Leo Mark
Federated Database -
characteristics
● Each federate has a set of APs, a DDBMS,
and a DB
● Part of a federate’s database is exported,
i.e., accessible to the federation
● The union of the exported databases
constitutes the federated database
● Federates will respond to query and update
requests from other federates
● Federates have more autonomy than with a
traditional distributed database
89
Database Concepts
© Leo Mark
Multi-Database
AP1 AP2 AP3
OSNET&DB OSNET&DB
micros(s) or
mainframes MULTI-DBMS MULTI-DBMS
DB DB DB
network, e.g
WWW
internal1
conceptual1
conceptual2
internal2
conceptual3
internal3
90
Database Concepts
© Leo Mark
Multi-Database - characteristics
● A multi-database is a distributed database
without a shared schema
● A multi-DBMS provides a language for
accessing multiple databases from its APs
● A multi-DBMS accesses other databases via
a network, like the www
● Participants in a multi-database may respond
to query and update requests from other
participants
● Participants in a multi-database have the
highest possible level of autonomy
91
Database Concepts
© Leo Mark
Parallel Databases
● A database in which a single query may be
executed by multiple processors working
together in parallel
● There are three types of systems:
– Shared memory
– Shared disk
– Shared nothing
92
Database Concepts
© Leo Mark
Parallel Databases - Shared Memory
● processors share memory via
bus
● extremely efficient processor
communication via memory
writes
● bus becomes the bottleneck
● not scalable beyond 32 or 64
processors
P processor
M memory
disk
P
M
P
P
P
93
Database Concepts
© Leo Mark
Parallel Databases - Shared Disk
● processors share disk via
intercoection network
● memory bus not a bottleneck
● fault tolerance wrt. processor
or memory failure
● scales better than shared
memory
● intercoection network to
disk subsystem is a bottleneck
● used in ORACLE Rdb
P
P
P
P
M
M
M
M
94
Database Concepts
© Leo Mark
Parallel Databases - Shared Nothing
● scales better than shared memory
and shared disk
● main drawbacks:
– higher processor communication cost
– higher cost of non-local disk access
● used in the Teradata database
machine
M P
M P
M P
M P