UNIT V IMPLEMENTATION & STORAGE

RAID-File Organizaion – Organization of Records in Files – Data Dictionary Storage – Column Oriented Storage - Indexing and Hashing –Ordered
Indices – B+ tree Index Files – B tree Index Files – Static Hashing – Dynamic Hashing – Query Processing Overview

FILE ORGANIZATION
 The database is stored as a collection of files.
 Each file is a sequence of records.
 A record is a sequence of fields.
 Classifications of records
– Fixed length record
– Variable length record
 Fixed length record approach:
Assume record size is fixed each file has records of one particular type only different files are used for
different relations
Simple approach
- Record access is simple
Example pseudo code
type account = record
account_number char(10);
branch_name char(22);
balance numeric(8);
end
Total bytes 40 for a record

Two problems
- Difficult to delete record from this structure.
- Some record will cross block boundaries, that is part of the record will be stored in one block and
part in another. It would require two block accesses toread or write
Reuse the free space alternatives:
– move records i + 1, . . ., n to n i, . . . , n – 1
– do not move records, but link all free records on a
free list
– Move the final record to deleted record place.
Free Lists
 Store the address of the first deleted record in the file header.
 Use this first record to store the address of the second deleted record, and so on

Prepared by [Link],AP(SG)/CSE/NIET
Variable-Length Records
Byte string representation
 Attach an end-of-record ( ) control character to the end of each record
 Difficulty with deletion

Disadvantage
It is not easy to reuse space occupied formerly by deleted record.
There is no space in general for records grows longer

Slotted Page Structure

Slotted page header contains:

– number of record entries
– end of free space in the block
– location and size of each record

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 chains.

Prepared by [Link],AP(SG)/CSE/NIET
 ORGANIZATION OF RECORDS IN FILES
• Sequential – store records in sequential order, based on the value of the search key of each record
• Heap – a record can be placed anywhere in the file where there is space
• 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
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

INDEXING AND HASHING

Basic Concepts
 Indexing mechanisms used to speed up access to desired data.
– E.g., author catalog in library
 Search Key - attribute to set of attributes used to look up records in a file.
An index file consists of records (called index entries) of the form

Search-key pointer
 Index files are typically much smaller than the original file
 Two basic kinds of indices:
– Ordered indices: search keys are stored in sorted order
– Hash indices: search keys are distributed uniformly across ―buckets and by using a hash
function the values are determined.
Ordered Indices
 In an ordered index, index entries are stored sorted on the search key value.
 Primary index: in a sequentially ordered file, the index whose search key specifies the sequential order of
the file.
 Secondary index: an index whose search key specifies an order different from the sequential order of the
file.
Types of Ordered Indices
 Dense index
 Sparse index
Dense Index Files

Prepared by [Link],AP(SG)/CSE/NIET
  Dense index — Index record appears for every search-key value in the file.

Sparse Index Files

 Sparse Index
contains index records for only some search-key values.
 To locate a record with search-key value K we:
– Find index record with largest search-key value that is less than or equal to
Searchfile sequentially starting at the record to which the index record points

Multilevel Index
 If primary index does not fit in memory, access becomes expensive.
 To reduce number of disk accesses to index records, treat primary index kept on disk as a sequential file and
construct a sparse index on it.
– outer index – a sparse index of primary index
– inner index – the primary index file
 If even outer index is too large to fit in main memory, yet another level of index can be created, and so on.

Prepared by [Link],AP(SG)/CSE/NIET
Index Update: Deletion
If deleted record was the only record in the file with its particular search-key value, the search-key is deleted from
the index also.
 Single-level index deletion:
– Dense indices – deletion of search-key is similar to file record deletion.
– Sparse indices – if an entry for the search key exists in the index, it is deleted by replacing the entry
in the index with the next search-key value in the file (in search-key order). If the next search-key
value already has an index entry, the entry is deleted instead of being replaced.
Index Update: Insertion
 Single-level index insertion:
– Performa lookup using the search-key value appearing in the record to be inserted.
– Dense indices – if the search-key value does not appear in the index, insert it.
– Sparse indices – if index stores an entry for each block of the file, no change needs to be made to
the index unless a new block is created. In this case, the first search-key value appearing in the new
block is inserted into the index.
Secondary Index on balance field of account

