CSIS3714

Thabo
“Do” or “die”
CHAPTER 12

What is a transaction?

• Any action that reads from and/or writes to a database

• Logical unit of work that must be either entirely completed or aborted

• Successful transaction changes database from one consistent state to another

– One in which all data integrity constraints are satisfied

• Most real-world database transactions are formed by two or more database requests

– Equivalent of a single SQL statement in an application program or transaction

Transaction properties:

• ACIDS test – Atomicity, Consistency, Isolation, Durability, Serializability

• Atomicity

– All operations (SQL requests) of a transaction must be completed

• Consistency

– Permanence of database’s consistent state

– When a transaction is completed, the database reaches a consistent state

• Isolation

– Data used during transaction cannot be used by second transaction until the first is completed

• Durability

– Once transactions are committed, they cannot be undone

• Serializability

– Concurrent execution of several transactions yields consistent results

– Concurrent results appear to have been executed in serial order

• Multiuser databases are subject to multiple concurrent transactions

Transaction Management with SQL

• Transaction support is provided by two SQL statements: COMMIT and ROLLBACK

• Transaction sequence must continue until:

– COMMIT statement is reached

– ROLLBACK statement is reached

– End of program is reached

– Program is abnormally terminated

• COMMIT statement is reached

 – All changes are permanently recorded

• ROLLBACK statement is reached

– All changes are aborted and the database is rolled back to its previous state

• End of program is reached

– Equivalent to a COMMIT

• Program is abnormally terminated

– Equivalent to a ROLLBACK

The Transaction Log

• A DBMS uses a transaction log to keep track of all transactions that update the database

• Information is used for recovery triggered by a ROLLBACK, abnormal termination or system failure

• Some RDBMs use the log to recover a database forward to a consistent state

• The transaction log is itself a database which is managed by the DBMS

Concurrency Control

• Coordination of simultaneous transaction execution in a multiprocessing database

• Objective is to ensure serializability of transactions in a multiuser environment

• Three main problems:

– Lost updates

– Uncommitted data

– Inconsistent retrievals

Uncommitted Data

• Uncommitted data phenomenon:

– Two transactions are executed concurrently

– First transaction rolled back after second already accessed uncommitted data

Inconsistent Retrievals

• Inconsistent retrievals:

– First transaction accesses data

– Second transaction alters the data

– First transaction accesses the data again

• Transaction might read some data before they are changed and other data after changed

• Yields inconsistent results

The Scheduler

• Special DBMS program

– Purpose is to establish order of operations within which concurrent transactions are executed

• Interleaves execution of database operations:

– Ensures serializability

– Ensures isolation

• Serializable schedule

– Interleaved execution of transactions yields same results as serial execution

Concurrency Control with Locking Methods

• Lock

– Guarantees exclusive use of a data item to a current transaction

– Required to prevent another transaction from reading inconsistent data

– Pessimistic locking

• Use of locks based on the assumption that conflict between transactions is likely

– Lock manager

• Responsible for assigning and policing the locks used by transactions

• Indicates level of lock use

• Locking can take place at following levels:

– Database

– Table

– Page

– Row

– Field (attribute)

• Database-level lock

– Entire database is locked

• Table-level lock

– Entire table is locked

• Page-level lock

– Entire diskpage is locked

– Table can span several pages and a page can contain several rows of one or more tables

– Currently the most frequently used multiuser DBMS locking method

• Row-level lock

– Allows concurrent transactions to access different rows of same table

 • Even if rows are located on same page

– Less restrictive, but requires more overhead

• Field-level lock

– Allows concurrent transactions to access same row

• Requires use of different fields (attributes) within the row

– Is the most flexible, but requires high level of overhead

Lock Types

• Binary lock

– Two states: locked (1) or unlocked (0)

– Is considered too restrictive to yield optimal concurrency conditions

• Exclusive lock

– Access is specifically reserved for transaction that locked object

– Must be used when potential for conflict exists

• Shared lock

– Concurrent transactions are granted read access on basis of a common lock

• Exclusive lock

– Issued when a transaction wants to update a data item and there is no current lock on the item

– Mutual exclusion rule: only one transaction at a time can hold an exclusive lock on the same object

• Shared lock

– Issued when a transaction wants to read data from the database and there is no exclusive lock on
the data item

