Transcript Chapter 8. Object-Oriented Databases

OBJECT-ORIENTATION
by
Khoshafian and Abnous
Chap. 8 Object-Oriented Databases
서울대학교 컴퓨터공학부
객체지향시스템연구실
snu oopsla lab
교수 김 형 주
1
Contents







Introduction
Foundation and Evolution of OODBs
Persistence in OODBs
Transactions & Concurrency Control in OODBs
Recovery in OODBs
Versioning
Client/Server Architecture and OODBs
2
Introduction
Object-Oriented Databases
Object Orientation
Abstract Data Typing
Inheritance
Object Identity
Database Capabilities
Persistence
Concurrency
Transactions
Recovery
Querying
Versioning
Integrity
Security
Performance
3
Overview of DBMS Concepts(1)

Persistence


Transactions


the ability of objects to persist different program invocations
units are executed either entirely or not at all (atomicity).
Concurrency control

to guarantee database and transaction consistency
4
Overview of DBMS Concepts(2)

Recovery

three types of failures:




transaction failure
system failure
media failure
Querying

queries are used to select subsets and subobjects from
database collection objects or sets
5
Overview of DBMS Concepts(3)

Versioning


Integrity


consists of tools & constructs to automate or simplify the
construction & organization of versions or configuration
the predicates that capture the consistency of a database
Security


Encryption algorithms
User access control mechanism
6
Overview of DBMS Concepts(4)

Performance issues



indexes or accelerators
clustering techniques
query optimization
7
Approaches to OODB(1)

Novel database data model/data language approach



the most aggressive approach for incorporating OO
capabilities into DB
ODMG93: ODL, OQL. OML
Extending an existing database language with objectoriented capabilities



e.g. extending SQL with object-oriented constructs
Intelliget SQL
UniSQL
8
Approaches to OODB(2)

Extending an existing object-oriented programming
language with database capabilities



e.g. OODB extensions have been incorporated in C++ and
Smalltalk as language extension
Gemstone’s OPAL (Smalltalk extension)
Providing extendible object-oriented database
management system libraries


C++ client library for database management
Ontos, Versant
9
Approaches to OODB(3)

Embedding object-oriented database language
constructs in a host language


e.g. O2 provides embedded extensions for C and Basic
Application-specific products with an underlying
object-oriented DBMS


Echelon: OODBMS for XML
Multimedia content server
10
Approaches to OODBs: Summary






Novel database data model/data language approach
Extending an existing database languages with OO capabilities
Extending an existing OO programming language with database
capabilities
Providing extendible OODBMS libraries
Embedding OODB language constructs in a host language
Application-specific products with an underlying OODBMS
11
Contents







Introduction
Foundation and Evolution of OODBs
Persistence in OODBs
Transactions & Concurrency Control in OODBs
Recovery in OODBs
Versioning
Client/Server Architecture and OODBs
12
Foundation and Evolution of OODBs





The hierarchical data model
The network data model
The relational data model
Set-and-Tuple complex object models
Semantic data models
13
Hierarchical Data Model

This model represents the structures of the persistent
DB



as a collection of tree
node ( a set of objects of the same type )
relationship ( one-to-many (parent: child) )

70’s: IBM IMS

COBOL, PL/I
14
Parent
Child #1
………….
Child #n
< The hierarchical data model >
15
Desktop 2
Desktop 1
Folder 13
Folder 12
Folder 11
Document 112
Document 111
A hierarchical representation of
desktops, folders, documents
16
Network Model

This model is more general than the hierarchical
model.

same record type can be


owner (parent)
member (child)

70’s: System 2000

COBOL, PL/I
17
Owner #1
………………..
Owner #n
Member
< The network model >
18
Desktop
1
N
Contains
1
Drawer
N
1
Contains
N
Contains
Contains
1
N
Folder
Cabinet
1-to-many relationships supported directly by
the network model
19
Relational Model

Navigational (how)


Declarative (what)




in a relational DB
Constitution of RDB


