Tuesday 29 May 2012

DNS - Configuring Forward and Reverse Lookup Zones

Things you should know 

Domain Name System (DNS) refers to the domain name resolution mechanism, which allows using domain names, instead of IP addresses to access a domain. E.g. you can use http://facebook.com/ instead of http://66.220.149.11/ to access the facebook website.

The process of converting a DNS name to an IP address is known as DNS name resolution process.

A forward lookup zone is a DNS zone in which hostname to IP address relations are stored. When a computer requests the IP address of a specific hostname, the forward lookup zone is queried and the result is returned.
A reverse lookup zone does just the opposite. When a computer requests the hostname of an IP address, the reverse lookup zone is queried and the result is returned.

Practical Implementation

Open DNS Window and uncheck IPv6

Start - Administrative Tools- DNS
Right Click on Server
Select Properties
Select only the following IP Address
Uncheck IPv6 entry
OK

DNS - Uncheck IPv6
Configuring forward lookup zone

Expand Server Node
Right Click on Forward Lookup Zones
New Zone

DNS - Opening New Zone Wizard
New Zone wizard will appear. Give Next. Now you have to select the zone type.  

What is a zone? What are its types?

A zone is an entity that stores the records (information) about the objects that it manages. A record consists of a domain and its corresponding IP address. There are three types of zones. 
  • Primary Zone:  You can add and alter resource records in a primary zone.
  • Secondary Zone: It contains read-only records obtained from a primary DNS zone.
  • Stub Zone:  Stub zone in Microsoft server 2008 is a specialized version of a secondary zone. A stub zone contains only those resource records that are necessary to identify the authoritative DNS server for that zone. 
As we are creating a new zone for the first time, hence select primary zone.

DNS - Zone Type
Keep the option Store the Zone in Active Directory checked and give next.

Next is Zone replication scope.

Zone Replication Scope
Description
All DNS servers in the Active Directory forest

Replicates zone data to all DNS servers running on domain controllers in the Active Directory forest. Usually, this is the broadest scope of replication.
All DNS servers in the Active Directory domain
Replicates zone data to all DNS servers running on domain controllers in the Active Directory domain. This option is the default setting for Active Directory-integrated DNS zone replication in the Windows Server 2003 family.

All domain controllers in the Active Directory domain
Replicates zone data to all domain controllers in the Active Directory domain. If you want Windows 2000 DNS servers to load an Active Directory zone, this setting must be selected for that zone.


We will keep the default and give next. 

Provide the zone name. e.g. ciots.com
Select - Allow both nonsecure and secure dynamic updates and give next and finish.
An entry will be created for ciots.com in the forward lookup zones.

Select ciots.com, right click on it and select New Host. A host is used to resolve an IP address to a device in a domain. The device can be a computer, printer etc. 

DNS - Adding a new Host
The New Host window will appear.

Now consider for the domain ciots.com we have the FTP server at location 192.168.1.12 for which we have to create the DNS forward lookup entry. 

Enter name ftp and provide the IP address as 192.168.1.12

DNS - Configuring new host
Finally click on Add Host. With this we have completed forward lookup entry.

Video Tutorial Creating a DNS Forward Lookup Zone





Configuring reverse lookup zone


Right click on Reverse Lookup Zones and Select New Zone. The settings will be nearly same as the configuration settings of forward lookup zone.


Select IPv4 Reverse Lookup Zone – Next
Enter Network ID as 192.168.1 – Next
Allow both nonsecure and secure dynamic updates – Next – Finish

Right Click on the node created and select New Pointer (PTR)

DNS - Adding new PTR
Enter host IP address: 192.168.1.12
Host name: browse and select ftp.ciots.com
OK

Now we will use the nslookup command to verify these entries.

Verify Forward Lookup entry
In the command prompt, enter nslookup ftp.ciots.com , this will give the associated IP address.

Verify Reverse Lookup entry
In the command prompt, enter nslookup 192.168.1.12 , this will give the associated host name.

DNS - nslookup command

Video Tutorial Creating a New Reverse Lookup Zone




Sunday 27 May 2012

Creating a user in Active Directory