Two-Phase Locking to Ensure Serializability

• Defines how transactions acquire and relinquish locks

• Guarantees serializability, but does not prevent deadlocks

– Growing phase

• Transaction acquires all required locks without unlocking any data

– Shrinking phase

• Transaction releases all locks and cannot obtain any new lock

• Governed by the following rules:

– Two transactions cannot have conflicting locks

– No unlock operation can precede a lock operation in the same transaction

– No data are affected until all locks are obtained

Deadlock

• Condition that occurs when two transactions wait for each other to unlock data

• Possible only if one of the transactions wants to obtain an exclusive lock on a data item

– No deadlock condition can exist among shared locks

• Three techniques to control deadlock:

– Prevention

• A transaction requesting a lock is aborted when there is a possibility that a deadlock can
occur

– Detection

• DBMS periodically tests for deadlocks. If a deadlock is detected, one of the transactions is
aborted and the other continues

– Avoidance

• Transaction must obtain all locks it needs before it can be executed

• Choice of deadlock control method depends on database environment

– Low probability of deadlock; detection recommended

– High probability; prevention recommended

Concurrency Control with Time Stamping Methods

• Assigns global unique time stamp to each transaction

• Produces explicit order in which transactions are submitted to DBMS

• Time stamps

– Uniqueness

• Ensures that no equal time stamp values can exist

– Monotonicity

• Ensures that time stamp values always increase

– Used to execute conflicting transactions in time stamp order

Wait/Die and Wound/Wait Schemes

• Wait/die

– Older transaction requests a lock, it will wait (wait) until the other transaction is completed and the
lock is released

– Younger transaction requesting a lock, it will die (rolled back) and be rescheduled

Older transactions wait and younger transaction dies

• Wound/wait

– Older transaction requests a lock, is will preempt (wound) the younger transaction by rolling it back
 – Younger transaction requesting a lock, it will wait until the other transaction is completed and locks
are released

Older transaction rolls back the younger transaction and reschedules it

Concurrency Control with Optimistic Methods

• Optimistic approach

– Based on assumption that majority of database operations do not conflict

– Does not require locking or time stamping techniques

– Transaction is executed without restrictions until it is committed

– Phases: read, validation, and write

• Optimistic approach

– Read

• Transaction reads the database, executes the needed computations and makes the updates
to a private copy of the database values

– Validation

• Transaction is validated to ensure changes made will not affect the integrity and consistency
of the database

– Write

• The changes are permanently applied to the database

Database Recovery Management

• Restores database to previous consistent state

• Based on atomic transaction property

– All portions of transaction are treated as single logical unit of work

– All operations are applied and completed to produce consistent database

• If transaction operation cannot be completed:

– Transaction aborted

– Changes to database are rolled back

• Levels of backup

– Full

– Differential

– Transaction log
Transaction Recovery

• Write-ahead-log protocol: ensures transaction logs are written before data is updated

• Redundant transaction logs: ensure physical disk failure will not impair ability to recover

• Buffers: temporary storage areas in primary memory

• Checkpoints: operations in which DBMS writes all its updated buffers to disk

• Deferred-write technique

• Only transaction log is updated

• Recovery process: identify last checkpoint

• If transaction committed before checkpoint:

• Do nothing

• If transaction committed after checkpoint:

• Use transaction log to redo the transaction

• If transaction had ROLLBACK operation:

• Do nothing

• Write-through technique

• Database is immediately updated by transaction operations during transaction’s execution

• Recovery process: identify last checkpoint

• If transaction committed before checkpoint:

• Do nothing

• If transaction committed after last checkpoint:

• DBMS redoes the transaction using “after” values

• If transaction had ROLLBACK or was left active:

• Use transaction log to roll back or undo

CHAPTER 13

Database Performance-Tuning Concepts

• Goal of database performance is to execute queries as fast as possible

• End users and DBMS interact as follows:

– The end user application generates a query

– The query is sent to the DBMS

– The DBMS executes the query

– The DBMS sends the resulting data set to the end user

• This must occur as fast as possible

Database Performance-Tuning Concepts

• Database performance tuning

– Set of activities and procedures designed to reduce response time of database system

• All factors must operate at optimum level with minimal bottlenecks

