Unit – 3

1. Elaborate the usage of data dictionary storage in dbms.(6 M)

2. Apply the role of data dictionary storage in file organization.

Explain with neat diagram.(10 M)

Data Dictionary Storage

A data dictionary, also known as a system catalog, is a
crucial component in a relational database system. It acts as a
centralized repository that stores metadata, which is data
about data. This metadata is essential for managing the
database efficiently.

Purpose of Data Dictionary

The primary purpose of a data dictionary is to provide
information about the database structure and ensure smooth
database management. It helps the system identify various
details like table structures, attribute types, and user
information.

Information Stored in Data Dictionary

The data dictionary stores several types of information,
including:
Relation Information:
 • Table names.
• Number of columns in each table.
• Storage method and location of each table.
Attribute Information:
• Column names.
• Data types and their sizes.
• Position of each column in the table.
View Information:
• Names of all database views.
• Definitions explaining how each view is formed.
Index Information:
• Index names.
• The table associated with each index.
• Attributes used in the index.
• Type of index (e.g., clustered or non-clustered).
User Information:
• Names of authorized users.
• Encrypted passwords for security.
• User groups or roles.
Statistical Data:
• Number of records in each table.
• Storage methods and file details.
Why is the Data Dictionary Important?
The data dictionary is important because:
• It helps the database locate and retrieve data quickly.
• Metadata stored as database tables makes data
management easier using SQL queries.
• Some metadata (like Index Metadata) may be stored in
a simplified format for faster access.

Diagram:
 Conclusion
The data dictionary is a crucial part of any database system,
providing detailed information that ensures smooth database
operation, improved security, and better data management.

1. Explain the measure of query cost in query processing.(6 M)

2. Identify the overview of query processing(10 M)

3. Decide the measures of query cost in query processing.(10M)

1. Overview of Query Processing

Query processing refers to the steps involved in retrieving
data from a database in response to a user's query. The main
steps are:
1. Parsing and Translation:
o The query (e.g., SQL) is translated into an internal
form such as relational-algebra.
o The system verifies the syntax and ensures all
relation names are valid.
2. Optimization:
o The system generates multiple possible query
execution plans.
o It selects the most efficient plan to minimize the
cost.
 3. Evaluation:
o The selected execution plan is executed, and the
result is returned to the user.

2. Measures of Query Cost

The cost of executing a query is measured in terms of:
• Disk Accesses: Reading/writing data blocks from/to the
disk.
• CPU Time: Time taken by the processor to execute
query steps.
• Communication Costs: Relevant in distributed
databases where data is exchanged between systems.

3. Explanation of Query Cost Measurement

In most cases, disk access cost is the most important factor
because disk operations are slower than in-memory tasks.
 For better performance, systems may:
• Use indexes for faster data access.
• Optimize disk access to reduce the number of seeks and
block transfers.
By understanding these steps and cost factors, databases can
efficiently process queries and improve overall performance.

1. What is the basic concept of indices in database ? (6 M)

2. Identify and describe two types of ordered indices used in

database management systems.(10 M)

3. Design the dense and sparse indices(10 M)

4. Develop the ordered indices in indexing.(10 M)

Understanding Ordered Indices in Databases

In database management systems, an index is a special data
structure that helps improve the speed of data retrieval.
Without an index, the database must scan every record in the
table to find the required information, which can be slow for
large datasets. An index acts like a roadmap, helping the
system locate data quickly and efficiently.

Basic Concept of Indices

An index works by creating a separate structure that holds key
values (from one or more columns) along with pointers that
direct the system to the actual records in the table. This
reduces the need for full table scans and enhances search
performance.

Types of Ordered Indices

Ordered indices are a specific type of index where the entries
are stored in sorted order based on the key values. This sorting
makes ordered indices ideal for range queries, sequential
access, and efficient searching. There are two key types of
ordered indices:
1. Dense Index:
o In a dense index, every record in the database has
a corresponding entry in the index. Each entry
contains two parts:
▪ Key Value – The value used for sorting and
searching.
 ▪ Pointer – A reference that points directly to the