There are four ways for creating users. Let's see each of them one by one.

Using the GUI


Steps

Start
Administrative Tools
Active Directory Users and Computers
mcitp.com (expand the domain node by clicking on plus)
Right Click on Users
New User
Configure the details and create the new user.

Creating a user in Active Directory (GUI)
Using Command

To create a user Amarjeet with login name amar in the domain mcitp.com and the user must change password after first login.

Open command prompt and execute the following command.

dsadd user "CN=Amarjeet, CN=Users, dc=mcitp, dc=com" -samid amar 
-pwd * -mustchpwd yes


Creating a user in Active Directory (Command)
Now the user can login with the name amar and has to change password at the time of first login.

How to Add a Client Machine in a Domain

Steps

Right Click on My Computers
Properties
Go to Computer Name Tab Click on Change button
Select Domain
Give domain name e.g. mcitp.com
Provide Server Administrator’s credentials 
It will verify and the system will restart.



Now log in on the domain with the Active Directory user credentials.

Installing Active Directory in Windows Server 2008

Before Installing Active Directory we have to configure the machines. Click here to know more

Note : To install Active Directory we need at least 2 machines in workgroup. One will be the server machine and the other will be a client.

What is Active Directory Domain Services (AD DS) ?


Active Directory (AD) is a structure used on computers and servers running the Microsoft Windows operating system (OS). AD is used to store network, domain, and user information and was originally created by Microsoft in 1996. It was first deployed on Microsoft Windows 2000.

Active Directory Domain Services (AD DS) stores directory data (about users, computers, organizational units and other network resources)  and manages communication between users and domains, including user logon processes, authentication, and directory searches. An Active Directory domain controller is a server that is running AD DS.

AD DS provides a distributed directory service that you can use for centralized, secure management of your network.

Installing Active Directory on Windows Server 2008

Start - run - dcpromo - OK

The installation wizard will appear for Active Directory. Read the instructions and give Next twice. 

As we are creating domain for the first time, hence select Create a new domain in a new forest

Installing AD - Creating new domain
Give FQDN i.e. Fully Qualified Domain Name. e.g. mcitp.com

Installing AD - Giving FQDN
Specify Forest Functional Level

If the organization where we are doing this setup is already having some other machines running any version of Windows Server and you want to establish trust relationship with those machines, then select the lowest version from the list.

As this is our first machine and no other servers exist, hence select Windows Server 2008.

Installing AD - Specifying Forest Functional Level
Now when you give next, a warning will appear regarding IP, give yes and continue.

As DNS is not installed yet on the system, a message will appear in this regard. Give yes and continue.

Next it will ask for the path where the database of the Active Directory will be stored on the disk. Keep  the default values and give next.

Give directory service administrator password - e.g. admin@123 and give next.

The installation will start. 

Check Reboot on Completion so that system will restart after completing the AD installation.

Now

Create a user. Click here to know more

Bring the Client Machine in Domain. Click here to know more

and Finally login from client on the domain with the new user name and password.


Installing AD - Login Screen

Preparing Machines Before Installing Active Directory

There are few settings need to be done before we start with Active Directory (AD) installation.

What we have already done


We have created two machines and already installed operating system.
  • Server Machine : Windows Server 2008
  • Client Machine  : Windows XP
Now we will take these settings further. 

As we are working with Oracle VM Virtual Box Manager, for each machine created,
  1. Select the Machine
  2. Go to Settings
  3. Go to Network Tab
  4. Select Attached to - Bridge Adapter
Configuring Bridge Adapter Settings (Click on the image to enlarge)
Configuring Server IP Address

Go to Network and Sharing Center
Manage Network Connections
Right Click on Local Area Connection
Properties
Select Internet Protocol Version 4 (TCP/IPv4)
Click on Properties
Set the following IP Address


Configure Client IP Address

Use the following IP settings for client machine.


Change the Computer names (Both Systems)

Right Click on My Computer
Properties
Change Settings
Change (Button)
Give Computer Name 
OK
and restart the computer.

Turn Off Firewall (Both Systems)

Start
Control Panel
Windows Firewall
Turn Windows Firewall On or Off
Turn Off Windows Firewall
OK