• Good database performance starts with good database design – no amount of fine-tuning will make a poorly
designed database perform as well as a well-designed database

Performance Tuning: Client and Server

• Client side

– Generate SQL query that returns correct answer in least amount of time

• Using minimum amount of resources at server

– SQL performance tuning

• Server side

– DBMS environment configured to respond to clients’ requests as fast as possible

• Optimum use of existing resources

– DBMS performance tuning

DBMS Architecture

• All data in database are stored in data files

• Data files

– Automatically expand in predefined increments known as extends

– Grouped in file groups or table spaces

• Table space or file group

 – Logical grouping of several data files that store data with similar characteristics

• Data cache or buffer cache: shared, reserved memory area

– Stores most recently accessed data blocks in RAM

• SQL cache or procedure cache: stores most recently executed SQL statements

– Also PL/SQL procedures, including triggers and functions

• DBMS retrieves data from permanent storage and places it in RAM

• Input/output request: low-level data access operation to/from computer devices

• Data cache is faster than data in data files

– DBMS does not wait for hard disk to retrieve data

• Majority of performance-tuning activities focus on minimizing I/O operations

• Typical DBMS processes:

– Listener, user, scheduler, lock manager, optimizer

Database Query Optimization Modes

• Most of the algorithms for query optimization are based on two principles:

– The selection of the optimum execution order

– The selection of sites to be accessed to minimize communication costs

• Automatic query optimization

– DBMS finds the most cost-effective access path without user intervention

• Manual query optimization

– Requires that the optimization be selected and scheduled by the end user or programmer

• Query optimization algorithms can be classified according to when the optimization is done:

– Static query optimization

• Takes place at compilation time (when the query is compiled by the DBMS)

– Dynamic query optimization

• Takes place at execution time (Database access strategy is defined when the program is
executed)

• Dynamic query optimization

– Uses the most up-to-date information about the database

– Dynamic query optimization is efficient but its cost is measured by run-time processing overhead

– The best strategy is determined every time the query is executed, which could happen several times
in the same program

• Statistically based query optimization algorithm

– Uses statistical information about the database

– Dynamic statistical generation mode

 – Manual statistical generation mode

• Rule-based query optimization algorithm

– Based on a set of user-defined rules to determine the best query access strategy

Database Statistics

• Measurements about database objects and available resources:

– Tables

– Indexes

– Number of processors used

– Processor speed

– Temporary space available

• Make critical decisions about improving query processing efficiency

• Can be gathered manually by DBA or automatically by DBMS

– Parsing

• Break down query into smaller units

• Transform original SQL query into slightly different version of original SQL code that is fully equivalent but
more efficient

• Statistics are used to determine the most efficient way to execute the query

• Query optimizer analyses SQL query and finds most efficient way to access data

• Validated for syntax compliance

• Validated against data dictionary: Tables and column names are correct, User has proper access rights

• Once the SQL statement is transformed, the DBMS creates an access or execution plan

• DBMS checks if access plan already exists for query in SQL cache. DBMS reuses the access plan to save
time. If not, optimizer evaluates various plans

• Chosen plan placed in SQL cache

– Execution

• DBMS executes the query using chosen execution plan

• All I/O operations indicated in access plan are executed

• Locks acquired

• Data retrieved and placed in data cache

• Transaction management commands processed

– Fetching

• All rows matching the specified condition are retrieved, sorted, grouped and/or aggregated

• Rows of resulting query result set are returned to client

Query Processing Bottlenecks

• Delay introduced in the processing of an I/O operation that slows the system

– CPU

– RAM

– Hard disk

– Network

– Application code

Indexes and Query Optimization

• Indexes

– Crucial in speeding up data access

– Facilitate searching, sorting, and using aggregate functions as well as join operations

– Ordered set of values that contains index key and pointers

More efficient to use index to access table than to scan all rows in table sequentially

• Data sparsity: number of different values a column could possibly have

• Indexes implemented using:

– Hash indexes

– B-tree indexes

– Bitmap indexes

• DBMSs determine best type of index to use

Optimizer Choices

• Rule-based optimizer

– Preset rules and points

– Rules assign a fixed cost to each operation

• Cost-based optimizer

– Algorithms based on statistics about objects being accessed

– Adds up processing cost, I/O costs, resource costs to derive total cost

