Relation algebra

JOIN Operator

JOIN is used to combine related tuples from two relations:

• In its simplest form the JOIN operator is just the cross product of the two relations.
• As the join becomes more complex, tuples are removed within the cross product to make the result of the join more meaningful.
• JOIN allows you to evaluate a join condition between the attributes of the relations on which the join is undertaken.

The notation used is

 R JOINjoin condition S

JOIN Example

Figure : JOIN

Natural Join

Invariably the JOIN involves an equality test, and thus is often described as an equi-join. Such joins result in two attributes in the resulting relation having exactly the same value. A `natural join' will remove the duplicate attribute(s).

• In most systems a natural join will require that the attributes have the same name to identify the attribute(s) to be used in the join. This may require a renaming mechanism.
• If you do use natural joins make sure that the relations do not have two attributes with the same name by accident.

OUTER JOINs

Notice that much of the data is lost when applying a join to two relations. In some cases this lost data might hold useful information. An outer join retains the information that would have been lost from the tables, replacing missing data with nulls.
There are three forms of the outer join, depending on which data is to be kept.

• LEFT OUTER JOIN - keep data from the left-hand table
• RIGHT OUTER JOIN - keep data from the right-hand table
• FULL OUTER JOIN - keep data from both tables

OUTER JOIN example 1

Figure : OUTER JOIN (left/right)

OUTER JOIN example 2

binarysearch tree

  #include<iostream.h>
          #include<conio.h>
          #include<stdio.h>
          #include<stdlib.h>
          struct node
          {
               int data;
               node *left;
               node *right;
          };

          node *tree=NULL;
          node *insert(node *tree,int ele);

          void preorder(node *tree);
          void inorder(node *tree);
          void postorder(node *tree);
          int count=1;

          void main()
          {
               clrscr();
               int ch,ele;
               do
               {
                    clrscr();
                    cout<<"\n\t\a\a1----INSERT A NODE IN A BINARY TREE.\a\a";
                    cout<<"\n\t\a\a2----PRE-ORDER TRAVERSAL.\a\a";
                    cout<<"\n\t\a\a3----IN-ORDER TRAVERSAL.\a\a";
                    cout<<"\n\t\a\a4----POST-ORDER TRAVERSAL.\a\a";
                    cout<<"\n\t\a\a5----EXIT.\a\a";
                    cout<<"\n\t\a\aENTER CHOICE::\a\a";
                    cin>>ch;
                    switch(ch)
                    {
                         case 1:
                         cout<<"\n\t\a\aENTER THE ELEMENT::\a\a";
                         cin>>ele;
                         tree=insert(tree,ele);
                         break;

                         case 2:
                         cout<<"\n\t\a\a****PRE-ORDER TRAVERSAL OF A TREE****\a\a";
                         preorder(tree);
                         break;

                         case 3:
                         cout<<"\n\t\a\a****IN-ORDER TRAVERSAL OF A TREE****\a\a";
                         inorder(tree);
                         break;

                         case 4:
                         cout<<"\n\t\a\a****POST-ORDER TRAVERSAL OF A TREE****\a\a";
                         postorder(tree);
                         break;

                         case 5:
                         exit(0);
                    }
               }while(ch!=5);
          }

          node *insert(node *tree,int ele)
          {
               if(tree==NULL)
               {
                    tree=new node;
                    tree->left=tree->right=NULL;
                    tree->data=ele;
                    count++;
               }
               else
               if(count%2==0)
               tree->left=insert(tree->left,ele);
               else
               tree->right=insert(tree->right,ele);
               return(tree);
          }

          void preorder(node *tree)
          {
               if(tree!=NULL)
               {
                    cout<<tree->data;
                    preorder(tree->left);
                    preorder(tree->right);
                    getch();
               }
          }

          void inorder(node *tree)
          {
               if(tree!=NULL)
               {
                    inorder(tree->left);
                    cout<<tree->data;
                    inorder(tree->right);
                    getch();
               }
          }

          void postorder(node *tree)
          {
               if(tree!=NULL)
               {
                    postorder(tree->left);
                    postorder(tree->right);
                    cout<<tree->data;
                    getch();
               }
          }

towers of hanoi.

#include<iostream.h>
void move(int n,char *s,char *i,char *d)
// s stands for source tower
// d stands for destination tower
// i stands for intermediate tower
{
 if(n>0)
 {
  move(n-1,s,d,i);
  // move n-1 disks from source to intermediate tower
  cout<<”disk “<<n<<” is moved from “<<s<<” to “<<d<<endl;
  // move the disk from to source to destination
  move(n-1,i,s,d);
  // move n-1 disks from intermediate to destination
 }
}
void main()
{
 cout<<”\n**********************************************************\n”;
 cout<<”This C++ program is to solve the towers of hanoi problem”;
 cout<<”\n**********************************************************\n”;
 cout<<”Enter the no. of disks “;
 int n;
 cin>>n;
 move(n,”source tower”,”intermediate tower”,”destination tower”);
}

queue linkedlist

#include<conio.h>    
#include<iostream.h> 
#include<process.h>  
#include<malloc.h>  
 
//   Creating a NODE Structure
struct node
{
   int data;
   struct node *next;
};
 
// Creating a class QUEUE
class queue
{
   struct node *frnt,*rear;
   public:
      queue() // constructure
      {
  frnt=rear=NULL;
      }
      void insert(); // to insert an element
      void del();  // to delete an element
      void show(); // to show the stack
};
// Insertion
void queue::insert()
{
   int value;
   struct node *ptr;
   cout<<"\nInsertion\n";
   cout<<"Enter a number to insert: ";
   cin>>value;
   ptr=new node;
   ptr->data=value;
   ptr->next=NULL;
   if(frnt==NULL)
      frnt=ptr;
   else
      rear->next=ptr;
   rear=ptr;
   cout<<"\nNew item is inserted to the Queue!!!";
   getch();
}
 
// Deletion
void queue::del()
{
   if(frnt==NULL)
   {
      cout<<"\nQueue is empty!!";
      getch();
      return;
   }
   struct node *temp;
   temp=frnt;
   frnt=frnt->next;
   cout<<"\nDeletion Operation........\nDeleted value is "<<temp->data;
   delete temp;
   getch();
}
 
// Show Queue
void queue::show()
{
   struct node *ptr1=frnt;
   if(frnt==NULL)
   {
      cout<<"The Queue is empty!!";
      getch();
      return;
   }
   cout<<"\nThe Queue is\n";
   while(ptr1!=NULL)
   {
      cout<<ptr1->data<<" ->";
      ptr1=ptr1->next;
   }
   cout<<"END";
   getch();
}
 
// Main function
int main()
{
   clrscr();
   queue q;
   int choice;
   while(1)
   {
      cout<<"\n-----------------------------------------------------------";
      cout<<"\n\t\tQUEUE USING LINKED LIST\n\n";
      cout<<"1:INSERTION\n2:DELETION\n3:DISPLAY QUEUE\n4:EXIT";
      cout<<"\nEnter your choice(1-4): ";
      cin>>choice;
      switch(choice)
      {
       case 1:
   q.insert();
   break;
       case 2:
   q.del();
   break;
       case 3:
   q.show();
   break;
       case 4:
   exit(0);
   break;
       default:
   cout<<"Please enter correct choice(1-4)!!";
   getch();
   break;
       }
   }
   return 0;
}
 

infix to prefix

#include <iostream.h>
#include <string.h>
#include <ctype.h>
const int MAX = 50 ;
class infix
{
 private :
  char target[MAX], stack[MAX] ;
  char *s, *t ;
  int top, l ;
 public :
  infix( ) ;
  void setexpr ( char *str ) ;
  void push ( char c ) ;
  char pop( ) ;
  void convert( ) ;
  int priority ( char c ) ;
  void show( ) ;
} ;
infix :: infix( )
{
 top = -1 ;
 strcpy ( target, "" ) ;
 strcpy ( stack, "" ) ;
 l = 0 ;
}
void infix :: setexpr ( char *str )
{
 s = str ;
 strrev ( s ) ;
 l = strlen ( s ) ;
 * ( target + l ) = '\0' ;
 t = target + ( l - 1 ) ;
}
void infix :: push ( char c )
{
 if ( top == MAX - 1 )
  cout << "\nStack is full\n" ;
 else
 {
  top++ ;
  stack[top] = c ;
 }
}
char infix :: pop( )
{
 if ( top == -1 )
 {
  cout << "Stack is empty\n" ;
  return -1 ;
 }
 else
 {
  char item = stack[top] ;
  top-- ;
  return item ;
 }
}
void infix :: convert( )
{
 char opr ;
 
 while ( *s )
 {
  if ( *s == ' ' || *s == '\t' )
  {
   s++ ;
   continue ;
  }
 
  if ( isdigit ( *s ) || isalpha ( *s ) )
  {
   while ( isdigit ( *s ) || isalpha ( *s ) )
   {
    *t = *s ;
    s++ ;
    t-- ;
   }
  }
 
  if ( *s == ')' )
  {
   push ( *s ) ;
   s++ ;
  }
 
  if ( *s == '*' || *s == '+' || *s == '/' ||
    *s == '%' || *s == '-' || *s == '$' )
  {
   if ( top != -1 )
   {
    opr = pop( ) ;
 
    while ( priority ( opr ) > priority ( *s ) )
    {
     *t = opr ;
     t-- ;
     opr = pop( ) ;
    }
    push ( opr ) ;
    push ( *s ) ;
   }
   else
    push ( *s ) ;
   s++ ;
  }
 
  if ( *s == '(' )
  {
   opr = pop( ) ;
   while ( ( opr ) != ')' )
   {
    *t = opr ;
    t-- ;
    opr =  pop ( ) ;
   }
   s++ ;
  }
 }
 
 while ( top != -1 )
 {
  opr = pop( ) ;
  *t = opr ;
  t-- ;
 }
 t++ ;
}
int infix :: priority ( char c )
{
 if ( c == '$' )
  return 3 ;
 if ( c == '*' || c == '/' || c == '%' )
  return 2 ;
 else
 {
  if ( c == '+' || c == '-' )
   return 1 ;
  else
   return 0 ;
 }
}
void infix :: show( )
{
 while ( *t )
 {
  cout << " " << *t ;
  t++ ;
 }
}
 
void main( )
{
 char expr[MAX] ;
 infix q ;
 
 cout << "\nEnter an expression in infix form: " ;
 cin.getline ( expr, MAX ) ;
 
 q.setexpr( expr ) ;
 q.convert( ) ;
 
 cout << "The Prefix expression is: " ;
 q.show( ) ;

infix to post fix

#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
class expression
{
private:
 char infix[100];
 char stack[200];
 int top;
 int r;
 char postfix[100];
public:
 void convert();
 int input_p(char);
 int stack_p(char);
 int rank(char);
};
int expression::input_p(char c)
{
 if(c==’+’ || c==’-')
  return 1;
 else if(c==’*’ || c==’/')
  return 3;
 else if(c==’^')
  return 6;
 else if(isalpha(c)!=0)
  return 7;
 else if(c==’(‘)
  return 9;
 else if(c==’)')
  return 0;
 else
 {
  cout<<”Invalid expression ::input error\n”;
  exit(0);
 }
}
int expression::stack_p(char c)
{
 if(c==’+’ || c==’-')
  return 2;
 else if(c==’*’ || c==’/')
  return 4;
 else if(c==’^')
  return 5;
 else if(isalpha(c)!=0)
  return 8;
 else if(c==’(‘)
  return 0;
 else
 {
  cout<<”Invalid expression  ::stack error\n”;
  exit(0);
 }
}
int expression::rank(char c)
{
 if(c==’+’ || c==’-')
  return -1;
 else if(c==’*’ || c==’/')
  return -1;
 else if(c==’^')
  return -1;
 else if(isalpha(c)!=0)
  return 1;
 else
 {
  cout<<”Invalid expression ::in rank\n”;
  exit(0);
 }
}
void expression::convert()
{
 cout<<”\n*************************************************\n”
  <<”This program converts the given infix expression\n”
  <<”in to postfix form”
                <<”\n*************************************************\n”;
 cout<<”Enter an infix expression ::\n”;
 cin>>infix;
 int l=strlen(infix);
 infix[l]=’)';
 infix[l+1]=”;
 //Convertion starts
 top=1;
 stack[top]=’(‘;
 r=0;
 int x=-1;
 int i=0;
 char next=infix[i];
 while(next!=”)
 {
  //Pop all the elements to outputin stack which have higher precedence
  while( input_p(next) < stack_p(stack[top]) )
  {
   if(top<1)
   {
    cout<<”invalid expression ::stack error\n”;
    exit(0);
   }
   postfix[++x]=stack[top];
   top–;
   r=r+rank(postfix[x]);
  
   if(r<1)
   {
    cout<<”Invalid expression  ::r<1\n”;
    exit(0);
   }
  }
  if(input_p( next ) != stack_p( stack[top]))
   stack[++top]=next;
  else
   top–;
  i++;
  next=infix[i];
 }
 postfix[++x]=”;
 if(r!=1 || top!=0)
 {
  cout<<”Invalid expression ::error in rank or stack\n”;
  exit(0);
 }
 cout<<”\n\nThe corresponding postfix expression is ::\n”;
 cout<<postfix<<endl;
}
int main()
{
 expression obj;
 obj.convert();
 return 0;
}
/************************************************************************
SAMPLE OUTPUT::
—————

*************************************************
This program converts the given infix expression
in to postfix form
*************************************************
Enter an infix expression ::
(a+b^c^d)*(c+d)
The corresponding postfix expression is ::
abcd^^+cd+*

reverse string with c++

#include <iostream>
#include <string>
using namespace std;
 
void recursiveReverse( char a[], int start, int end )
{
 int i, j;
 
 for(i=start; i<end; i++)
 {
 
  for(j=end;j>start;j--)
  {
   char temp = a[i];
   a[i]=a[j];
   a[j]=temp;
  }
 
 }
 
}
 
 
 
void stringReverse( char str[] )
{
  int length = strlen( str );
  recursiveReverse( str, 0, length - 1 );
}
 
int main()
{
 
  char a[20];
 
  for (int i = 0; i < 20; i++ )
  a[i] = 'A' + i;
  a[19] = '\0';
  cout << "string before reversing:  " << a << endl;
  stringReverse( a );
  cout << "string  after reversing:  " << a << endl;
  return 0;

towers of hanoi c++

#include <iostream>
#include <vector>
using namespace std;
 
void towers( vector <int> &disks, int start, int end, int temp)
{
 if( disks == 1 )  // base case
  cout <<start <<"---> "<< end <<"\n";
 
  else //recursion step
  {
   //move disks - 1 disk from start to temp
      towers(disks - 1, start, temp, end);
 
   //move last disk from start to end
   cout<<start<< "---> "<< end << "\n";
 
   //move disks - 1 disk from temp to end
   towers(disks - 1, temp, end, start);
 
  } // end else
} // end function towers
 
int main() 
{
 int n;
    cout<<"Enter number of Discs: ";
 cin >> n;
    towers(n, 1, 3, 2);
    return 0;
}