Firewall Settings
Turn on Network Discovery on Server (Optional)

Right Click on My Network Places icon in the Tray
Go to Network and Sharing Center
Click on the Arrow button
Select Turn on network discovery
Apply

Turn on Network Discovery

Ping Systems and assure that they are connected

Start - run - ping 192.168.1.10 –t


Now we can start with active directory installation. Click Here to know more

Saturday 26 May 2012

Building a Binary Tree using Inorder and Postorder Traversals in Java

class TNode
{
 int data;
 TNode left;
 TNode right;

 TNode(int d)
 {
  data = d;
  left= null;
  right=null;
 }
}

class TreeBuilder
{
 static int postIndex;
 static int[] in, post;
 TNode Start;

 static void setValue(int[] i, int[] p)
 {
  in = i;
  post = p;
  postIndex=in.length-1; //Change 1
 }

 static int findInIndex(int inStart, int inEnd, int value)
 {
  for(int i=inStart; i<=inEnd; i++)
   if(in[i]==value)
   return i;

  return -1;
 }

 //Main method with the logic for building tree using Pre and Inorder traversals
 static TNode buildTree(int inStart, int inEnd)
 {
  if(inStart>inEnd)
   return null;

  TNode node = new TNode(post[postIndex--]); //Change 2

  if(inStart==inEnd)
   return node;

  int inIndex = findInIndex(inStart, inEnd, node.data);
  
  //Change 3

  node.right=buildTree(inIndex+1, inEnd);
  node.left=buildTree(inStart, inIndex-1);

  return node;
 }
}

class TreeBuilderDemo 
{
 public static void main(String[] args) 
 {
  int[] in = {8, 4, 10, 9, 11, 2, 5, 1, 6, 3, 7};
  int[] post = {8, 10, 11, 9, 4, 5, 2, 6, 7, 3, 1};

  TreeBuilder.setValue(in, post);

  TNode start = TreeBuilder.buildTree(0,in.length-1);

  System.out.print("\nPreorder\t: ");
  printPreorder(start);

  System.out.print("\n\nInorder\t\t: ");
  printInorder(start);

  System.out.print("\n\nPostorder\t: ");
  printPostorder(start);

  System.out.println("");
 }

 static void printInorder(TNode node)
 {
  if (node == null)
   return; 

  printInorder(node.left);   
  System.out.print(node.data + "\t "); 
  printInorder(node.right);   
 }

 static void printPreorder(TNode node)
 {
  if (node == null)
   return; 

  System.out.print(node.data + "\t ");
  printPreorder(node.left);   
  printPreorder(node.right);   
 }

 static void printPostorder(TNode node)
 {
  if (node == null)
   return; 

  printPostorder(node.left);   
  printPostorder(node.right);   
  System.out.print(node.data + "\t ");
 }
}

Click here to learn Building a Binary Tree using Inorder and Preorder Traversals in Java.

Wednesday 23 May 2012

Cards Arrangement Program in Java

Aim

Write a program to print the source sequence of cards, for one card below the deck & every alternate card opened & discarded ?

Code
import java.io.*;

class OutSequenceException extends Exception
{
 public String toString()
 {
  return "OutSequenceException: Invalid Number Entered !\nProgram Terminating....";
 }
}