Using Hints to Affect Optimizer Choices

• Optimizer might not choose best plan

• Makes decisions based on existing statistics

– Statistics may be old

– Might choose less-efficient decisions

• Optimizer hints: special instructions for the optimizer embedded in the SQL command text
SQL Performance Tuning

• Evaluated from client perspective

– Most current relational DBMSs perform automatic query optimization at the server end

– Most SQL performance optimization techniques are DBMS-specific

• Rarely portable

• Majority of performance problems are related to poorly written SQL code

• Carefully written query usually outperforms a poorly written query

Index Selectivity

• General guidelines for indexes:

– Create indexes for each attribute in WHERE, HAVING, ORDER BY, or GROUP BY clause

– Do not use in small tables or tables with low sparsity

– Declare primary and foreign keys so optimizer can use indexes in join operations

– Declare indexes in join columns other than PK/FK

DBMS Performance Tuning

• Includes managing DBMS processes in primary memory and structures in physical storage

• DBMS performance tuning at server end focuses on setting parameters used for the:

– Data cache

– SQL cache

– Sort cache

– Optimizer mode: cost-based or rule-based

• Some general recommendations for creation of databases:

– Use RAID (Redundant Array of Independent Disks) to provide balance between performance and
fault tolerance

– Minimize disk contention: use multiple, independent storage volumes with independent spindles to
minimize hard disk cycles

• Some general recommendations for creation of databases:

– Put high-usage tables in their own table spaces

– Assign separate data files in separate storage volumes for indexes, system, and high-usage tables

– Take advantage of table storage organizations in database, for example use the index-organized
tables

– Partition tables based on usage

– Use denormalized tables where appropriate

– Store computed and aggregate attributes in tables

The evolution of distributed database management systems

• A DDBMS governs the storage and processing of logically related data over interconnected computer
systems in which both data and processing functions are distributed among several sites.

• Centralized database

• required that corporate data be stored in a single central site, usually a mainframe or midrange
computer

• Access was provided through dumb terminals

• Worked well to fill structured needs

• Fell short when quickly moving events required faster response times and equally quick access to
information.

• Quick unstructured access to databases, using ad hoc queries to generate on-the-spot information was
required.

• Database management systems based on the relational model could provide the environment in which
unstructured information needs would be met by employing ad hoc queries.

• Over the last two decades there has been a series of crucial social and technological changes that affected
database development and design:

• Business operations became global

• Customer demands and needs favored an on-demand transaction style

• Low-cost, smart mobile devices increased the demand for complex and fast networks to
interconnect them

• Applications must manage multiple types of data, such as voice, video, music and images

• As large business units restructured in response, two database requirements became obvious:

• Rapid ad-hoc data access was crucial in the quick-response decision-making environment

• Decentralization of management structures based on decentralized business units made

decentralized multiple-access and multiple-location databases a necessity

• The way these factors were addressed was strongly influenced by:

• The growing acceptance of the internet

• The mobile wireless revolution

• The accelerated growth of companies using “applications as a service” – providing remote

applications to companies that want to outsource their application development

• The increased focus on mobile business intelligence

• Distributed database is desirable because centralized management is subject to problems:

• Performance degradation due to the increase in remote locations

• High costs associated with maintaining and operating central database systems

• Reliability problems created by dependence on central site

• Scalability problems associated with physical limits of single site, eg space, power consumption

• Organizational rigidity: the database might not support the flexibility required by modern global
organizations
DDBMS Advantages

• Data are located near the greatest demand site

• Faster data access as end users often only work with a locally stored subset

• Faster data processing since data is processed at several sites

• Growth facilitation: new sites can be added without affecting the operations of other sites

• Improved communications: local sites are smaller and situated closed to the customer base

• Reduced operating costs: more cost-effective to add workstations to a network than to update a mainframe

• User friendly interface as PCs and workstations are usually equipped with easy to use GUIs

• Less danger of a single-point failure: When one of the computers fails, the workload is picked up by other
workstations

• Processor independence: the end user is able to access any available copy of the data, and the request is
processed by any processor at the data location.

DDBMS Disadvantages

• Complexity of management and control: applications must recognize data location and be able to merge
data from different sites. Transaction management, concurrency control, security etc must all be addressed