location of the record in the database.
o Since every record is indexed, this type of index
offers fast and direct access to individual records.
However, it requires more storage space due to the
large number of entries.

2. Sparse Index:
o In a sparse index, only selected key values are
included in the index. Typically, one key from each
data block (group of records) is stored.
o Sparse indices use less storage compared to dense
indices, but searching may take additional steps.
The system first finds the closest key in the index,
then scans sequentially within that block to locate
the exact record.
 Developing Ordered Indices
Creating ordered indices involves arranging the index entries
in sorted order based on key values. This sorted structure
helps improve search performance using techniques like
binary search, which is faster than scanning data
sequentially.
By combining dense and sparse indices effectively, database
systems can achieve a balance between storage efficiency and
retrieval speed, improving overall database performance.

1. What does file organization mean in a database system?

Can you explain how data is stored and arranged in files?"(6 M)

2. Develop the structure of fixed-length records in file

organization.(6 M)
3. Conclude the concept of variable length record in file
organization.(6 M)

4. Discuss how sequential files are structured, and where sequential

file organization is most effective compared to other file
organization methods.(6 M)

5. Examine the concept organizing records in the file of

different types.(6 M)

6. Design the organization of records in files(10 M)

7. Explain the variable length records in file organization.(10 M)

8. Explain the variable length records in file organization.(10 M)

9. Explain about the various technique used in file

organization.(10 M)

[Link] the importance of multitable clustering file organization

in data storage concepts with instructor and department
relation.(6M)

File Organization in a Database System

What is File Organization?

File organization refers to how data is stored and arranged in
database files. These files are saved on disks and managed by
the operating system.
How is Data Stored in Files?
 • Data is stored as records inside blocks. A block is a
fixed-size storage unit that helps in storing and
transferring data efficiently.
• Most databases use block sizes between 4 to 8 KB.
• Each block can hold multiple records, but no record is
split across two blocks. This makes data access faster and
simpler.
• Fixed-length records are easier to manage, while
variable-length records need special techniques for
storage.
• For large data like images or videos, the data is stored
separately with a pointer in the record to locate it.
This organized method improves database performance and
ensures smooth data handling.

Types of Records:
1. Fixed-Length Records
2. Variable-Length Records

Structure of Fixed-Length Records in File

Organization
Definition:
A fixed-length record is a record where each field has a
predefined maximum size, ensuring that all records occupy
the same amount of space.
Example Structure:
Consider a university database storing instructor records. Each
record has the following attributes:

Total Size Calculation:

• ID: 5 bytes
• Name: 20 bytes
• Department Name: 20 bytes
• Salary: 8 bytes
Total Record Size = 53 bytes
Data Storage Process:
• Each block holds as many complete records as possible
by dividing the block size by the record size. Any
leftover space in the block remains unused.
• Each record is stored sequentially without gaps.
Deletion Process:
• When a record is deleted, the system avoids shifting all
records. Instead, the deleted record's space is marked as
free.
• A file header stores the address of the first deleted
record. Each deleted record holds a pointer to the next
available space, forming a linked list (free list) of empty
spaces.
Insertion Process:
 • New records are inserted in the space marked by the
header pointer. If no free space exists, the new record is
added at the end of the file.
This structure ensures efficient storage and simplifies
insertion and deletion in fixed-length records.

Variable-Length Records in File Organization

Variable-length records are used in database systems when the
size of records is not fixed. Unlike fixed-length records, these
records may vary in size depending on the data stored. They
are commonly used when:
• A file contains multiple types of records.
• Some attributes have variable sizes (e.g., names or
addresses).
• Some attributes can repeat, such as arrays or lists.
Structure of Variable-Length Records
A variable-length record has two main parts:
1. Fixed-Length Attributes:
o These are fields that have a constant size, like
numbers or dates.
o They are stored at the beginning of the record for
easier access.
2. Variable-Length Attributes:
o These are fields that can change in size, like
VARCHAR data types.
 o Each variable-length attribute is represented by two