class Card
{
 public static void main(String[] args)
 {
  try
  {

   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   
   //Array to store inputs and sorted sequence
   int[] a = new int[60];
   int[] b = new int[60];

   boolean flag=false;
 
   int count=0, index=0, skips, n;

   System.out.print("Enter Limit (13,26,39,52) :");
   n = Integer.parseInt(br.readLine());

   if(n!=13 && n!=26 && n!=39 && n!=52)
    throw new OutSequenceException();
    

   System.out.println("Provide Inputs");
   
   for(int i=0; i<n; i++)
   {
    a[i]=Integer.parseInt(br.readLine());

    if(a[i]>n)
     throw new OutSequenceException();

   }

   System.out.print("Enter number of skips: ");
   skips = Integer.parseInt(br.readLine());
   

   for(int i=0; i<n; i++)
   {
    //if flag is true means skips are done and b[i]=0 so no element placed there
    if(flag  && b[i]==0)
    {
     b[i]=a[count];
     count++;//next card to be placed
     flag=false;
    }


    /* 
       if previous if not executed because flag=false but some element 
       is there then also this will not execute hence skip will not 
       be incremented rather i will increase and next position 
       will be checked 
    */

    if(b[i]==0) //means previous if is not executed and no element is placed there
    {
     index++; 
     if(index==skips)
     {
      flag=true;
      index=0;
     }
     else
      flag=false;
    }

    //Reset the loop
    if(i==(n-1))
     i=-1;

    //Exit
    if(count==n)
     break;    
    
   }   
 
   //Finally print the result
   for(int i=0; i<n; i++)
    System.out.println(b[i]);

  }
  catch(Exception e)
  {
   System.out.println(e);
  }  
 }
}

2's Complement using C Programming

Definition

Property
Two's complement representation allows the use of binary arithmetic operations on signed integers, yielding the correct 2's complement results.

Positive Numbers
Positive 2's complement numbers are represented as the simple binary.

Negative Numbers
Negative 2's complement numbers are represented as the binary number that when added to a positive number of the same magnitude equals zero.
Integer2's Complement
SignedUnsigned
550000 0101
440000 0100
330000 0011
220000 0010
110000 0001
000000 0000
-12551111 1111
-22541111 1110
-32531111 1101
-42521111 1100
-52511111 1011
Note:  The most significant (leftmost) bit indicates the sign of the integer; therefore it is sometimes called the sign bit.
If the sign bit is zero,
then the number is greater than or equal to zero, or positive.
If the sign bit is one,
then the number is less than zero, or negative.

Calculation of 2's Complement

