Please draw ERD Diagram. Sample diagram format also attached

profilekushal-kumar
ch08.ppt
Home>Information Systems homework help>Please draw ERD Diagram. Sample diagram format also attached

Chapter 8
Physical Database Design

BLCN-534: Fundamentals of Database Systems

Chapter Objectives

8-*

  • Describe the concept of physical database design.
  • Describe how a disk device works.
  • Describe the principles of file organizations and access methods.

Chapter Objectives

1. Describe the concept of physical database design.

2. Describe how a disk device works.

3. Describe the principles of file organizations and access methods.

4. Describe how simple linear indexes and B+-tree indexes work.

5. Describe how hashed files work.

6. List and describe the inputs to the physical database design process.

7. Perform physical database design and improve database performance using a variety of techniques ranging from adding indexes to denormalization.

8-*

Database Performance

Factors Affecting Application and Database Performance

Application Factors

Need for Joins

Need to Calculate Totals

Data Factors

Large Data Volumes

Database Structure Factors

Lack of Direct Access

Clumsy Primary Keys

Data Storage Factors

Related Data Dispersed on Disk

Business Environment Factors

Too Many Data Access Operations

Overly Liberal Data Access

8-*

Physical Database Design

  • The process of modifying a database structure to improve the performance of the run-time environment.
  • We are going to modify the third normal form tables produced by the logical database design techniques to make the applications that will use them run faster.

8-*

Disk Storage

  • Primary (Main) Memory - where computers execute programs and process data
  • Very fast
  • Permits direct access
  • Has several drawbacks
  • relatively expensive
  • not transportable
  • is volatile

8-*

Disk Storage

  • Secondary Memory - stores the vast volume of data and the programs that process them
  • Data is loaded from secondary memory into primary memory when required for processing.

8-*

Primary and Secondary Memory

  • When a person needs some particular information that’s not in her brain at the moment, she finds a book in the library that has the information and, by reading it, transfers the information from the book into her brain.

8-*

How Disk Storage Works

Disks come in a variety of types and capacities

Multi-platter, aluminum or ceramic disk units

Removable, external hard drives.

Provide a direct access capability to the data.

8-*

How Disk Storage Works

  • Several disk platters are stacked together, and mounted on a central spindle, with some space in between them.
  • Referred to as “the disk.”

8-*

How Disk Storage Works

  • The platters have a metallic coating that can be magnetized, and this is how the data is stored, bit-by-bit.

8-*

Access Arm Mechanism

  • The basic disk drive has one access arm mechanism with arms that can reach in between the disks.
  • At the end of each arm are two read/write heads.
  • The platters spin, all together as a single unit, on the central spindle, at a high velocity.

8-*

Tracks

  • Concentric circles on which data is stored, serially by bit.
  • Numbered track 0, track 1, track 2, and so on.

8-*

Cylinders

  • A collection of tracks, one from each recording surface, one directly above the other.
  • Number of cylinders in a disk = number of tracks on any one of its recording surfaces.

8-*

Cylinders

  • The collection of each surface’s track 76, one above the other, seem to take the shape of a cylinder.
  • This collection of tracks is called cylinder 76.

8-*

Cylinders

  • Once we have established a cylinder, it is also necessary to number the tracks within the cylinder.
  • Cylinder 76’s tracks.

8-*

Steps in Finding and Transferring Data

  • Seek Time - The time it takes to move the access arm mechanism to the correct cylinder from whatever cylinder it’s currently positioned.
  • Head Switching - Selecting the read/write head to access the required track of the cylinder.
  • Rotational Delay - Waiting for the desired data on the track to arrive under the read/write head as the disk is spinning.
  • Transfer Time - The time to actually move the data from the disk to primary memory once the previous 3 steps have been completed

8-*

File Organizations and Access Methods

  • File Organization - the way that we store the data for subsequent retrieval.
  • Access Method - The way that we retrieve the data, based on it being stored in a particular file organization.

8-*

Achieving Direct Access

  • An index tool.
  • Hashing Method - a way of storing and retrieving records.
  • If we know the value of a field of a record that we want to retrieve, the index or hashing method will pinpoint its location in the file and instruct the hardware mechanisms of the disk device where to find it.

8-*

The Index

  • Principal is the same as that governing the index in the back of a book
  • The items of interest are copied over into the index, but the original text is not disturbed in any way.
  • The items in the index are sorted.
  • Each item in the index is associated with a “pointer.”

8-*

