Home | | Database Management Systems | File Operations

Chapter: Database Management Systems : Trends In Database Technology

File Operations

The database is stored as a collection of files. Each file is a sequence of records. A record is a sequence of fields.

FILE OPERATIONS

 

The database is stored as a collection of files. Each file is a sequence of records. A record is a sequence of fields.

 

One approach:

o assume record size is fixed.

 

o each file has records of one particular type only. o different files are used for different relations.

This case is easiest to implement; will consider variable length records later.

Fixed-Length Records

Simple approach:

 

o Store record i starting from byte n (i 1), where n is the size of each

record.

 

o Record access is simple but records may cross blocks

Modification: do not allow records to cross block boundaries.

  Free List s

o Store the address of the first deleted record in the file header.

o Use this first record to store the address of the second deleted record, and so on.

o Can think of these stored addresses as pointers since they ―point to the location of a

record.

 

o More space efficient representation: reuse space for normal attributes of free records to store pointers. (No pointers stored in in-use records.)

 

Variable-Length Records

o Variable-length records arise in database systems in several ways:

Storage of multiple record types in a file.

 

  Record types that allow variable lengths for one or more fields.

 

  Record types that allow repeating fields (used in some older data models).

o Byte string representation

Attach an end-of-record ( ) control character to the end of each record.

 

Difficulty with deletion. Difficulty with growth.

Variable-Length Records: Slotted Page Structure

 

Slotted page header contains: o number of record entries. o end of free space in the block. o location and size of each record.

 

Records can be moved around within a page to keep them contiguous with no empty space between them; entry in the header must be up-dated.

 

Pointers should not point directly to record — instead they should point to the entry for the record in header.

 

Fixed-length representation:

o reserved space

o pointers

 

Reserved space – can use fixed-length records of a known maximum length; unused space in shorter records filled with a null or end-of-record symbol.

 

Pointer Method

Pointer method

 

A variable-length record is represented by a list of fixed-length records, chained together via pointers.

 

Can be used even if the maximum record length is not known

Disadvantage to pointer structure; space is wasted in all records except the first in a a chain.

 

Solution is to allow two kinds of block in file: Anchor block – contains the first records of chain

Overflow block – contains records other than those that are the first records of chairs.

 

Organization of Records in Files

Heap – a record can be placed anywhere in the file where there is space

 

Sequential – store records in sequential order, based on the value of the search key of each record

 

Hashing – a hash function computed on some attribute of each record; the result specifies in which block of the file the record should be placed

 

Records of each relation may be stored in a separate file. In a clustering NOTES

 

file organization records of several different relations can be stored in the same file

 

Motivation: store related records on the same block to minimize I/O

 

Sequential File Organization

 

Suitable for applications that require sequential processing of the entire file The records in the file are ordered by a search-key

 

Deletion – use pointer chains

Insertion –locate the position where the record is to be inserted

if there is free space insert there

 

if no free space, insert the record in an overflow block In either case, pointer chain must be updated

 

Need to reorganize the file from time to time to restore sequential order

 

Clustering File Organization

o Simple file structure stores each relation in a separate file.

 

o Can instead store several relations in one file using a clustering file organization. o E.g., clustering organization of customer and depositor:

 

Mapping of Objects to Files

 

Mapping objects to files is similar to mapping tuples to files in a relational system; object data can be stored using file structures.

 

Objects in O-O databases may lack uniformity and may be very large; such objects have to managed differently from records in a relational system.

 

o Set fields with a small number of elements may be implemented using data structures such as linked lists.

 

o Set fields with a larger number of elements may be implemented as separate relations in the database.

 

o Se t fields can also be eliminated at the storage level by normalization.

 

Similar to conversion of multivalued attributes of E-R diagrams to relations

 

Objects are identified by an object identifier (OID); the storage system needs a mechanism to locate an object given its OID (this action is called dereferencing).

 

o logical identifiers do not directly specify an object‘s physical location; must maintain an index that maps an OID to the object‘s actual location.

 

o physical identifiers encode the location of the object so the object can be found directly. Physical

 

OIDs typically have the following parts: 

1. a volume or file identifier 

2. a page identifier within the volume or file

3. an offset within the page


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Database Management Systems : Trends In Database Technology : File Operations |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.