To calculate the 2's complement of an integer, invert the binary equivalent of the number by changing all of the ones to zeroes and all of the zeroes to ones (also called 1's complement), and then add one.
For example,
0001 0001(binary 17)   such that   1110 1111(two's complement -17)
NOT(0001 0001) = 1110 1110  (Invert bits)
1110 1110 + 0000 0001 = 1110 1111  (Add 1)


2's Complement Addition

Two's complement addition follows the same rules as binary addition.
For example,
5 + (-3)  =  2     0000 0101 = +5
+ 1111 1101

 = -3
  0000 0010 = +2
Finally a C program to perform addition using 2's Complement.

#include<stdio.h>
#include<conio.h>
#include<math.h>
void showbits(int,int);

void main()
{
 int a,b,c,bit,d,e,f,g,i;
 char ch;
 do
 {
  clrscr();

  //accepting inputs
  printf("\nEnter the number of bits: ");
  scanf("%d",&bit);
  printf("Enter two numbers to be added:- \n");
  scanf("%d",&a);
  scanf("%d",&b);
  c=a+b;

  //Ones Complement
  d=~(a);
  e=~(b);

  if(a<0)
   f=a;
  else
   f=d+1;

  if(b<0)
   g=b;
  else
   g=e+1;

  //addition
  printf("\nAddition: \n");
  printf("\t ");
  showbits(f,bit);
  printf("\n");
  printf("\t+");
  showbits(g,bit);
  printf("\n\t");

  for(i=0;i<=bit;i++)
   printf("-");

  printf("\t ");
  showbits(c,bit);
  printf("\n");
  printf("\t= %d",c);

  if(c>=(-1*(pow(2,bit-1)))&&(c<=(pow(2,bit-1)-1)))
   printf("\n\nResult Status: No Overflow \n");
  else
   printf("\n\nResult Status: Overflow \n");

  printf("\n\n\nDo you wish to continue? (y/n)");

  ch=getch();
 }while(ch=='y');
}

void showbits(int n,int bit)
{
 int i,k,andmask;

 for(i=(bit-1);i>=0;i--)
 {
  andmask=1<<i;
  k=n & andmask;

  k==0?printf("0"):printf("1");
 }
}

Binary Search Tree in C Data Structure

In computer science, a binary search tree (BST) is a node based binary tree data structure which has the following properties:
  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.
From the above properties it naturally follows that: Each node (item in the tree) has a distinct key.

Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their their associated records.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.
Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays.
A binary search tree of size 9 and depth 3, with root 8 and leaves 1, 4, 7 and 13 

#include<stdio.h>
#include<conio.h>
#define null 0

struct t
{
 int data;
 struct t *left;
 struct t *right;
};

typedef struct t tree;
tree *ptr, *root, *q;

void inorder(tree *ptr); //left - root - right
void preorder(tree *ptr); //root - left - right
void postorder(tree *ptr); //left - right - root

void main()
{
 int val;
 char c='n';
 root = (tree *)malloc(sizeof(tree));

 clrscr();

 printf("Enter data: ");
 scanf("%d",&root->data);
 root->left=null;
 root->right=null;
 ptr=root; //set the current pointer to root

 fflush(stdin);
 printf("\nDo you want to add more nodes? (y/n)");
 c=getche();

 while(c!='n')
 {
  printf("\nEnter data: ");
  scanf("%d",&val);
  ptr=root;   //Every time start from root and traverse
  while(1)
  {
   if(val<ptr->data)
   {
    if(ptr->left==null)
    {
     q=(tree *) malloc(sizeof(tree));
     ptr->left=q;
     ptr=ptr->left;
     ptr->data=val;
     ptr->left=null;
     ptr->right=null;
     break;
    }
    else
     ptr=ptr->left;
   }
   else
   {
    if(ptr->right==null)
    {
     q=(tree *) malloc(sizeof(tree));
     ptr->right=q;
     ptr=ptr->right;
     ptr->data=val;
     ptr->left=null;
     ptr->right=null;
     break;
    }
    else
     ptr=ptr->right;
   }
  }

  printf("\nDo you want to add more nodes? (y/n)");
  c=getche();
 }

 printf("\n\n\n\n\nInorder:\n");
 inorder(root);

 printf("\n\nPreorder:\n");
 preorder(root);

 printf("\n\nPostorder:\n");
 postorder(root);

 getch();
}

void inorder(tree *ptr)
{
 //left - root - right
 if(ptr!=null)
 {
  inorder(ptr->left);
  printf("%d\t",ptr->data);
  inorder(ptr->right);
 }
}

void preorder(tree *ptr)
{
 //root - left - right
 if(ptr!=null)
 {
  printf("%d\t",ptr->data);
  inorder(ptr->left);
  inorder(ptr->right);
 }
}

void postorder(tree *ptr)
{
 //left - right - root
 if(ptr!=null)
 {
  inorder(ptr->left);
  inorder(ptr->right);
  printf("%d\t",ptr->data);
 }
}

Linked List in C Programming

#include<stdio.h>
#include<conio.h>
#define null 0

//structure of a node
struct n
{
 int data;        //data to store
 struct n *next;  //pointer to next node
};

typedef struct n node;
node *first, *p, *last;

void create(node*, int);
void display(node*, int);
void sort(node*);
int search(node*, int, int);
void Delete(node *,int);

void main()
{
 int count,d;

 clrscr();

 printf("Enter number of nodes: ");
 scanf("%d",&count);

 //creating nodes
 if(count>0)
 {
  first = (node *)malloc(sizeof(node));
  printf("Enter Data : ");
  scanf("%d",&first->data);
  first->next=null;

  count--;

  create(first,count);
 }

 printf("Displaying node contents -- \n\n\n");
 display(first,1);

 //sort operation on linked list
 sort(first);
 printf("\n\n\nAfter Sorting: \n\n");
 display(first,1);

 //search position of specified data
 printf("\n\n\nEnter data to search : ");
 scanf("%d",&d);

 count = search(first,d,1);

 if(count!=-1)
 {
     printf("Data found at %d.",count);
 }
 else
  printf("Data not found");

 //Add more nodes
 printf("\n\n\nEnter more number of nodes to add: ");
 scanf("%d",&count);

 create(last,count);
 sort(first);

 printf("\n\n\nFinal node values:");
 display(first,1);

 //Deleting a node
 printf("\n\nEnter data to delete: ");
 scanf("%d",&d);

 Delete(first,d);

 printf("\n\nAfter deletion nodes:\n ");
 display(first,1);

 getch();
}

void create(node *p,int count)
{
 if(count>0)
 {
  p->next =  (node *)malloc(sizeof(node));
  last=p=p->next;

  printf("Enter Data: ");
  scanf("%d",&p->data);
  p->next = null;

  count--;
  create(p,count);
 }
 else
  return;
}

void display(node *p, int count)
{
     if(p!=null)
     {
 printf("\nNode %d: %d",count,p->data);
 count++;
 display(p->next,count);
     }
     else
 return;
}

int search(node *p,int data, int count)
{
 if(p!=null)
 {
  if(data==p->data)
   return count;
  else
  {
   count++;
   search(p->next,data,count);
  }
 }
 else
  return -1;  //no matching node found
}

void Delete(node *p,int data)
{
 int count = search(first,data,1);

 if(count<0)
  printf("Data not found.");
 else
 {       p=first;
  count--;

  if(count==0)
   first=first->next;
  else
  {
   while(count>1)
   {
      p=p->next;
      count--;
   }

   p->next=p->next->next;
  }
 }
}

void sort(node *p)
{
 while(p!=null)
 {
  node *q = p->next;

  while(q!=null)
  {
   if(q->data<p->data)
   {
    int temp;
    temp=p->data;
    p->data=q->data;
    q->data=temp;
   }

   q=q->next;
  }
  p=p->next;
 }
}

Monday 21 May 2012

Data Flow Diagrams (DFD) and Difference between Logical and Physical DFD

  • A data flow diagram represents a software system as a labeled, directed graph.
  • Data flow diagram illustrates the flow of data among a set of components.
  • The components may be tasks, software components, or even abstractions of the functionality that will be included in the software system.
The data flow diagram (DFD) serves two purposes:
  1. Provides an indication of how data are transformed as they move through the system.
  2. Depicts the functions (and sub functions) that transform the data flow.
Symbols Used In DFD



Types of data flow diagrams (DFDs)

Data flow diagrams (DFDs) are categorized as either logical or physical. A logical DFD focuses on the business and how the business operates. It describes the business events that take place and the data required and produced by each event. On the other hand, a physical DFD shows how the system will be implemented.


Design Feature
Logical
Physical
What the model depicts
How the business operates
How hue system will be implemented (or how the current system operates)
What the process represent
Business activities
Programs, program modules and manual procedures
What the data stores represent
Collection of data, regardless of how the data is stored
Physical files and databases, manual files
Type of data source
Show data stores representing permanent data collections
Master files, transaction files. Any processes that operate at two different times must be connected by a data source
System controls
Show business controls
Show controls for validating input data, for obtaining a record (record found status), for ensuring successful completion of a process and for system security (example: Journal records)


A context diagram depicts the entire process being modeled as a single task, or box, in a process diagram. The diagram shows important interactions between the system and external agents.

A subsystem DFD contains one process per major subsystem. The DFD shows important interfaces with external agents. Each process is further represented by another DFD—an event-partitioned DFD (or diagram zero) for that subsystem.

An event-partitioned system model contains one process per event. The model shows important interfaces with external agents. If no subsystem DFD is created, the event-partitioned system model is also called diagram 0.

A DFD fragment is a portion of an event-partitioned system model that shows the process, external agents, data stores, and data flows needed to respond to a single event.

A process decomposition is a DFD that shows the internal implementation details of a single process on another DFD.

What are the advantages of DFDs?
  • DFDs depict flow and boundary.
  • DFD represents a graphical display of the process and is therefore a usable document that can be shown to both users and programmers. It serves the users as process verification.It serves the programmers as the schematic (blueprint) of the system from a technical perspective.
  • It can be used in JAD sessions and as part of the business specification documentation.
  • Most important, it can be used for maintaining and enhancing a process.

Sunday 20 May 2012

Difference between Insertion and Selection Sort

Insertion Sort
Selection Sort
Insertion sort, sorts a set of records by inserting record into an existing sorted file. The closer the file is sorted the more efficient the insertion sort becomes.

A selection sort is one in which successive elements are selected in order and placed into their proper sorted positions.

In insertion sort we know the element and search for its place.

In selection sort we know the place and search the element to be placed.
It is a live sorting technique. It can sort the data as it arrives.

It requires all the data to be present at the beginning of the sort.

This is a stable sorting algorithm.
This is not a stable sorting algorithm.

If the initial data is sorted then -
Comparisons = n*(n-1)/2
Moves = 0
Comparisons = n*(n-1)/2
Moves = 0

If the initial data is in reverse order then -
Comparisons =(n-1)
Moves = 2+3+4+ ----- +n
Comparisons = n*(n-1)/2
Moves = n/2 * 3 (each swap consist of 3 moves)


Saturday 19 May 2012

Multi Key Organization [Data Structures]

This technique is used to sort a file based on multiple key values. Multi key file organization allows access to a data file by several different key fields. Example: Library file that requires access by author and by subject matter and title.

Scenario 1 can be like, sort the file based on roll number (this is key; you can also create clustered index). On an attribute may be other than roll number e.g. Class (MCA-I, MCA-II, MCA-III, …., MCA-VI) invert the file. 

Now if I wish to access the records of students from MCA-VI, I will locate the first record and will go sequentially in the linked list. This technique works great if -

  • Attribute on which I am inverting is primary key or having nearly unique values
  • The need is to access everybody in a particular class

Longer the list, it is going to be a clumsy scan. The list can be flexible in size.
  • Selection/Search – go in a particular order;
  • Insertion – will be easy in append mode;
  • Deletion – 1) Re-arrange pointer     2) Mark deleted & re-arrange pointer at later point of time.