Simple Linear Index

  • Index is ordered by Salesperson Name field.
  • The first index record shows Adams 3 because the record of the Salesperson file with salesperson name Adams is at relative record location 3 in the Salesperson file.

8-*

Simple Linear Index

  • An index built over the City field.
  • An index can be built over a field with nonunique values.

8-*

Simple Linear Index

  • An index built over the Salesperson Number field.
  • Indexed sequential file - the file is stored on the disk in order based on a set of field values (salesperson numbers), and an index is built over that same field.

8-*

Simple Linear Index

8-*

Simple Linear Index

  • French 8, would have to be inserted between the index records for Dickens and Green to maintain the crucial alphabetic sequence.
  • Would have to move all of the index records from Green to Taylor down one record position.
  • Not a good solution for indexing the records of a file.

8-*

B+-tree Index

The most common data indexing system in use today.

Unlike simple linear indexes, B+-trees are designed to comfortably handle the insertion of new records into the file and to handle record deletion.

8-*

B+-tree Index

  • An arrangement of special index records in a “tree.”
  • A single index record, the “root,” at the top, with “branches” leading down from it to other “nodes.”

8-*

B+-tree Index

  • The lowest level nodes are called “leaves.”
  • Think of it as a family tree.

8-*

B+-tree Index

  • Each key value in the tree is associated with a pointer that is the address of either a lower level index record or a cylinder containing the salesperson records.
  • The index records contain salesperson number key values copied from certain of the salesperson records.

8-*

B+-tree Index

8-*

B+-tree Index

  • Each index record, at every level of the tree, contains space for the same number of key value/pointer pairs.
  • Each index record is at least half full.
  • The tree index is small and can be kept in main memory indefinitely for a frequently accessed file.

8-*

B+-tree Index

  • This is an indexed-sequential file, because the file is stored in sequence by the salesperson numbers and the index is built over the Salesperson Number field.
  • B+-tree indexes can also be used to index nonkey, nonunique fields.
  • In general, the storage unit for groups of records can be the cylinder or any other physical device subunit.

8-*

B+-tree Index

  • Say that a new record with salesperson number 365 must be inserted.
  • Suppose that cylinder 5 is completely full.

8-*

B+-tree Index

  • The collection of records on the entire cylinder has to be split between cylinder 5 and an empty reserve cylinder, say cylinder 11.
  • There is no key value/pointer pair representing cylinder 11 in the tree index.

8-*

B+-tree Index

  • The index record, into which the key for the new cylinder should go, which happens to be full, is split into two index records.
  • The now five key values and their associated pointers are divided between them.

8-*

Indexes

  • Can be built over any field (unique or nonunique) of a file.
  • Can also be built on a combination of fields.
  • In addition to its direct access capability, an index can be used to retrieve the records of a file in logical sequence based on the indexed field.

8-*

Indexes

  • Many separate indexes into a file can exist simultaneously. The indexes are quite independent of each other.
  • When a new record is inserted into a file, an existing record is deleted, or an indexed field is updated, all of the affected indexes must be updated.

8-*

Hashed Files

The number of records in a file is estimated, and enough space is reserved on a disk to hold them.

Additional space is reserved for additional overflow records.

8-*

Hashed Files

To determine where to insert a particular record of the file, the record’s key value is converted by a hashing routine into one of the reserved record locations on the disk.

To find and retrieve the record, the same hashing routine is applied to the key value during the search.

8-*

Division-Remainder Method

Divide the key value of the record that we want to insert or retrieve by the number of record locations that we have reserved.

Perform the division, discard the quotient, and use the remainder to tell us where to locate the record.

8-*

A Hashed File

Storage area for 50 records plus overflow records.

Collision - more than one key value hashes to the same location.

The two key values are called “synonyms.”

8-*

Hashed Files

  • Hashing disallows any sequential storage based on a set of field values.
  • A file can only be hashed once, based on the values of a single field or a single combination of fields.
  • If a file is hashed on one field, direct access based on another field can be achieved by building an index on the other field.

8-*

Hashed Files

  • Many hashing routines have been developed.
  • The goal is to minimize the number of collisions, which can slow down retrieval performance.
  • In practice, several hashing routines are tested on a file to determine the best “fit.”
  • Even a relatively simple procedure like the division-remainder method can be fine-tuned.

8-*

Hashed Files

  • A hashed file must occasionally be reorganized after so many collisions have occurred that performance is degraded to an unacceptable level.
  • A new storage area with a new number of storage locations is chosen, and the process starts all over again.

8-*