• Security: the probability of security lapses increases when data are located at multiple sites and
responsibility is shared at different sites

• Lack of standards since there are no standard communication protocols at the database level (although
TCP/IP is the de facto standard)

• Increased storage requirements: Multiple copies of data are stored at different sites, thus requiring more
storage space

• Increased training cost: training costs are usually higher than with a centralized database

• Costs: distributed solutions require duplicated infrastructure, such as physical location, personnel, software
and licensing

Distributed processing and distributed databases

• In distributed processing, a database’s logical processing is shared among two or more physically
independent sites that are connected through a network.

– The database is located at a single site, on the database server.

– The processing is shared between sites

• A distributed database, stores a logically related database over two or more physically independent sites.

– The sites are connected via a network

– The database is composed of several parts, known as database fragments

• Distributed processing does not require a distributed database

• Distributed processing may be based on a single database located on a single computer

• Both distributed processing and distributed databases require a network of interconnected components
Characteristics OF DDBMS

• A DBMS must have the following functions to be classified as distributed:

– Application interface to interact with the end user or application programs

– Validation to analyze data requests

– Transformation to determine which data request components are distributed and which are local

– Query optimization to find the best access strategy

– Mapping to determine the data location of local and remote fragments

• A DBMS must have the following functions to be classified as distributed:

– I/O interface to read or write data from or to permanent local storage

– Formatting to prepare the data for presentation to the end user

– Security to provide data privacy at both local and remote databases

• A DBMS must have the following functions to be classified as distributed:

– Backup and recovery to ensure the availability and recoverability of the database in case of a failure

– DB administration features

– Concurrency control to manage simultaneous data access and ensure data consistency across data
fragments

– Transaction management to ensure the data moves from one consistent state to another

• A fully distributed database management system must perform all the functions of a centralized DBMS:

– Receive an application’s request

– Validate, analyze and decompose the request

– Map the request’s logical-to-physical data components

– Decompose the request into several I/O operations

– Search for, locate, read and validate the data

– Ensure database consistency, security and integrity

– Validate the data for the conditions specified by the request

– Present the selected data in the required format

• In addition, a DDBMS must handle the necessary functions imposed by the distribution of data and
processing

– This must be done transparently to the end user

DDBMS COMPONENTS

• Computer workstations that form the network system. The distributed database system must be
independent of the computer system hardware

• Network hardware and software components that reside in each workstation. The network components
allow all sites to interact and exchange data
 • Communications media that carry the data from one workstation to another. It must be able to support
several types of communication media.

• The transaction processor (TP) which is the software component found in each computer that requests data.
It receives and processes the application’s data requests.

• The data processor (DP) which is the software component residing on each computer that stores and
retrieves data located at the site.

• The protocols determine how the distributed database system will:

• Interface with the network to transport data and commands between the DPs

• Synchronize all data received from the DPs and route retrieved data to the TPs

• Ensure common database functions in a distributed system, such as security, concurrency control,
backup and recovery

Levels of data and process distribution

• Database systems are classified on the basis of how process distribution and data distribution are supported

– Single-site processing, single-site data

– Multiple-site processing, single-site data

– Multiple-site processing, Multiple-site data

• Single-site processing, single-site data (SPSD)

– All processing is done on a single CPU or host computer

– All data are stored on the host computer’s local disk

– Processing cannot be done on the end user side

– The DBMS is situated on the host computer and dumb terminals connect to it

• Single-site processing, single-site data (SPSD)

– The functions of the TP and the DP are embedded within the DBMS

– DBMS usually runs under a time-sharing, multitasking operating system, which allows several
processes to run simultaneously

– All data storage and processing are handled by a single CPU

– Examples: mainframe and midrange DBMSs

• Multiple-site processing, single-site data (MPSD)

– Multiple processes run on different computers sharing a single data repository

– Typically there is a network file server running conventional applications that are accessed over LAN

• Multiple-site processing, single-site data (MPSD)

– The TP on each workstation acts only as a redirector to route all network data requests to the file
server

– The end user sees the file server as just another hard disk

– The end user must make a direct reference to the file server in order to access remote data
 • Multiple-site processing, single-site data (MPSD)

– All data selection, search and update functions take place at the workstation. This increases network
traffic, slows response time and increases communication costs