Scenario 2, records are sorted based on Roll numbers; now requirement is to get names of students starting with ‘J’. Therefore create inverted index on names where names starting with each alphabet will be stored as linked list. Now go through the linked list of ‘J’ to get all the records.


Indexed Sequential Organization [Data Structures]

This is a filing method used on direct access storage devices in which records are arranged in logical sequence by a key. Indexes to these keys permit direct access to individual records. In this file organization, the records of the file are stored one after another in the order they are added to the file. Indexed files can have random or sequential access modes. There is a range of keys (k1 to kn) that belong to a block. From key -> Block no. -> (sector no, Track no). The records need not to be sorted.

Clustered Index


If records are to be accessed sequentially and are placed at far places (different blocks) then the number of disk accesses increases resulting in inefficiency. Hence logically next records of a database should be placed on the same block to the extent possible i.e. “Records logically next should be physically close”. This storing of records in organizational way results in

  1. Reduced number of disk accesses
  2. On the page (block) we don’t need logical organization among records. They need not to be sorted.


Indexed File Organization [Data Structures]

A table is built on the top of the file. The queries and frequency of queries will decide the need for making index on one or more fields. There will be an space overhead for storing the table but this need must be justified. 

When the size of index table is too big, only a small portion of this table can be fetched into main memory and keeping the keys in sorted order becomes impossible. Hence this entire thing is maintained using B Tree. The same information of index table with essential organization can be represented using B Tree.

