Question 4

 • Sequential Files:-
1. A sequential file is designed for efficient processing of records in sorted order on
some search key. Records are chained together by pointers to permit fast retrieval
in search key order. Pointer points to next record in order. Records are stored
physically in search key order (or as close to this as possible). This minimizes
number of block accesses.

2. It is difficult to maintain physical sequential order as records are inserted and
deleted. Deletion can be managed with the pointer chains. Insertion poses problems
if no space where new record should go. If space, use it, else put new record in an
overflow block. Adjust pointers accordingly. Problem: we now have some records
out of physical sequential order. If very few records in overflow blocks, this will
work well. If order is lost, reorganize the file. Reorganizations are expensive and
done when system load is low.

3. If insertions rarely occur, we could keep the file in physically sorted order and
reorganize when insertion occurs. In this case, the pointer fields are no longer
required.

• Indexed Sequential Files:
Each record of a file has a key field which uniquely identifies that record.
An index consists of keys and addresses (physical disc locations).
An indexed sequential file is a sequential file (i.e. sorted into order of a key field) which
has an index.
A full index to a file is one in which there is an entry for every record.
Indexed sequential files are important for applications where data needs to be
accessed.....

• sequentially
• randomly using the index.

An indexed sequential file allows fast access to a specific record.
Example: A company may store details about its employees as an indexed sequential
file. Sometimes the file is accessed....

• sequentially. For example when the whole of the file is processed to produce
payslips at the end of the month.

• randomly. Maybe an employee changes address, or a female employee gets
married and changes her surname.
An indexed sequential file can only be stored on a random access device
eg magnetic disc, CD.
                
            

 A tree is a non-empty set, one element of which is designated the root of the tree while
the remaining elements are partitioned into non-empty sets each of which is a subtree of
the root.
Binary Tree: Each node has zero, one, or two children. This assertion makes many tree
operations simple and efficient.
Traversal techniques of the binary tree
Many problems require we visit* the nodes of a tree in a systematic way: tasks such as
counting how many nodes exist or finding the maximum element. Three different
methods are possible for binary trees: preorder, postorder, and in-order, which all do
the same three things: recursively traverse both the left and rights subtrees and visit the
current node. 
The difference is when the algorithm visits the current node:

preorder: Current node, left subtree, right subtree(DLR)
postorder: Left subtree, right subtree, current node(LRD)
in-order: Left subtree, current node, right subtree.(LDR)

• Visit means performing some operation involving the current node of a tree, like
incrementing a counter or checking if the value of the current node is greater than
any other recorded.
Sample implementations for Tree Traversal

preorder(node)
visit(node)
if node.left ≠ null then preorder(node.left)
if node.right ≠ null then preorder(node.right)
inorder(node)
if node.left ≠ null then inorder(node.left)
visit(node)
if node.right ≠ null then inorder(node.right)
postorder(node)
if node.left ≠ null then postorder(node.left)
if node.right ≠ null then postorder(node.right)
visit(node)
levelorder(root)
queue<node> q
q.push(root)
while not q.empty do
node = q.pop
visit(node)
if node.left ≠ null then q.push(node.left)
if node.right ≠ null then q.push(node.right)
Examples of Tree Traversals



preorder: 50, 30, 20, 40, 90, 100
inorder: 20, 30, 40, 50, 90, 100
postorder: 20, 40, 30, 100, 90, 50
            

File: A collection of data or information that has a name, called the filename. Almost all
information stored in a computer must be in a file. There are many different types of
files: data files, text files , program files, directory files, and so on. Different types of
files store different types of information. For example, program files store programs,
whereas text files store text.

Field: A space allocated for a particular item of information. A tax form, for example,
contains a number of fields: one for your name, one for your Social Security number,
one for your income, and so on. In database systems, fields are the smallest units of
information you can access. In spreadsheets, fields are called cells.
Most fields have certain attributes associated with them. For example, some fields are
numeric whereas others are textual, some are long, while others are short. In addition,
every field has a name, called the field name.

Record: In database management systems, a field can be required, optional, or
calculated. A required field is one in which you must enter data, while an optional field
is one you may leave blank. A calculated field is one whose value is derived from some
formula involving other fields. You do not enter data into a calculated field; the system
automatically determines the correct value.
A collection of fields is called a record.

Database: The definition of a database is a structured collection of records or data that is
stored in a computer system. In order for a database to be truly functional, it must not
only store large amounts of records well, but be accessed easily. In addition, new
information and changes should also be fairly easy to input. In order to have a highly
efficient database system, you need to incorporate a program that manages the queries
and information stored on the system. This is usually referred to as DBMS or a
Database Management System. Besides these features, all databases that are created
should be built with high data integrity and the ability to recover data if hardware fails.
            

Traversal is the facility to move through a structure visiting each of the vertices once.
We looked previously at the ways in which a binary tree can be traversed. Two possible
traversal methods for a graph are breadth-first and depth-first.

• Depth-First Traversal:
A depth-first traversal works in a similar way, except that the neighbors of each visited
vertex are added to a stack data structure. Vertices are visited in the order in which they
are popped from the stack, i.e. last-in, first-out.

• Algorithm of Depth-First Traversal:
1. Create an empty stack
2. Unmark all nodes
3. Mark the start node and place it on the stack
3. Loop while the stack is not empty
3.1 Remove a node, n, from the stack
3.2 Process node n
3.2 Loop for each of the nodes adjacent to n
3.2.1 If the node is unmarked then
3.2.1.1 Mark it and place it on the stack
4. Finish

• Breadth-First Traversal:
This method visits all the vertices, beginning with a specified start vertex. It can be
described roughly as “neighbors-first”. No vertex is visited more than once, and vertices
are only visited if they can be reached – that is, if there is a path from the start vertex.
Breadth-first traversal makes use of a queue data structure. The queue holds a list of
vertices which have not been visited yet but which should be visited soon. Since a
queue is a first-in first-out structure, vertices are visited in the order in which they are
added to the queue.
Visiting a vertex involves, for example, outputting the data stored in that vertex, and
also adding its neighbors to the queue. Neighbors are not added to the queue if they are
already in the queue, or have already been visited.

• Algorithm of Breadth-First Traversal:
1. Create an empty queue
2. Unmark all nodes
3. Mark the start node and place it on the queue
3. Loop while the queue is not empty
3.1 Remove a node, n, from the queue
3.2 Process node n
3.2 Loop for each of the nodes adjacent to n
3.2.1 If the node is unmarked then
3.2.1.1 Mark it and place it on the queue
4. Finish