Inputs to Physical
Database Design

  • Physical database design starts where logical database design ends.
  • The well structured relational tables produced by the conversion from ERDs or by the data normalization process form the starting point for physical database design.

8-*

More Inputs to Physical Database Design

Inputs Into the Physical Database Design Process

The Tables Produced by the Logical Database Design Process

Business Environment Requirements

Response Time Requirements

Throughput Requirements

Data Characteristics

Data Volume Assessment

Data Volatility

Application Characteristics

Application Data Requirements

Application Priorities

Operational Requirements

Data Security Concerns

Backup and Recovery Concerns

Hardware and Software Characteristics

DBMS Characteristics

Hardware Characteristics

8-*

The Tables Produced by the Logical Database Design Process

  • Form the starting point of the physical database design process.
  • Reflect all of the data in the business environment.
  • Are likely to be unacceptable from a performance point of view and must be modified in physical database design.

8-*

Business Environment Requirements: Response Time Requirements

  • Response time is the delay from the time that the Enter Key is pressed to execute a query until the result appears on the screen.
  • What are the response time requirements?

8-*

Business Environment Requirements: Throughput Requirements

  • Throughput is the measure of how many queries from simultaneous users must be satisfied in a given period of time by the application set and the database that supports it.

8-*

Data Characteristics

  • Data Volume Assessment
  • How much data will be in the database?
  • Roughly how many records is each table expected to have?
  • Data Volatility
  • Refers to how often stored data is updated.

8-*

Application Characteristics

  • What is the nature of the applications that will use the data?
  • Which applications are the most important to the company?
  • Which data will be accessed by each application?

8-*

Application Characteristics: Data Requirements

  • Which database tables does each application require for its processing?
  • Do the applications require that tables be joined?
  • How many applications and which specific applications will share particular database tables?
  • Are the applications that use a particular table run frequently or infrequently?

8-*

Application Characteristics: Priorities

When a modification to a table proposed during physical design that’s designed to help the performance of one application hinders the performance of another application, which of the two applications is the more critical to the company?

8-*

Operational Requirements: Data Security, Backup and Recovery

  • Data Security
  • Protecting data from theft or malicious destruction and making sure that sensitive data is accessible only to those employees of the company who have a “need to know.”
  • Backup and Recovery
  • Being able to recover a table or a database that has been corrupted or lost due to hardware or software failure to the recovery of an entire information system after a natural disaster.

8-*

Hardware and Software Characteristics

  • DBMS Characteristics
  • For example, exact nature of indexes, attribute data type options, and SQL query features, which must be known and taken into account during physical database design.
  • Hardware Characteristics
  • Processor speeds and disk data transfer rates.

8-*

Physical Database Design Techniques

Physical Design Categories and Techniques That DO NOT Change the Logical Design

Adding External Features

Adding Indexes

Adding Views

Reorganizing Stored Data

Clustering Files

Splitting a Table into Multiple Tables

Horizontal Partitioning

Vertical Partitioning

Splitting-Off Large Text Attributes

8-*

Physical Database Design Techniques

Physical Design Categories and Techniques That DO Change the Logical Design

Changing Attributes in a Table

Substituting Foreign Keys

Adding Attributes to a Table

Creating New Primary Keys

Storing Derived Data

Combining Tables

Combine Tables in One-to-One relationships

Alternative for Repeating Groups

Denormalization

Adding New Tables

Duplicating Tables

Adding Subset Tables

8-*

Adding External Features: Adding Indexes

Which attributes or combinations of attributes should you consider indexing in order to have the greatest positive impact on the application environment?

Attributes that are likely to be prominent in direct searches

Primary keys

Search attributes

Attributes that are likely to be major players in operations, such as joins, SQL SELECT ORDER BY clauses and SQL SELECT GROUP BY clauses.

8-*

Adding External Features: Adding Indexes

What potential problems can be caused by building too many indexes?

Indexes are wonderful for direct searches. But when the data in a table is updated, the system must take the time to update the table’s indexes, too.

8-*

General Hardware Company With Some Indexes

8-*

Adding External Features: Adding Views

  • Doesn’t change the logical design.
  • No data is physically duplicated.
  • An important device in protecting the security and privacy of data.

8-*

Reorganizing Stored Data

  • Doesn’t change the logical design.
  • No data is physically duplicated.
  • Clustering Files
  • Houses related records together on a disk.

8-*

Reorganizing Stored Data: Clustering Files

  • The salesperson record for salesperson 137, Baker, is followed on the disk by the customer records for customers 0121, 0933, 1047, and 1826.

8-*