• Select * from customer where cust_balance > 1000

• Multiple-site processing, single-site data (MPSD)

– Client/server architecture is a variation

• All database processing is done at the server site, thus reducing network traffic

• Multiple-site processing, multiple-site data (MPMD)

– Fully distributed DBMS with support for multiple data processors and transaction processors at
multiple sites

– Depending on the level of support for different types of centralized DBMSs, DDBMSs are classified as
either homogenous or heterogeneous

• Multiple-site processing, multiple-site data (MPMD)

– Homogenous DDBMSs integrate only one type of centralized DBMS over a network

– Heterogeneous DDBMSs support different DBMSs that may even support different data models

Distributed database transparency features

• A distributed database system requires functional characteristics that can be grouped and described as
transparency features.

• The features allow the end user to feel like the database’s only user

• The DDBMS transparency features are:

• Distribution transparency allows a distributed database to be treated as a single logical database. If

a DDBMS exhibits distribution transparency, the user does not need to know:

• That the data are partitioned

• That the data can be replicated at several sites

• The data location

• The DDBMS transparency features are:

• Transaction transparency allows a transaction to update several network sites. Transaction

transparency ensures that a transaction will be entirely completed or aborted

• Failure transparency ensures that the system will continue to operate in the event of a node failure.
Functions that were lost because of the failure will be picked up by another network node

• The DDBMS transparency features are:

• Performance transparency allows the system to perform as if it were a centralized DBMS. This also
ensures that the system will find the most cost-effective path to access remote data

• Heterogeneity transparency allows the integration of several different local DBMSs under a common
schema. The DDBMS is responsible for translating the data requests from the global schema to the
local DBMS schema
 • Distribution transparency allows a physically dispersed database to be managed as though it were a
centralized database.

• The level of transparency supported by the DDBMS varies from system to system.

Distribution transparency

• Distribution transparency allows a physically dispersed database to be managed as though it were a

centralized database.

• The level of transparency supported by the DDBMS varies from system to system.

• Three levels of distribution transparency are recognized:

• Fragmentation transparency is the highest level of transparency. The end user or programmer does
not need to know that a database is portioned. Therefore, neither fragment name nor locations are
specified prior to data access

• Location transparency exists when the end user or programmer must specify the database fragment
names but does not need to specify where those fragments are located

• Local mapping transparency exists when the end user or programmer must specify both the
fragment names and their locations

• Distribution transparency is supported by the distributed data dictionary (DDD) or a distributed data catalog
(DDC).

• The DDC contains the description of the entire database as seen by the database administrator.

• The database description, known as the distributed global schema, is the common schema used by local TPs
to translate user requests into subqueries that are processed by different DPs.

• The DDC itself is distributed and is replicated at the network nodes.

Transaction transparency

• Transaction transparency is a DDBMS property that ensures that database transactions maintain the
distributed database’s integrity and consistency.

• A transaction can update data stored on many different computers connected in a network.

• Transaction transparency ensures that the transactions are completed only when all database sites involved
in the transaction complete their part of the transaction.

• Distributed requests and distributed transactions

• Whether or not a transaction is distributed, it is formed by one or more database requests

• The basic difference between a non-distributed transaction and a distributed transaction is that the
latter can update or request data from several different remote sites on a network

• Distributed requests and distributed transactions

• A remote request lets a single SQL statement access the data that are to be processed by a single
remote database processor, that is, the statement can reference data at only a single site

• A remote transaction composed of several requests, accesses data at a single remote site

• Distributed requests and distributed transactions

 • A distributed transaction allows a transaction to reference several different local or remote DP sites.

• Each single request can reference only one local or remote DP site, but the transaction as a whole
can reference multiple DP sites

• Distributed requests and distributed transactions

• In order for a request to be able to access data from more than one remote site, the DBMS must
support distributed requests

• A distributed request lets a single SQL statement reference data located at several different local or
remote DP sites.

Distributed concurrency control

• Multi-site, multi-process operations are more likely to create data inconsistencies and deadlocked
transactions than a single-site system

• If each transaction was committed by a local DP, but one of the DPs could not commit then the data would
not be consistent.

– The two-phase commit protocol is a solution to the problem

Two-phase commit protocol

• A final commit must not be issued until all sites have committed their parts of the transaction

