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
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.