Primary and Secondary Indices

 Secondary indices have to be dense.
 Indices offer substantial benefits when searching for records.
 When a file is modified, every index on the file must be updated, Updating indices imposes overhead on
database modification.
 Sequential scan using primary index is efficient, but a sequential scan using a secondary index is expensive
– each record access may fetch a new block from disk
`
B+-TREE INDEX FILES
+ +
Example of a B -tree : B -tree for account file (n = 3)

Prepared by [Link],AP(SG)/CSE/NIET
  Disadvantage of indexed-sequential files: performance degrades as file grows, since many overflow blocks
get created. Periodic reorganization of entire file is required.
 Advantage of B+-tree index files: automatically reorganizes itself with small, local, changes, in the face of
insertions and deletions. Reorganization of entire file is not required to maintain performance.
 Disadvantage of B+-trees: extra insertion and deletion overhead, space overhead.

A B+-tree is a rooted tree satisfying the following properties:

 All paths from root to leaf are of the same length
 Each node that is not a root or a leaf has between [n/2] and n children.
 Special cases:
– If the root is not a leaf, it has at least 2 children.
– If the root is a leaf, it can have between 0 and (n–1) values.
B+-Tree Node Structure
 Typical node

– Ki are the search-key values

– Pi are pointers to children (for non-leaf nodes) or pointers to records or buckets of records (for leaf
nodes).
 The search-keys in a node are ordered
K1 < K2 < K3 < . . . < Kn–1
Properties of Leaf Nodes
 For i = 1, 2, . . ., n–1, pointer Pi either points to a file record with search-key value Ki, or to a bucket of
pointers to file records, each record having search-key value Ki.
 Pn points to next leaf node in search-key order

Non-Leaf Nodes in B+-Trees

Non leaf nodes form a multi-level sparse index on the leaf nodes. For a non-leaf node with m pointers:
– All the search-keys in the subtree to which P1 points are less than K1.

Example of a B+-tree: B+-tree for account file (n = 3)

Prepared by [Link],AP(SG)/CSE/NIET
B+-tree for account file (n = 5)

 Non-leaf nodes other thanroot must have between 3 and 5 children ((n/2 and n with n =5).
 Root must have at least 2 children.
Observations about B+-trees
 Since the inter-node connections are done by pointers, ―logically‖ close blocks need not be ―physically‖
close.
 The B+-tree contains a relatively small number of levels thus searches can be conducted efficiently.
 Insertions anddeletions to the main file can be handled efficiently.
Updates on B+-Trees: Insertion
 Find the leaf node in which the search-key value would appear
 If the search-key value is already there in the leaf node, record is added to file and if necessary a pointer is
inserted into the bucket.
 If the search-key value is not there, then add the record to the main file and create a bucket if
[Link]:
– If there is room in the leaf node, insert (key-value, pointer) pair in the leaf node otherwise, split the
node.
Example: B -Tree before and after insertion of ―Clearview‖
+

Updates on B+-Trees: Deletion

• Find the recordto be deleted, and remove it from the main file and from the bucket (if present)
• Remove (search-key value, pointer) from the leaf node if there is no bucket or if the bucket has become
empty
• If the node has too few entries due to the removal, and the entries in the node and a sibling fit into a single
node, then
– Insert all the search-key values in the two nodes into a single node (the one on the left), and delete

Prepared by [Link],AP(SG)/CSE/NIET
 the other node.
– Delete the pair (Ki–1, Pi), where Pi is the pointer to the deleted node, from its parent, recursively
using the above procedure.

Before and after deleting “Downtown”

• The removal of the leaf node containing ―Downtown‖ did not result in its parent having too little pointers.
So the cascaded deletions stopped with the deleted leaf node‘s parent.
Deletion of “Perryridge” from result of previous example

• Node with ―Perryridge‖ becomes empty and merged with its sibling.
• Root node then had only one child, and was deleted and its child became the new root node
B+-Tree File Organization
• The leaf nodes in a B+-tree file organization store records, instead of pointers.
• Since records are larger than pointers, the maximum number of records that can be stored in a leaf node is
less than the number of pointers in a nonleaf node.
• Leaf nodes are still required to be half full.
• Insertion and deletion are handled in the same way as insertion and deletion of entries in a B+-tree index.

Prepared by [Link],AP(SG)/CSE/NIET
 B-TREE INDEX FILES
• Similar to B+-tree, but B-tree allows search-key values to appear only once; eliminates redundant storage of
search keys.
• Search keys in nonleaf nodes appear nowhere else in the B-tree; an additional pointer field for each search
key in a nonleaf node must be included.

Generalized B-tree leaf node

Nonleaf node – pointers Bi are the bucket or file record pointers.

B+-tree on same data

Advantages of B-Tree indices:

– May use less tree nodes than a corresponding B+-Tree.
– Sometimes possible to find search-key value before reaching leaf node.
Disadvantages of B-Tree indices:
– Only small fraction of all search-key values are found early
– Non-leaf nodes are larger, so fan-out is reduced (no. of pointers). Thus, B-Trees typically have
greater depth than corresponding B+-Tree
– Insertion and deletion more complicated than in B+-Trees
– Implementation is harder than B+-Trees.

HASHING
• Hashing is an effective technique to calculate the direct location of a data record on the disk without using
index structure.
• Hashing uses hash functions with search keys as parameters to generate the address of a data record.
Hash Organization
Bucket
A hash file stores data in bucket format. Bucket is considered a unit of storage. A bucket typically
stores one complete disk block, which in turn can store one or more records.
Hash Function
A hash function, h, is a mapping function that maps all the set of search-keys K to the address
where actualrecords are placed. It is a function from search keys to bucket addresses.
 Worst hash function maps all search-key values to the same bucket.

Prepared by [Link],AP(SG)/CSE/NIET
  An ideal hash function is uniform, i.e., each bucket is assigned the same number of search-key values from
the set of all possible values.
 Ideal hash function is random, so each bucket will have the same number of records.
Types
• Static Hashing
• Dynamic Hashing
STATIC HASHING
 In static hashing, when a search-key value is provided, the hash function always computes the same address.
 For example, if mod-4 hash function is used, then it shall generate only 5 values. The output address shall
always be same for that function.
 The number of buckets provided remains unchanged at all times.
Example of Hash File Organization
 There are 10 buckets,
 The hash function returns the sum of the binary representations of the characters modulo 10
– E.g. h(Perryridge) = 5 h(Round Hill) = 3 h(Brighton) = 3

Operation
 Insertion − When a record is required to be entered using static hash, the hash function h computes the
bucket address for search key K, where the record will be stored.
Bucket address = h(K)
 Search − When a record needs to be retrieved, the same hash function can be used to retrieve the address of
the bucket where the data is stored.
 Delete − This is simply a search followed by a deletion operation.
Handling of Bucket Overflows
 Bucket overflow can occur because of
– Insufficient buckets
– Skew in distribution of records. This can occur due to :
• multiple records have same search-key value
 Although the probability of bucket overflow can be reduced, it cannot be eliminated; it is handled by using
overflow buckets.
 Overflow chaining – the overflow buckets of a given bucket are chained together in a linked list.
 Above scheme is called closed hashing.
– An alternative, called open hashing, which does not use overflow buckets, is not suitable for
database applications.

Prepared by [Link],AP(SG)/CSE/NIET
Hash Indices
• Hashing can be used not only for file organization, but also for index-structure creation.
• A hash index organizes the search keys, with their associated record pointers, into a hash file structure.
• Hash indices are always secondary indices

Deficiencies of Static Hashing

 In static hashing, function h maps search-key values to a fixed set of B of bucket addresses.
– Databases grow with time. If initial number of buckets is too small, performance will degrade due
to too much overflows.
– If file size at some point in the future is anticipated and number of buckets allocated accordingly,
significant amount of space will be wasted initially.
– If database shrinks, again space will be wasted.
 These problems canbe avoided by using techniques that allow the number of buckets to be modified
dynamically.
DYNAMIC HASHING
• Good for database that grows and shrinks in size
• Allows the hashfunction to be modified dynamically
• Extendable hashing – one form of dynamic hashing
– Hash function generates values over a large range — typically b-bit integers, with b = 32.
– At any time use only a prefix of the hash function to index into a table of bucketaddresses.
– Let the length of the prefix be i bits, 0  i  32.
– Bucket address table size = 2i. Initially i = 0
– Value of i grows and shrinks as the size of the database grows and shrinks.
– Multiple entries in the bucket address table may point to a bucket.
– Thus, actualnumber of buckets is < 2i

Prepared by [Link],AP(SG)/CSE/NIET
 – The number of buckets also changes dynamically due to coalescing and splitting of buckets.
General Extendable Hash
In this structure, i2 = i3 = i, whereas i1 = i – 1

Insertion in Extendable Hash Structure

To split a bucket j when inserting record with search-key value Kj:
 If i > ij (more than one pointer to bucket j)
– allocate a new bucket z, and set ij = iz = (ij + 1)
– Update the second half of the bucket address table entries originally pointing to j, to point toz
– remove each record in bucket j and reinsert (in j or z)
– recompute new bucket for Kj and insert record in the bucket (further splitting is required if the
bucket is still full)
 If i = ij (only one pointer to bucket j)
– If i reaches some limit b, or too many splits have happened in this insertion, create an overflow
bucket
 Else
– increment i and double the size of the bucket address table.
– replace each entry in the table by two entries that point to the same bucket.
– recompute new bucket address table entry for Kj
Now i > ij so use the first case above.
Deletion in Extendable Hash Structure
 To delete a key value,
– locate it in its bucket and remove it.
– The bucket itself can be removed if it becomes empty (with appropriate updates to the bucket
address table).
– Coalescing of buckets can be done (can coalesce only with a ―buddy‖ bucket having same value of ij
and same ij –1 prefix, if it is present)
– Decreasingbucket address table size is also possible
• Note: decreasing bucket address table size is an expensive operation and should be done
only if number of buckets becomes much smaller than the size of the table
Example

Prepared by [Link],AP(SG)/CSE
CS1403/Database Design and Management Department of CSE & ADS 2022 - 2023

Initial Hash structure, bucket size = 2

Hash structure after insertion of one Brighton and two Downtown records

Hash structure after insertion of Mianus record

Hash structure after insertion of three Perryridge records

Hash structure after insertion of Redwood and Round Hill records

Use of Extendable Hash Structure

 To locate the bucket containing search-key Kj:
1. Compute h(Kj) = X
2. Use the first i high order bits of X as a displacement into bucket address table, and follow the pointer to

Prepared by [Link],AP(SG)/CSE
 Appropriate bucket
Updates in Extendable Hash Structure
 To insert a record with search-key value Kj
– follow same procedure as look-up and locate the bucket, say j.
– If there is room in the bucket j insert record in the bucket.
– Overflow buckets used instead in some cases.
 To delete a key value,
– locate it in its bucket and remove it.
– The bucket itself can be removed if it becomes empty
– Coalescing of buckets can be done
– Decreasingbucket address table size is also possible
 Benefits of extendable hashing:
– Hash performance does not degrade with growth of file
– Minimal space overhead
 Disadvantages of extendable hashing
– Extra level of indirection to find desired record
Bucket address table may itself become very big.

QUERY PROCESSING OVERVIEW

1. The scanning, parsing, and validating module produces an internal representation of the query.
2. The query optimizer module devises an execution plan which is the execution strategy to retrieve the result
of the query from the database files. A query typically has many possible execution strategies differing in
performance, and the process of choosing a reasonably efficient one is known as query optimization. Query
optimization is beyond this course. The code generator generates the code to execute the plan. The runtime
database processor runs the generated code to produce the query result.

Evaluation of SQL Statement

The query is evaluated in a different order.
 The tables in the from clause are combined using Cartesian products. The where predicate is then applied.
 The resulting tuples are grouped according to the group by clause. The having predicate is applied to each
group, possibly eliminating some groups. The aggregates are applied to each remaining group. The select
clause is performed last.
Translating SQL Queries into Relational Algebra
 SQL query is first translated into an equivalent extended relational algebra expression.
 SQL queries are decomposed into query blocks, which form the basic units that can be translated into the
algebraic operators and optimized.
 Query block contains a single SELECT-FROM-WHERE expression, as well as GROUP BY and HAVING
clauses.
 Nested queries within a query are identified as separate query blocks.
Example:

Prepared by [Link],AP(SG)/CSE
SELECT LNAME, FNAME
FROM EMPLOYEE
WHERE SALARY > (SELECT MAX(SALARY)
FROM EMPLOYEE
WHERE DNO=5);
 The inner block
• (SELECT MAX (SALARY) FROM EMPLOYEE WHERE DNO=5)
– Translated in:
• ℑ MAX SALARY( σDNO=5(EMPLOYEE))
 The Outer block
• SELECT LNAME, FNAME FROM EMPLOYEE WHERE SALARY > C
– Translated in:
• ∏ LNAZME, FNAME ( σSALARY>C(EMPLOYEE))
(C represents the result returned from the inner block.)
 The query optimizer would then choose an execution plan for each block.
 The inner block needs to be evaluated only once. (Uncorrelated nested query).
 It is much harder to optimize the more complex correlated nested queries.
External Sorting
It refers to sorting algorithms that are suitable for large files of records on disk that do not fit entirely in main
memory, such as most database files.
 ORDER BY.
 Sort-merge algorithms for JOIN and other operations (UNION, INTERSECTION). Duplicate elimination
algorithms for the PROJECT operation (DISTINCT). Typical external sorting algorithm uses a sort-merge
strategy: Sort phase: Create sort small sub-files (sorted sub-files are called runs).
 Merge phase: Then merges the sorted runs. N-way merge uses N memory buffers to buffer input runs, and 1
block to buffer output. Select the 1st record (in the sort order) among input buffers, write it to the output
buffer and delete it from the input buffer. If output buffer full, write it to disk. If input buffer empty, read
next block from the corresponding run.
E.g. 2-way Sort-Merge

HEURISTIC-BASED QUERY OPTIMIZATION

1. Break up SELECT operations with conjunctive conditions into a cascade of SELECT operations
2. Using the commutativity of SELECT with other operations, move each SELECT operation as far down the
query tree as is permitted by the attributes involved in the select condition

Prepared by [Link],AP(SG)/CSE
 3. Using commutativity and associativity of binary operations, rearrange the leaf nodes of the tree
4. Combine a CARTESIAN PRODUCT operation with a subsequent SELECT operation in the tree into a
JOIN operation, if the condition represents a join condition
5. Using the cascading of PROJECT and the commuting of PROJECT with other operations, break down and
move lists of projection attributes down the tree as far as possible by creating new PROJECT operations as
needed
6. Identify sub-trees that represent groups of operations that can be executed by a single algorithm
Example
 Query
"Find the last names of employees born after 1957 who work on a project named ‘Aquarius‘."
 SQL
SELECT LNAME
FROM EMPLOYEE, WORKS_ON, PROJECT
WHERE PNAME=’Aquarius‘ AND PNUMBER=PNO AND ESSN=SSN AND BDATE=’1957-12-31‘;

Cost Estimation in Query Optimization

The main aim of query optimization is to choose the most efficient way of implementing the relational algebra
operations at the lowest possible cost.
 The query optimizer should not depend solely on heuristic rules, but, it should also estimate the cost of
executing the different strategies and find out the strategy with the minimum cost estimate.
The cost functions used in query optimization are estimates and not exact cost functions.
 The cost of an operation is heavily dependent on its selectivity, that is, the proportion of select operation(s)
that forms the output.
 In general the different algorithms are suitable for low or high selectivity queries.
 In order for query optimizer to choose suitable algorithm for an operation an estimate of the cost of
executing that algorithm must be provided
The cost of an algorithm depends on cardinality of its input.
 To estimate the cost of different query execution strategies, the query tree is viewed as containing a series of
basic operations which are linked in order to perform the query.
 It is also important to know the expected cardinality of an operation‘s output because this forms the input to
the next operation.

Prepared by [Link],AP(SG)/CSE
Cost Components of Query Execution
The cost of executing the query includes the following components:
– Access cost to secondary storage.
– Storage cost.
– Computation cost.
– Memory uses cost.
– Communication cost.
Importance of Access cost
Out of the above five cost components, the most important is the secondary storage access cost.
 The emphasis of the cost minimization depends on the size and type of database applications.
 For example in smaller database the emphasis is on the minimizing computing cost as because most of the
data in the files involve in the query can be completely store in the main memory.
 For large database, the main emphasis is on minimizing the access cost to secondary device.
 For distributed database, the communication cost is minimized as because many sites are involved
 for the data transfer.
Cost functions for SELECT Operation
Linear Search:
– [nBlocks(R)/2], if the record is found.
– [nBlocks(R)], if no record satisfied the condition.
Binary Search :
o [log2(nBlocks(R))], if equality condition is on key attribute, because SCA(R) = 1 in this case.o[log2(nBlocks(R))] +
[SCA(R)/bFactor(R)] – 1, otherwise.
Equity condition on Primary key
– [nLevelA(I) + 1]
Equity condition on Non-Primary key
– [nLevelA(I) + 1] + [nBlocks(R)/2]
Cost functions for JOIN Operation
Join operation is the most time consuming operation to process.
 An estimate for the size (number of tuples) of the file that results after the JOIN operation is required to
develop reasonably accurate cost functions for JOIN operations.
 The JOIN operations define the relation containing tuples that satisfy a specific predicate F from the
Cartesian product of two relations R and S.

Prepared by [Link],AP(SG)/CSE
RAID
RAID (redundant array of independent disks) originally redundant array of inexpensive disks) is a way of storing the
same data in different places on multiple hard disks to protect data in the case of a drive failure.
RAID: Redundant Arrays of Independent Disks
Disk organization techniques that manage a large numbers of disks, providing a view of a single disk of high
capacity and high speed by using multiple disks in parallel, and high reliability by storing data redundantly, so that
data can be recovered even if a disk fails
Motivation for RAID
 Just as additional memory in form of cache, can improve the system performance, in the same way
additional disks can also improve system performance.
 In RAID we can use an array of disks which operates independently since there are many disks, multiple I/O
requests can be handled in parallel if the data required is on separate disks
 A single I/O operation can be handled in parallel if the data required is distributed across multiple disks.
Benefits of RAID
 Data loss can be very dangerous for an organization
 RAID technology prevents data loss due to disk failure
 RAID technology can be implemented in hardware or software
 Servers make use of RAID Technology
RAID Level 0- Stripping and non-redundant
 RAID level 0 divides data into block units and writes them across a number of disks. As data is placed
across multiple disks it is also called “data Striping”.
 The advantage of distributing data over disks is that if different I/O requests are pending for two different
blocks of data, then there is a possibility that the requested blocks are on different disks

There is no parity checking of data. So if data in one drive gets corrupted then all the data would be lost. Thus RAID
0 does not support data recovery Spanning is another term that is used with RAID level 0 because the logical disk
will span all the physical drives. RAID 0 implementation requires minimum 2 disks.
Advantages
 I/O performance is greatly improved by spreading the I/O load across many channels & drives.
 Best performance is achieved when data is striped across multiple controllers with only one driver per
controller

Disadvantages
 It is not fault-tolerant, failure of one drive will result in all data in an array being lost
RAID Level 1: Mirroring (or shadowing)
 Also known as disk mirroring, this configuration consists of at least two drives that duplicate the storage of

Prepared by [Link],AP(SG)/CSE
 data. There is no striping.
 Read performance is improved since either disk can be read at the same time. Write performance is the same
as for single disk storage.
 Every write is carried out on both disks. If one disk in a pair fails, data still available in the other.
 Data loss would occur only if a disk fails, and its mirror disk also fails before the system is repaired
Probability of combined event is very small.

RAID Level 2:
This configuration uses striping across disks, with some disks storing error checking and correcting (ECC)
information. It has no advantage over RAID 3 and is no longer used.

RAID Level 3: Bit-Interleaved Parity

 A single parity bit is enough for error correction, not just detection, since we know which disk has failed
– When writing data, corresponding parity bits must also be computed and written to a parity bit disk
– To recover data in a damaged disk, compute XOR of bits from other disks (including parity bit disk)
 I/O operation addresses all the drives at the same time, RAID 3 cannot overlap I/O. For this reason, RAID 3
is best for single-user systems with long record applications.

Prepared by [Link],AP(SG)/CSE
RAID Level 4: Block-Interleaved Parity
 When writing data block, corresponding block of parity bits must also be computed and written to
paritydisk
 To find value of a damaged block, compute XOR of bits from corresponding blocks (including parity
block)from other disks.

RAID Level 5:
 RAID 5 uses striping as well as parity for redundancy. It is well suited for heavy read and low
writeoperations.
 Block-Interleaved Distributed Parity; partitions data and parity among all N + 1 disks, rather than
storingdata in N disks and parity in 1 disk.

RAID Level 6:
 This technique is similar to RAID 5, but includes a second parity scheme that is distributed across the
drives in the array. The use of additional parity allows the array to continue to function even if two disks
fail simultaneously. However, this extra protection comes at a cost.
 P+Q Redundancy scheme; similar to Level 5, but stores extra redundant information to guard against
multiple disk failures.
Better reliability than Level 5 at a higher cost; not used as widely.

Prepared by [Link],AP(SG)/CSE
 DATA DICTIONARY STORAGE
In a database management system (DBMS), a data dictionary can be defined as a component that stores
a collection of names, definitions, and attributes for data elements used in the database. The database
stores metadata, that is, information about the database. These data elements are then used as part of a
database, research project, or information system.
It stores all information about relationships or tables, from the schema and constraints used. All
metadata is preserved. In general, metadata refers to information about data. Thus, storing the
connection scheme and other metadata in a single structure called a data dictionary or system directory.
A data dictionary is like an A-Z dictionary of a relational database system that stores all the information
about every relationship in the database.
What is a Data Dictionary?
The data dictionary consists of two words, data, which represents data collected from several sources,
and dictionary, which represents where this data is available. The data dictionary is an important part of
the relational database because it provides additional information about the relationship between several
tables in the database. A data dictionary in a DBMS helps users manage data in an orderly and orderly
manner, thereby preventing data redundancy.
Below is a data dictionary that describes the table that contains employee details.

Field Size for

Field Name Data Type Description Example
Display

Unique ID of each
EmployeeID Integer 8 100025
employee

Full name of the Emily

FullName Text 30
employee Johnson

Date of birth of
DOB Date/Time 10 1990-05-15
employee

Phone number of 555-123-

PhoneNumber Integer 10
employee 4567
Some of the advantages of using a data dictionary are:
 In DBMS, the data model provides very little information about the database, so the data dictionary
is very important to get the right knowledge about the entities, relationships, and attributes that exist
in the data model.
 The data dictionary provides consistency by reducing data redundancy in data collection and use
among different team members.
 Data dictionaries provide structured analysis and design tools by implementing data standards. Data
standards are sets of rules that govern the collection, recording, and presentation of data.
 Using a data dictionary helps define the naming convention used in the model.

Prepared by [Link],AP(SG)/CSE
Types of Data Dictionary in DBMS

There are basically two types of data dictionaries in a database management system:
 Integrated Data Dictionary
 Stand Alone Data Dictionary

Integrated Data Dictionary

Every relational database has an Integrated Data Dictionary available in the DBMS. This integrated
data dictionary acts as a system directory that is accessed and updated by the relational database. The
old database does not have an integrated data dictionary, so the database administrator must use the
Stand Alone Data Dictionary. An Integrated Data Dictionary in a DBMS can link metadata.

The integrated data dictionary can be further divided into two types:
Active: When any changes are made to the database, the active data dictionary is automatically updated
by the DBMS. It is also known as a self-updating dictionary because it continuously updates its data.
Passive: Unlike active dictionaries, passive dictionaries must be updated manually when there are
changes in the database. This type of data dictionary is difficult to manage because it requires proper
functionality. Else, the database and data dictionary will be synchronized.

Stand Alone Data Dictionary

This type of database in the DBMS is very adaptive because it grants the administrator in charge of the
confidential information complete autonomy to define and manage all crucial data. Whether the
information is printed or not has nothing to do with it. A data dictionary that has a stand-alone format
enables database designers to have the flexibility to communicate with end users regardless of their data
dictionaries format.

There is no standard format for data dictionaries. Here are some common elements:
 Data Elements: The data dictionary describes each data element by specifying the names, data
types, storage formats and validation rules.
 Table: All information about the table, such as the user who created the table, the number of rows
and columns, the date the table was created and entered, etc.

Prepared by [Link],AP(SG)/CSE
 Indexes: Indexes for database tables are stored in the data dictionary. The DBMS stores the index
name used and index attributes, locations, and properties, as well as the creation date, in each index.
 Programs: Applications defined for database access, reports, application formats and screens, SQL
queries, etc. also stored in the data dictionary.
 Relationships between data elements: A data dictionary stores relationship types; for example, if it
is mandatory or optional, the nature of the relationship and connection, etc.
 Administration and End Users: The data dictionary stores all administrative and end user data.
Metadata in a DBMS, stored in a data dictionary, is like a monitor that controls database usage and
whether users are allowed to access the database.

How to Create a Data Dictionary?

As mentioned above, most businesses rely on a database management system that has an integrated data
dictionary because it is automatically updated and easy to maintain. Documentation for databases
including MySQL, SQL Server, Oracle, etc. This can be done in various relational databases such as
Database administrators can use templates in SQL Server, Oracle, or Microsoft Excel to create a stand-
alone data dictionary.
The various notations used to create a data dictionary are:

Data Construct Notation Stands For

Composition = is composed of

Sequence + AND

Selection [|] OR

Repetition { }^n n repetitions

Parentheses () to represent optional data

Comment *…* to define a comment

COLUMN ORIENTED STORAGE

What is a Columnar Database?

Columnar databases are those where the data is stored in columns instead of rows as is done in the traditional row-
based databases as they offer impressive benefits in certain types of queries and data manipulation operations.
Therefore, databases that are organized in columns provide better performances for operations that require
applications to read data such as data analytics and data warehousing. This approach enhances the rate of query
processing and reduces disk I/O making it suitable for cases that involve a large number of queries that are
processed on large amounts of data.

Prepared by [Link],AP(SG)/CSE
Columnar Database VS Row Database
Both Columnar and Row databases are a few methods used for processing big data analytics and data warehousing.
But their approach is different from each other.
For example:
 Row Database: “Customer 1: Name, Address, Location.”(The fields for each new record are stored in a long
row).
 Columnar Database: “Customer 1: Name, Address, Location.”(Each field has its own set of columns).

Example of Columnar Database

Here is an example of a simple database table with four columns and three rows.
ID Number Last Name First Name Bonus

534782 Miller Ginny 6000

585523 Parker Peter 8000

479148 Stacy Gwen 2000

In a Columnar DBMS, the data stored is in this format:

534782, 585523, 479148; Miller, Parker, Stacy; Ginny, Peter, Gwen; 6000, 8000, 2000.

In a Row-oriented DBMS, the data stored is in this format:

534782, Miller, Ginny, 6000; 585523, Parker, Peter, 8000; 479148, Stacy, Gwen, 2000.

When to use the Columnar Database

1. Queries that involve only a few columns.
2. Compression but column-wise only.
3. Clustering queries against a huge amount of data.

Advantages of Columnar Database

1. Columnar databases can be used for different tasks such as when the applications that are related to big data
comes into play then the column-oriented databases have greater attention in such case.
2. The data in the columnar database has a highly compressible nature and has different operations like (AVG),
(MIN, MAX), which are permitted by the compression.
3. Efficiency and Speed: The speed of Analytical queries that are performed is faster in columnar databases.
4. Self-indexing: Another benefit of a column-based DBMS is self-indexing, which uses less disk space than a
relational database management system containing the same data.

Limitation of Columnar Database

1. For loading incremental data, traditional databases are more relevant as compared to column-oriented databases.
2. For Online Transaction Processing (OLTP) applications, Row oriented databases are more appropriate than
columnar databases.

Prepared by [Link],AP(SG)/CSE