Splitting a Table Into
Multiple Tables

  • Horizontal Partitioning
  • Vertical Partitioning
  • Splitting-Off Large Text Attributes

8-*

Splitting a Table Into
Multiple Tables: Horizontal Partitioning

  • The rows of a table are divided into groups, and the groups are stored separately on different areas of a disk or on different disks.
  • Useful in managing the different groups of records separately for security or backup and recovery purposes.
  • Improve data retrieval performance.
  • Disadvantage: retrieval of records from more than one partition can be more complex and slower.

8-*

Splitting a Table Into
Multiple Tables: Horizontal Partitioning

8-*

Splitting a Table Into
Multiple Tables: Vertical Partitioning

  • The separate groups, each made up of different columns of a table, are created because different users or applications require different columns.
  • Each partition must have a copy of the primary key.

8-*

Splitting a Table Into
Multiple Tables: Vertical Partitioning

8-*

The Salesperson table

Splitting a Table Into
Multiple Tables: Splitting Off Large Text Attributes

  • A variation on vertical partitioning involves splitting off large text attributes into separate partitions.
  • Each partition must have a copy of the primary key.

8-*

Changing Attributes
in a Table

  • Changes the logical design.
  • Substituting a Foreign Key
  • Substitute an alternate key (Salesperson Name, assuming it is a unique attribute) as a foreign key.
  • Saves on the number of performance-slowing joins.

8-*

Adding Attributes to a Table: Creating New Primary Keys

  • Changes the logical design.
  • In a table with no single attribute primary key, indexing a multi-attribute key would likely be clumsy and slow.
  • Create a new serial number attribute primary key for the table.

8-*

Adding Attributes to a Table: Creating New Primary Keys

  • The current two-attribute primary key of the CUSTOMER EMPLOYEE table can be replaced by one, new attribute.

8-*

Adding Attributes to a Table: Storing Derived Data

  • Calculate answers to certain queries once and store them in the database.

8-*

Combining Tables

  • If two tables are combined into one, then there must surely be situations in which the presence of the new single table allows us to avoid joins that would have been necessary when there were two tables.

  • Combination of Tables in One-to-One Relationships
  • Alternatives for Repeating Groups
  • Denormalization

8-*

Combining Tables: Combination of Tables in One-to-One Relationships

  • Advantage: if we ever have to retrieve detailed data about a salesperson and his office in one query, it can now be done without a join.

8-*

Combining Tables: Combination of Tables in One-to-One Relationships

  • Disadvantages:
  • the tables are no longer logically as well as physically independent.
  • retrievals of salesperson data alone or of office data alone could be slower than before.
  • storage of data about unoccupied offices is problematic and may require a reevaluation of which field should be the primary key.

8-*

Combining Tables: Alternatives for Repeating Groups

  • If repeating groups are well controlled, they can be folded into one table.

8-*

Combining Tables: Denormalization

  • It may be necessary to take pairs of related, third normal form tables and to combine them, introducing possibly massive data redundancy.
  • Unsatisfactory response times and throughput may mandate eliminating run-time joins.

8-*

Combining Tables: Denormalization

  • Since a salesperson can have several customers, a particular salesperson’s data will be repeated for each customer he has.

8-*

Combining Tables: Denormalization

8-*

Adding New Tables

  • Duplicating Tables
  • Duplicate tables and have different applications access the duplicates.
  • Adding Subset Tables
  • Duplicate only those portions of a table that are most heavily accessed.
  • Assign subsets to different applications to ease the performance crunch.

8-*

Good Reading Bookstores: Problem

  • Assume that Good Reading’s headquarters frequently needs to quickly find the details of a book, based on either its book number or its title, together with details about its publisher.
  • If a join takes too long, resulting in unacceptable response times, throughput, or both, what are the possibilities in terms of physical design that can improve the situation?

8-*

Good Reading Bookstores: Solutions

  • The Book Number attribute and the Book Title attributes in the PUBLISHER table can each have an index built on them to provide direct access, since the problem says that books are going to be searched for based on one of these two attributes.
  • The two join attributes—the Publisher Name attribute of the PUBLISHER table and the Publisher Name attribute of the BOOK table—can each have an index built on them to help speed up the join operation.

8-*

Good Reading Bookstores: Solutions

  • If the DBMS permits it, the two tables can be clustered, with the book records associated with a particular publisher stored near that publisher’s record on the disk.
  • The two tables can be denormalized, with the appropriate publisher data being appended to each book record (and the PUBLISHER table being eliminated).

8-*