Relative File Organization [Data Structures]

There should be some logic for placing a particular record at particular place. Using hashing the address generated can’t be physical address. You can’t pinup the record at particular place. Hence hashing does not generate absolute address due to following reasons.

  1. The absolute address has to be some track number, sector number
  2. If we succeed and pinup a record at a particular place then we won’t be able to defragment the file at any later point of time.

h(key) -> rid : rid is the relative position of the record in the file. If 5 records can fit on a block then all the 5 records fitting on a particular block will have same rid. Hence h(key) -> bid. This block number is given to the OS routine, which maps bid to (track no, sector no). The OS routine will not perform any calculation instead it will search the mapping in a table. This is because, if you do calculation (i.e. you do pinning) then the block can’t be moved but table provide flexibility of changing the place if required by just updating the corresponding bid -> (track no, sector no) mapping in the table. This whole scheme is called Direct Access Mode. Relative file organization of DS fits well with this mode. Once file grows you have to shift entire file, therefore there will be a lot of hassle.

Insertion
  • Block is partially empty – use the space
  • Block is not empty – use another (overflow) block
Deletion of records will be with a marker (X). Records will be physically present but marked deleted.

File Organization Basics [Data Structures]

In data structure, file is a collection of records one after another and having fixed length.
  • Insertion – At the end;
  • Deletion – Anywhere;
  • Search – Record by record;