in a hierarchical or a navigational DB
relation(table) : row+column
1970, E.F. Codd (IBM)
Relational Calculus, Relational Algebra
1976: Ingres(UC Berkely), System/R(IBM SanJose)
20
Columns
C1 C2
CN
Folders
Desktops
Rows
Documents
Intelligent Office Tables
Relational DB for Intelligent offices
21
Set-&-Tuple complex object Model


1985: Khoshafisian & Banchillon
Set-&-tuple complex object model

have been proposed to the relational model with nested
relations




attribute values can be tuples or sets
Set valued attributes
Relation valued attributes
Extending SQL


extending relational calculus permitting sets
extending relational algebra permitting sets
22
Semantic Data Model

Semantic data model



semantic v.s. object-oriented model




node --- entity, object
link --- relationship
entity type v.s. class
entity v.s. instance
attribute v.s. instance variable
So many proposals (1980-1986)

GEM, Association Model, SDM, RM/T, ……
23
Integrity Constraints for OODBs








Unique/primary key constraints
Existential constraint
NOT NULL constraint
Integrity rules
Triggers
Pre- and postconditions for methods
Disjointness constraint
Covering constraint
24
Contents







Introduction
Foundation and Evolution of OODBs
Persistence in OODBs
Transactions & Concurrency Control in OODBs
Recovery in OODBs
Versioning
Client/Server Architecture and OODBs
25
Persistence in OODBs


Ways to create and maintain persistent objects
Three strategy to create & identify persistent objects:



persistent classes and class extensions
persistence through reachability
persistence instances
26
Persistent classes and class extensions





System built-in persistent classes
Subclasses of built-in persistent classes are persistent
Understand as ADT constructor and Container classes
Most cases: COLLECTION classes (set, bag, list, array)
Iterators (for navigating persistent instances)
27
Application’s Object Space
Persistent
Object Space
DB
Transient
Object Space
X
Y
Z
Persistence through reachability
28
Persistent Instances
Transient Instances
Archival
Documents
Query
Result
Accounts
Invoices
New
Folder
Declaring Persistent & Transient instances
29
Main Stream to Manipulate Persistent OODBs

Strategies for persistence in OODBs

extending a DB language with OO capability



extending SQL with OO features
IntelligentSQL, UniSQL
extending an OO language with DB capabilities


language extension: making Smalltak an OODBMS
entendible library: Ontos, Versant
30
Extending SQL with OO

SQL standards



SQL-89
SQL-92
Currently SQL3 standardization effort incorporates
OO features




user-defined abstract data typing
inheritance
set, collection types
object identity
31
Case Study (ORDB): Intelligent SQL


Prototype developed at Ashton-Tate that extended
SQL and the InterBase DB engine
Main concepts of object orientation