values:
o Offset: Indicates where the data starts in the record.
o Length: Specifies the size of the data.
o This helps in locating and accessing variable-length
attributes efficiently.
3. Null Bitmap:
o This is a special structure that marks attributes that
have NULL values.
o For example, if an attribute is empty, its
corresponding bit in the bitmap is set to 1.

Storage in Blocks (Slotted-Page Structure)

Variable-length records are stored in blocks using a special
structure called the slotted-page structure. Each block has:
• Header: Contains information such as:
o Number of records in the block.
o Position where free space begins.
o An array with the location and size of each record.
 • Records Storage: Records are stored from the end of the
block towards the start.
• Free Space: This area lies between the header and the
first record, ensuring efficient use of space.

Handling Insertions and Deletions:

• Insertion: New records are added in the free space, and
the header is updated.
• Deletion: The deleted record’s space is marked as empty.
Other records may be shifted to keep the free space
together.

Organization of Records in Files

1. Heap File Organization:
o Records are stored in any empty space available.
o No particular order is followed, making it easy to
insert records but slower to search.
2. Sequential File Organization:
 o Records are stored in sorted order based on a chosen
key.
o It helps in faster searching for sorted data but
inserting new records takes more time.
3. Hashing File Organization:
o A hash function is used to decide where to store
each record.
o This method allows fast searching but is not good
for finding records in a sequence.
4. Multitable Clustering File Organization:
o Records from related tables are stored together in
one file.
o This makes fetching related data faster and more
efficient.

Multitable Clustering File Organization

Multitable clustering is a file organization technique where

related records from two or more relations are stored together
in the same block to improve query performance, especially
for join operations.
Introduction
Multitable clustering is a file organization technique that
stores related records from multiple relations in the same
block, improving query performance.
Separate File Storage
In traditional database systems, each relation is stored in a
separate file, which is simple to implement and suitable for
small-scale databases.
Limitations of Separate File Storage
For large databases, managing multiple individual files
becomes inefficient, making it harder to optimize data
retrieval.
Alternative Approach
To improve efficiency, large database systems often use one
large file to store all relations and manage them internally.
Concept of Multitable Clustering
In this method, related records from multiple relations are
stored together in the same block to reduce the number of
block reads during join operations.
Example of Multitable Clustering
For instance, in a university database, department and
instructor records are stored near each other based on their
dept_name values to speed up join queries.
Advantages of Multitable Clustering
This method enhances performance by minimizing disk
accesses for join queries.
Challenges of Multitable Clustering
Multitable clustering may slow down queries that retrieve data
from only one relation.
Solution for Efficient Access
To address this challenge, pointer chains can be used to
efficiently locate and access records of the same relation.
Sequential File Organization
Definition:
A sequential file is a type of file organization where records
are stored in sorted order based on a search key. The search
key can be any attribute or combination of attributes; it doesn't
have to be the primary key or a superkey.
Structure of Sequential Files
1. Pointer Chaining:
o Records are linked using pointers to maintain the
search-key order.
o Each record points to the next record in the sorted
order.
2. Physical Storage:
 o Records are stored physically in search-key order or
as close to it as possible to minimize block access
during sequential processing.
3. Insertion Process:
o Locate the record that comes before the new record
in the search-key order.
o If there’s free space in the same block, insert the
new record there.
o If no space is available, insert the new record in an
overflow block and adjust pointers accordingly.
4. Deletion Process:
o Deletions are handled by maintaining pointer
chains, ensuring records remain linked in the correct
order.
5. Reorganization:
o Over time, frequent insertions may disturb the
sorted order.
o When the file becomes inefficient, reorganization is
required to restore the sequential order.
o This process is time-consuming and is usually done
during low system load.

Conclusion
Effective file organization improves data storage, access, and
management. Choosing the right method, such as heap,
sequential, or hashing, ensures better performance and faster
data retrieval based on system needs.