In Data Structure it is called as heap, in OS it is called as sequential file. OS visualizes file as a series of blocks as it is not concerned about the contents of the file. A block is generally of the size of sector defined on disk. Disk can be hard sector (predefined sectors generally 8) or soft sector (user defined sectors which we use). OS does everything (deleting or appending records) in terms of blocks.

If we consider a disk with 8 sectors then every track will have sectors numbered from 1 to 8. Contents of the file (block) is defines using track number - sector number combination. FAT maintains this entry indicating the ith block (bi) is stored at track n and sector j.

Space to a file cannot be allocated in advance as it may grow beyond expectations. Hence every time when a block is required OS looks for empty block (a mark is associated with the block indicating its availability). When an available block is encountered then it is given to the file, an entry is made in the FAT and the block’s entry is deleted from available list; and finally file contents are appended.

If the FAT is too long then locating a block with desired data will be an exhaustive search. Hence in UNIX, the first 10 entries of DAT are direct addresses (directly pointing to data blocks). The 11th block will store the address of the block holding addresses of other data blocks. The 12th block will point to a block, which is pointing to other blocks holding addresses of data blocks.

Direct
Single Indirect
Double Indirect
Triple Indirect
10
500
500 X 500 = 5002
500 X 500 X 500 = 5003

Note: The number 500 will differ from OS to OS, installation to installation, machine to machine. It is size of block/size of each address.

This system supports small size files and at the same time it can support large files too. It provides quick access to small files and at the same time supports big files with little reduced efficiency. The table with 10+3 entries has to be memory resident. The direct addressing blocks can be configured if average file size is smaller or larger than predefined 10 direct blocks. A 4th level of indirection can also be added using 14th block. Levels of indirection are added in incremental manner.

Hence the advantages of UNIX FAT over traditional FAT are
  1. FAT need to be memory resident and huge FAT can’t be accommodated.
  2. Searching through big size FAT – As it won’t fit on memory so you need to perform multiple disk accesses and at the end you may not be having the address you were looking for. We can’t spend too much time on just locating the address of a block.
Disk Access & Block Organization

As head passes through blocks, contents are read, loaded into disk buffer and then transferred to RAM. Once the disk buffer is full, it needs some time to get flushed before other data can be placed in it.



Physical Organization


Logical Organization


In this organization, blocks are stored one after another. The R/W head moves with a constant speed. After reading b1, the disk buffer is full and the R/W head is in b2 which is the next block to be read. As we need some time to empty the disk buffer hence this organizations is not efficient.

In this organization, blocks are placed at a distance of two blocks. After reading b1, the disk buffer is full. The R/W head has to skip two blocks and during this time the disk buffer can be flushed. Hence this is an efficient block organization.


Track no. is the thing that expects physical movement of head which occurs in a jumpy manner. The track no. access requests need to be optimized with the intention of minimizing head movement on disk. Hence different disk scheduling techniques are used. As the disk scheduling algorithms optimize the head movement therefore a request placed fists may be fulfilled later.

Record Number -> Block Number -> (Track Number, Sector Number) -> Disk



If records are of fixed size then a fixed n records can be placed on a block. Never ever split record across blocks. Now translate record no. to block no. using simple calculation. E.g. if 2 records are on each block then 9th record will be on 4th block.
  • B Tree: Key Value -> Record id (rid) -> Block id (bid) -> (Track number, Sector Number)
  • Hashing: h (Key Value) - > Record id (rid) -> Block id (bid) -> (Track number, Sector Number)
Logical & Physical Address Space – The record with key value 50 is logical view of record. rid to bid is logical address translation. Obtaining (Track Number, Sector Number) from bid is physical address translation.

In Hashing with bucketing the rid itself will be bid. Bucket Address = Block no. Hence h(key) -> bid -> ts.

Do you like this article?