• The two-phase commit protocol guarantees that if a portion of a transaction operation cannot be committed,
all changes at all sites will be rolled back.

• Each DP maintains its own transaction log.

• The two-phase commit protocol requires that the transaction entry log for each DP be written before the
database fragment is actually updated.

• The two-phase commit protocol requires a DO-UNDO-REDO protocol and a write-ahead protocol

• The DO-UNDO-REDO protocol is used by the DP to roll back and/or roll forward transactions with the help of
the transaction log entries:

• DO performs the operation and records the before and after values in the transaction log

• UNDO reverses an operation, using the log entries written by the DO portion of the sequence

• REDO redoes an operation, using the log entries written by the DO portion of the sequence

• To ensure that the DO, UNDO and REDO operations can survive a crash while they are being executed, a
write-ahead protocol is used.

• The write-ahead protocol forces the log entry to be written to permanent storage before the actual
operation takes place.

• The two-phase commit protocol defines the operations between two types of nodes: the coordinator and
one of more subordinates.

• The participants agree on a coordinator.

• Generally the coordinator is the node that initiates the transaction

• Phase 1: preparation
 • The coordinator sends a PREPARE TO COMMIT message to all subordinates

• The subordinates receive the message, write the transaction log, using the write-ahead protocol,
and send an acknowledgement (YES or NO) message

• The coordinator makes sure that all nodes are ready to commit, or it aborts the action

• If all nodes are PREPARED TO COMMIT, the transaction goes to phase 2.

• If one or more nodes reply NO or NOT PREPARED, the coordinator broadcasts an ABORT message to all
subordinates

• Phase 2: the final COMMIT

• The coordinator broadcasts a COMMIT message to all subordinates and waits for the replies

• Each subordinate receives the COMMIT message, then updates the database using the DO protocol

• The subordinates reply with a COMMITTED or NOT COMMITTED message to the coordinator

• If one or more subordinates did not commit, the coordinator sends ABORT message, thereby forcing them to
UNDO all changes.

• The objective of the two-phase protocol is to ensure that all nodes commit their part of the transaction;
otherwise the transaction is aborted

• If one of the nodes fails to commit, the information required to recover the database is in the transaction
log, and can be recovered using the DO-UNDO-REDO protocol

Performance and failure transparency

• Performance transparency allows a DDBMS to perform as if it were a centralized database

– No performance degradation should be incurred due to data distribution

• Failure transparency ensures that the system will continue to operate in the case of a node or network
failure

• The objective of query optimization is to minimize the cost associated with the execution of a request. The
costs are a function of:

– Access (I/O) time cost involved in accessing the physical data stored on disk

– Communication cost associated with the transmission of data among nodes in distributed data
systems

– CPU time cost associated with the processing overhead of managing distributed transactions

• Resolving data requests in a distributed data environment must take the following points into consideration

– Data distribution: the DDBMS must decide which fragment to access

– Data replication: the data may be replicated at several sites. The database must ensure that all
copies are consistent, which makes the access process more complex

– Network and node availability: response time can not be easily predetermined because some nodes
finish their part of the query in less time than others and network path performance varies.

• Network latency (round trip)

• Network partitioning (delay imposed when nodes become unavailable)

Distributed data design

• The design principles and concepts are still applicable to the design of a distributed database.

• A distributed database does introduce new issues:

– How to partition the database into fragments

– Which fragments to replicate

– Where to locate those fragments and replicas

Data fragmentation

• Data fragmentation allows you to break a single object into two or more segments or fragments.

– Each fragment can be stored at any site on the network

• Horizontal fragmentation

– Division of a relation into subsets of tuples

– Each fragment is stored at a different node

– Each fragment has unique rows

– Rows all have the same attributes

• Vertical fragmentation

– Division of a relation into subsets of attributes

– Each subset is stored at a different node

– Each fragment has unique columns – with the exception of the key column

• Mixed fragmentation

– Combination of horizontal and vertical strategies

– A table may be divided into several horizontal subsets, each one having a subset of the attributes

Horizontal fragmentation

• There are various ways to partition a table horizontally:

– Round-robin partitioning

• Rows are assigned to a given fragment in a round-robin fashion to ensure an even

distribution of rows among all fragments

• Not a good strategy for location awareness