abstract data types
inheritance
tuples and object identity
extended dot “.” notation
identity
32
Intelligent SQL: Abstract Data Type
CREATE CLASS Stack[T] {
INSTANCE VARIABLE (
ARRAY StArr[M] of T,
Top INTEGER);
METHODS (
push ….. ( ……);
pop ….. (…….);
}
CREATE TABLE Account(
AccountNumber INTEGER,
Location
CHAR(20)
Payables
Stack[Dollar])
SELECT AccountNumber, Pop(Payables)
FROM Account
WHERE Location = “New York”
33
Intelligent SQL: Inheritance
CREATE TABLE OfficeWorker (
Name CHAR(20),
Address CHAR(100),
Workeroffice CHAR(10), Salary FLOAT, DateOfBirth DATE)
CREATE TABLE Manager
SPECIALIZES OfficeWorker ( Title CHAR(10))
CREATE TABLE VicePresident
SPECIALIZES Manager (AdminAssistant CHAR(20))
SELECT Address FROM Manager WHERE Salary > 60K
CREATE TABLE HighlyPaidWorker
SPECIALIZES OfficeWorkers
WHERE Salary > 60,000
34
Intelligent SQL: Tuple and OID
CREATE TUPLE ADDRESS (
Number INTEGER, StrtName CHAR (20), AptNo INTEGER,
City CHAR(20),
State CHAR(20),
Zip INTEGER);
CREATE TABLE Persons (
Name CHAR (20), Age INTEGER, HomeAddr ADDRESS);
CREATE TABLE Persons(
Name CHAR(20), Age INTEGER,
HomeAddr TUPLE( Number INTEGER,
StrtName CHAR (20),
AptNumber INTEGER, City CHAR(20),
State CHAR(20),
Zip INTEGER)
35
Case Study(ORDB): UniSQL


Won Kim at UniSQL, Inc.
SQL/X is an extension of the SQL-89 with objectoriented extensions




direct reference to table records
ability to associate procedures or methods with table
definitions
support of table inheritance
support of collection types in relations
36
UniSQL
CREATE CLASS IMAGE (
Size INTEGER,
Type INTEGER,
Content …)
CREATE CLASS PERSON (
Name CHAR (32),
…
Picture IMAGE);
CREATE CLASS MAP (
MapName CHAR(32),
MapRegion CHAR(32);
MapImage set IMAGE)
37
Extending OOPL with DB Capabilities

Two alternatives

use language extensions that enrich the OO language with
database capabilities


GemStone’s OPAL by ServioLogic
provide extendible OODBMS libraries

C++ libraries for database management by Ontos, Versant,
Objectivity, and ObjectDesign
38
Case Study (PL Ext): OPAL



Making Smalltalk as a DB language
OPAL is the GemStone’s DDL and DML
Defining a class in OPAL
Receiving_class_name subclass ‘Name_subclass’ instVarName:
ListofInstanceVariables
classVars: ListofClassVariables
poolDictionaries: ListofCommonVariables
inDictionary: DictionaryName
constraints: ListofDomainConstraints
InstanceInvariant: False/True
isModifiable: False/True
39
Case Study (PL Ext): OPAL
Richworker := Workers select:
{:aworker | aworker.salary > 60000}
Jones := Workers select:
{ :aworker | (aWorker.age > 21) &
(aWorker.name.last = “Jones”)}
40
C++ Classes for DB capabilities

Class libraries supporting persistence and DB
capabilities






constructors new with various parameters
methods to destroy the persistent object
methods to read/write object from/to DB
methods to lock/unlock the object
predicate to check the object’s modification
Persistent classes are defined by their inheritance
from a root persistent class
41
PersistentObject
PersistentFolder
Persistent
AccountFolder
PersistentWorker
Persistent
SalesPersion
PersistentPeripheral
Persistent
Scanner
< Persistent classes routed at PersistentObject >42
Case Study (Library): Versant



OODBMS from Versant Object Technology
Supports C, C++, and Smalltalk interface
Persistent root class PObject provides





new operator
delete method
className(), isPersistent(), isInstanceOf(),...
object management methods
version management methods
43
Case Study (Library): ObjectStore(1)



ObjectStore ODBMS from ObjectDesign, Inc.
A number of high-performance capability
Any object type can be persistent or transient
// Create an instance of office_type
Officeapp *officeobject = new(officedb, office_type)
// Declare binding of a variable to a database
Database *officedb;
……………..
officedb = os_database::open(“/office/officedb”);
44
Case Study (Library): ObjectStore(2)

Collections and Querying in ObjectStore

ObjectStore collection classes :


os_Collection, os_Set,
os_Bag,
os_List
The general form for executing a query is :
<collection-object>.os_query( <element type name>,
<query string>,
<database> )
corporateOffices[: size > 200 :];
45
Persistent Complex Object Storage Strategies
(Fast Object Access!!!)

Two complementary storage techniques

indexing to accelerate the searches



conventional indexing techniques are applicable
B-tree, primary/secondary index, hashing, etc.
clustering to store objects that are accessed together as close
as possible

graph structured object space are mapped onto physical storage
units such as pages, segments
46
Page 1
Page 2
…………..
Persistent Object Space
Physical Disk Pages
Mapping complex object spaces onto
secondary-storage disk pages
47
Case Study (Clustering): ObjectStore

ObjectStore

persistent address space


concurrently sharable
its size is larger than that of virtual address space





theoretical 2^29 bytes/DB
Main memory < Virtual Memory < Persistent Memory
Several disks can be used for persistent memory
A database can have many segments
Clustering objects in the segments improve the performance
48
Physical
memory
VM
Persistent
Memory
OS Paging System
ObjectStore & VM extend views of memory
in similar way
49
Case Study (Clustering): GemStone

GemStone

specify how objects should be clustered
(e.g.) MyObject cluster
clusterPerson
self cluster.
name cluster.
age cluster.
Soc-sec-num cluster.
Address cluster.
address streetNum cluster
address streetName cluster
address State cluster
50
Contents







Introduction
Foundation and Evolution of OODBs
Persistence in OODBs
Transactions & Concurrency Control in OODBs
Recovery in OODBs
Versioning
Client/Server Architecture and OODBs
51
Transactions in OODBMS(1)

Constructs
 begin transaction
 end(commit) transaction
 abort transaction

to undo all work and terminate the transacation without its
updates
52
Transactions in OODBMS(2)

Properties(ACID)




Atomicity: a program that either is executed entirely or is not
executed at all
Consistency: all associated semantic integrity constraints are
satisfied
Isolation: the safeguard provided by the database system
against mutual interference between concurrent transactions
Durability: preserve the effects of all committed transactions
as well as db consistency in the presence of system and
media failures
53
State S1
State S2
Folders
Folders
Documents
Documents
Transaction
Workers
Workers
All integrity constraints
are satisfied
All integrity constraints
are satisfied
Transactions maintain consistency
54
Long Transactions

Advanced database applications


Issues on long transactions




CAD, CAM, GIS, telecommunication, etc.
on a failure, the entire transactions has to be rolled back
the more complex and large a transaction, the more conflicts
with other transactions
computer supported cooperative work
Long transaction management techniques


nested transaction
cooperating transaction
55
SD1
Document
Outline
SD1
First
Draft
SD1 SD1
Subdocuments
Integrated for
First Draft
Second
Draft
Reviews cumulating
in 2nd Drft
+
Draft 2
Final
Draft
Integrating Figures,
Charts, Etc. , for
Final Draft
The multiple steps to complete a complex document
56
Nested Transactions


Introduced by Moss (1981)
Transactions have a tree structure
Top Level Transaction
ST1
ST11
ST12
ST2
ST21
ST22
57
Final
Draft
Final Draft
Top-level Transaction
Integrate
Draft 2
Subtransaction for Draft 2:
integrate annotations
Subtransaction for
Graphics
……...
Subtransaction for Graphics
Draft 1
Subtransaction for
Draft 1
Nested transaction in document-preparation example
58
Cooperating Transactions


Some advanced application involve users who need to
cooperate
Each workers come up with rules to


regulate the coordination
synchronize their individual subtransactions
59
Concurrency Control


The activity of synchronizing the actions of transactions
occurring at the same time: Protocol
Algorithms based on



Locking: Two-phase locking, Multiple-granularity locking
Timestamp ordering
Commit time certification
60
Lock based Concurrency Control

Two-phase locking protocol


separate the transaction into a growing phase and a
shrinking phase
Multigranularity locking




physical storage organization
classes and instances
class hierarchy locking
complex or composite object locking
61
Other Concurrency Control Mechanisms

Multiversion concurrency control



creates a new version of a database for each update
transaction
garbage collection to get rid of old versions
Optimistic concurrency control


perform any operation on a database object
determine whether a transaction’s commit can be safely
processed
62
Case Study (Concurrency control)

GemStone



Versant


write, intention write, update, read, intention read, and null lock modes
Objectivity/DB




both optimistic and pessimistic (locking) concurrency control
read (Shared), write, exclusive lock modes
read, update lock modes
multiple granularity locking
check-in/check-out protocol
ONTOS


both optimistic and pessimistic (locking) concurrency control
read, write, and write intent lock
63
Contents







Introduction
Foundation and Evolution of OODBs
Persistence in OODBs
Transactions & Concurrency Control in OODBs
Recovery in OODBs
Versioning
Client/Server Architecture and OODBs
64
Recovery in OODBs(1)

Types of failures

transaction failures


systems failures


a transaction fails to commit
hardware or software problems
media failures

hard disk crashes or other nonrecoverable errors on the hard
disk
65
Recovery in OODBs(2)

Recovery manager

log




is used to record & store the before & after image of updated
objects
Undo log
Redo log
data replication or mirroring

shadowing
66
Case Study (Recovery)

GemStone

create replicas of the persistent database
SystemRepository replicateWith: <file name>


all replicas are updated before the transaction commits
ODB-II from Fusitsu


transaction recovery with roll back
system recovery with log
67
Contents







Introduction
Foundation and Evolution of OODBs
Persistence in OODBs
Transactions & Concurrency Control in OODBs
Recovery in OODBs
Versioning
Client/Server Architecture and OODBs
68
Versioning






System facility for keeping track of previous states or
alternate states of objects
A version set contains all the versions of the object
Important in design-oriented environment
Create a version, derive a version
Retrieve a version, update a version, delete a version
Check-in/out


check-in : from private DB to public DB
check-out : from public DB to private DB
69
Workstation Server:
Private DB
Check-out
``
Check-in
Designer’s PC:
Public DB
< Check-in & check out in versioning >
70
Design Object: O1
V1: Original Version
Alternative Versions
V4
V2
V3
V6
V5
V7:Final Version
{V1,V2,V3,V4,V5,V6,V7} : the version set of O1
V1-V3-V6-V7 : a linear version of O1
{V2,V3} : alternative version of V1
Version Set of O1:
71
Version Creation

Language constructs



Check-out and check-in object versions
retrieve successors or predecessors of versions
Different approaches for creating versioned objects


inheritance from Version class
explicit property with versioned declaration
72
Inheritance
class
class
Method
Signature
Method Name
(is-a)
Version
PersistentObject
Folder
Version
Retrieve predecessor
Version
Retrieve successor
VersionFolder
Version
Version
Versioned objects through multiple inheritance
73
Configuration




Collections of objects that must be maintained
mutually consistently
A unit for locking and versioning
Each object within the configuration can have a
history of versions
Version percolation: If a new version of any
component object in a configuration is derived, a new
version of the configuration is also derived.
74
Time
V1
Object 1
V1
Object 2
V2
V3
V2
Object 3 V1
V1
Object 1
V1
Object 2
Object 3 V1
V2
V4
V3
V3
V2
Configuration 1
V4
V3
V2
V2
V4
V4
V3
V3
V4
V4
Configuration 2
Versions of objects & configurations
75
Check-out/Check-in Model and Versioning

Algorithm for accessing objects concurrently in client/server
architectures






step1. begin transaction
step2. navigate or locate the object(s) to be manipulated
step3. check out the objects with either read or write lock, depending
on intent
step4. manipulate the object(s), possibly updating it
step5. check in object(s) back to common area (repository), possibly
creating a new version
step6. commit transaction
76
Versioning in OODBs

ITASCA


ONTOS



automatic versioning of objects tagged as versioned
versioning and alternative mechanisms
configuration objects
ObjectDesign

configurations and versioning with alternatives
77
Contents







Introduction
Foundation and Evolution of OODBs
Persistence in OODBs
Transactions & Concurrency Control in OODBs
Recovery in OODBs
Versioning
Client/Server Architecture and OODBs
78
Client/Server Architectures and OODBs

Client/Server architecture



Distributed databases



file servers
database servers
homogeneous distributed database
heterogeneous distributed database
Standardization effort


CORBA(Common Object Request Broker Architecture) by OMG
Client/Server Paradigm + OO Paradigm
79
C/S Architecture: File Servers


Concurrent resource sharing among multiple users
File servers




file, block, page level I/O
buffering, locking, concurrent access
back-up, authorization, transaction
The client side

execution of the application
80
Application
Application
DBMS(Front End)
DBMS(Front End)
ClientOS
Network OS API
ClientOS
Network OS API
Data Filing
Computations
GUI Front End
< File server architecture >
81
C/S Architecture: Database Servers

Programming interfaces to database servers



tools or programs used to interact with the server
constitute the client side of the software that is used to
interact with the server
Partitioning functions between clients and server

peer-to-peer architecture


each node has the potential of becoming both a client and a
server
local and personal databases

check-out/check-in model of application development
82
Client/Server and OODBMS

Partition of functionality between C/S of OODBMS

object-server architecture




page-server architecture



the server manages objects
queries and methods can be executed on the server node
thin client
the server does not process queries or execute methods,
these are performed on the client side
heavy client
file-server architecture
83
Two types of object accesses

Navigational


variable “reachable” objects are accessed through attribute
values or elements of referencing or parent objecs
Query(or declarative) access

a search mechanism through a query
84
A (possible) layered Architecture of OODBMS
Query Manager,
Accessor/Update Manager
Query Optimizer
Complex Object Manager
Concurrency Control
and Transaction Manager
Storage and Index Manager
Buffer Manager
Recovery Manager
Physical I/O
85
Alternative strategies on the server side

Query and accessor/update/method interface


Complex object interface



the highest level that could be supported by the server
the server provides a slightly lower level interface than the
query or method access option
Storage and index manager layer interface
Physical file and block I/O

is similar file server architectures except that the
management and concurrency control of the the I/O blocks is
performed by OODBMS
86
Server process:
Query and Evaluate
High-level Query
Descriptor(Result)
Client process:
SELECT ….
< Server processing high-level query statements >87
Case Study (Client/Server)

Objectivity/DB : page server architecture




Server does page read/write and lock based concurrency
control
Client does other modules
Heavy client
Versant : object server architecture



Server does most parts of processing
Dual buffer: Server cache, Client cache
Thin client
88
Client
Cache
Object
Requests
Object
Server
Cache
< Versant’s client/object server architecture >
89
Distributed Databases


Interconnected LANs/ Mulitple Servers
Characteristics




Autonomy: the degree to which sites within the distributed
database system may operate independently
Distribution transparency: the extent to which the distribution
of data to sites is shielded from users and application
Heterogeneity: different hardware and operating system may
use different data representation
Total isolation: each site in the distributed database system
is a stand-alone server and is unaware of the other sites
90
File
Server
LAN
DB
Server
LAN/WAN
Interconnect
LAN
File
Server
DB
Server
File
Server
LAN
DB
Server
< Distributed database on interworked LANs >
91
Client
Server #1:
Folders
DATABASE:
Folders
Workers
Peripherals
Server #2:
Workers
Server #3:
Peripherals
< One logical database distributed across various servers >
92
Distributed transaction management

Requirements for atomic commitment




each participant must arrive at the same commit or abort
decision
each participant has veto power
each participant must not reverse its decision once a unanimous
decision is reached
Two-phase commit protocol
93
Site
#1
Site
#2
Site
#3
Site
#1
Coordinator
Site
#2
Phase II
Site
#3
Coordinator
OK
OK
Phase I
OK
COMMIT in 2-phase commit protocol
for distributed transactions
94
Site
#1
Site
#2
Site
#3
Site
#1
Coordinator
Site
#2
Phase II
Site
#3
Coordinator
OK
Failed
Phase I
OK
ABORT in 2-phase commit protocol
for distributed transactions
95
Case Study (Distributed OODB)

ONTOS object database



database can be physically distributed to many servers
two-phase commit protocol
Open ODB from HP


the server part: An object manager and underlying RDB
engine (ALLBASE/SQL)
two-phase commit protocol
96