The database is stored as a collection of files. Each file is a sequence of records. A record is a sequence of fields.
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.
o Store record i starting from byte n (i – 1), where n is the size of each
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
o More space efficient representation: reuse space for normal attributes of free records to store pointers. (No pointers stored in in-use 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.
o reserved space
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.
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