• There are various ways to partition a table horizontally:

– Range partitioning based on a partition key

• A partition key is one or more attributes in a table that determine the fragment in which a
row will be stored.

• For example, for location awareness, a good partition key could be the state
Mixed fragmentation

• Mixed fragmentation requires a two-step process

– Horizontal fragmentation

– Followed by vertical fragmentation

Data replication

• Data replication refers to the storage of data copies at multiple sites served by a computer network

• Fragment copies can be stored at several sites to serve specific information requirements

• Data copies can help to reduce communication and total query costs

• The mutual consistency rule requires that all copies of data fragments be identical

• The DDBMS must ensure that a database update is performed at all sites where replicas exist

• There are basically two styles of replication:

• Push replication

• Pull replication

• Push replication

• After a data update, the originating DP node sends the changes to the replica nodes to ensure that
data are immediately updated

• Focus on data consistency

• Decreases data availability due to the latency involved in ensuring data consistency

• Pull replication

• After a data update, the originating DP node sends the messages to the replica nodes to notify them
of the change

• The replica nodes decide when to apply the changes

• Focus on data availability

• Allows for temporary data inconsistencies

• If the database is fragmented, the DDBMS must decompose a query into subqueries to access appropriate
fragments

• If the database is replicated, the DDBMS must decide which copy to access. A READ operation selected the
nearest copy to satisfy the transaction. A WRITE operation requires that all copies be selected and updated
to satisfy the mutual consistency rule.

• The TP sends a data request to each selected DP for execution.

• The DP receives and executes each request and sends the data back to the TP.

• The TP assembles the DP responses.

• Fully replicated database

• Stores multiple copies of each database fragment at multiple sites

• Can be impractical due to the overhead it imposes

 • Partially replicated database

• Stores multiple copies of some database fragment at multiple sites

• Unreplicated database

• Stores each fragment at a single site

• Several factors influence the decision to use data replication:

• Database size: the amount of data to be replicated impacts storage requirements and data
transmission costs

• Usage frequency: the frequency of data usage determines how frequently the data needs to be
updated.

• Costs: performance, software overhead and management associated with synchronizing transactions
and their components.

Data Allocation

• Data allocation describes the process of deciding where to locate data

• Data allocation strategies:

– With centralized data allocation the entire database is stored at one site

– With partitioned data allocation the database is divided into several disjointed parts and stored at
several sites

– With replicated data allocation copies of one or more database fragments are stored at several sites

• Data allocation algorithms consider:

– Performance and data availability goals

– Size, number of rows and number of relations that an entity maintains with other entities

– Types of transactions to be applied to the database and the attributes accessed by each of those
transactions

The cap theorem

• CAP stands for the 3 desirable properties of a distributed data system:

– Consistency

– Availability

– Partition tolerance

• Consistency

– All nodes should see the same data at the same time

• Availability

– A request is always fulfilled by the system.

– No received request is ever lost

• Partition tolerance
 – The system continues to operate even in the event of a node failure

Database security

• Security is far more complex than in a centralized DBMS

• The underlying network also has to be made secure

• Password authentication is provided as is additional security, such as authentication through database links

Distributed databases within the cloud

• Cloud computing is a style of delivering applications, data and resources to users over the web

• Provides an alternative for organizations who do not wish to provide their own IT infrastructure to host
databases and software

• Benefits of using cloud infrastructure

• Cost effectiveness: only one infrastructure used to host services for multiple organizations, thus
reducing the cost for individual organizations

• Latest software: most cloud providers will ensure that their software is always the latest version

• Benefits of using cloud infrastructure

• Scalable architecture: it is easy to increase the database capacity and/or change the underlying
model

• Mobile access: data and software in the cloud can be accessed from anywhere

• Current NoSQL solutions include column stores and document stores

• Column stores

• For large scale distributed systems which store petrabytes of data across hundreds of servers. For
example, Google

• Document stores

• Move away from storing data in tables. Instead, each document is stored differently depending on
its size and format

CJ Dates twelve commandments

• Local site dependence

• Central site dependence

• Failure independence

• Location transparency

• Fragmentation transparency

• Replication transparency

• Distributed query processing

• Distributed transaction processing

• Hardware independence

• Operating system independence

• Network independence

• Database independence