The Student Database Examples: Part 1

Database Operations

The Students example showed the development of a class Student and the use of an array to store a collection of student records. In general, if we are maintaining a database we need not only to store records, but to update the database by adding and deleting records. We would also want to be able to look up individual records. Here is a program which provides the "front end" to a student database:
     1  import*;
     2  import java.util.*;
     4  class StudentDatabaseUse
     5  {
     6  //  Read a number of Student records from a file, store them in a
     7  //  database, and perform operations on them.
     8  //  The file is given as a command line operator
    10     public static void main(String[] args) throws IOException
    11     {
    12      Database database=null;
    13      Student newStudent,foundStudent;
    14      BufferedReader in = new BufferedReader(new InputStreamReader(;
    15      BufferedReader inFile;
    16      String surname,command;
    17      char ch;
    18      int i;
    19      if(args.length==0)
    20         {
    21          System.out.println("File name should be given as command-line argument");
    22          System.exit(1);
    23         }
    24      try
    25         {
    26          inFile = new BufferedReader(new FileReader(args[0]));
    27          database = new StudentDatabase1();
    28          for(;;)
    29             try
    30                {
    31       ;
    32                 database.insert(newStudent);
    33                }
    34             catch(PersonException e)
    35                {
    36                 System.out.println(e.getMessage()+"\n");
    37                }
    38         }
    39      catch(FullUpException e)
    40         {
    41          System.out.println("No room for any more records");
    42         }
    43      catch(FileNotFoundException e)
    44         {
    45          System.out.println("No file '"+args[0]+"' found");
    46          System.exit(2);
    47         }
    48      catch(IOException e)
    49         {
    50         }
    51      ch='l';
    52      while(ch!='q')
    53         {
    54          switch(ch)
    55             {
    56              case 'l': database.list(); break;
    57              case 'd': System.out.print("Enter surname of student to be deleted: ");
    58                        surname=in.readLine();
    59                        try {
    60                             database.delete(surname);
    61                             System.out.println("Record deleted\n");
    62                            }
    63                        catch(NotFoundException e)
    64                            {
    65                             System.out.println("No record found for "+surname+"\n");
    66                            }
    67                        break;
    68              case 'r': System.out.print("Enter surname of student: ");
    69                        surname=in.readLine();
    70                        try {
    71                             foundStudent=(Student)database.retrieve(surname);
    72                             System.out.println("\nFull record is:\n");
    73                             System.out.println(foundStudent);
    74                            }
    75                        catch(NotFoundException e)
    76                            {
    77                             System.out.println("No record found for "+surname+"\n");
    78                            }
    79                        break;
    80              case 'i': try {
    81                             newStudent=Student.promptedRead(in);
    82                             database.insert(newStudent);
    83                             System.out.println("Record inserted\n");
    84                            }
    85                        catch(PersonException e)
    86                            {
    87                             System.out.println(e.getMessage()+"\n");
    88                            }
    89                        catch(FullUpException e)
    90                            {
    91                             System.out.println("No room for any more records\n");
    92                            }
    93                        break;
    94              case 'q': break;
    95              default: System.out.println("Not a valid command");
    97             }
    98          do {
    99              do {
   100                  System.out.print("Enter command: ");
   101                  command=in.readLine();
   102                 }
   103              while(command.length!=0);
   104              i=0;
   105              do {
   106                  ch=command.charAt(i++);
   107                 }
   108              while(ch==' '&&i<command.length());
   109             }
   110          while(ch==' ');
   111         }
   112     }
The program is designed to read a list of student records from a file, and store them in a database. In this case, the file is given as as a command line argument, so to run the program taking the data from a file called mystudents you would have to type the Linux command:
% java StudentDatabaseUse1 mystudents
Line 26 is where the command line argument, which in the above case would store the string "mystudents" is accessed as args[0]. If the file named "mystudents" is not found then a FileNotFoundException is created, this is caught on line 43, the System.exit(2) command on line 46 then causes the program to halt right away. In general, System.exit(n) where n is an integer causes program execution to halt. The convention is that n is 0 if the program halts normally, some other value if it is halting due to some error. In this case an error code 2 is produced. The error code can be used in Linux, but you need not be concerned with it at present - it will be ignored if the program is just run normally.

The complex code on lines 98-109 is designed to make sure the program behaves sensibly no matter what the user enters in response to the prompt for a new command. It has to be able to read past blanks and newlines until it gets to a character which is treated as a command.

The database is declared on line 12, the initialisation to the special value null here just indicates explicitly that it is not referencing any object. It starts referencing an object on line 27 when a new object of class StudentDatabase1 is created. The important thing is that a completely object-oriented approach to the database is taken. The database is only operated on through its methods: insert on lines 32 and 82, list on line 56, delete on line 60 and retrieve on line 71. Compare this with the example in the Students page where there was no separate class for a student database, it was just represented as an array which could be accessed or modified by any array operation.

The importance of the separate object for the database is that now it does not matter how the database is stored. We have only seen arrays at this point for storing collections of objects, but there are other ways. We could change the way we represented a database without having to change the StudentDatabaseUse1 class, because that class does not depend on any particular representation. This is what we referred to as data hiding in the Dates: Part 3 examples. Just as in those examples we avoided being able to arbitarily change the components of dates, which could result in invalid dates, so here we avoid arbitary changing of the components of the database. As the only way the database can be changed is through its methods, it can ensure that these methods are written in such a way as to maintain its consistency.

Interface use

You will see on line 12 of the program the variable database is declared to be of type Database whereas on line 27 it is set to a new object of type StudentDatabase1. This can be done if StudentDatabase1 is a subclass (i.e. inherits from) Database, or implements it. In this case, Database is just an interface (see the People example where the idea of a Java interface is first introduced) which says what the methods on a database are, but does not say how they are implemented. Here is the code for it:
     1  interface Database
     2  {
     3   public void insert(Object obj) throws FullUpException;
     4   public void delete(String key) throws NotFoundException;
     5   public Object retrieve(String key) throws NotFoundException;
     6   public void list();
     7  }
As you can see, it does not even mention Students. In fact this is an interface for a general database which can store objects of any sort. In Java the type Object means an object of any sort. In fact any class which does not inherit from another class is treated as automatically having Object as the superclass it inherits from. The method insert inserts the object it takes as its argument into the database (thus Database is a mutable type as objects of that type can be changed by methods on them). The method delete takes a string and deletes an object which this string refers to. In the student database example, the string is the surname of the student, so this operation is used to delete a student with a given surname (for simplicity we will ignore the complexities caused by more than one student having the same surname). Again, this is a mutating operation. The method retrieve returns the object in the database associated with a given string but does not change the database, so it is non-mutating. The method list lists the entire database. If a string is given as argument to delete or retrieve but no object is found associated with that string an exception is thrown. The exception is not one that is built into Java, so a class for it is needed:
     1  class NotFoundException extends Exception
     2  {
     3   NotFoundException(String s)
     4   {
     5    super(s);
     6   }
     7  } 
Another exception, again not built-in, is thrown if there is not enough room to store a new object in the database:
     1  class FullUpException extends Exception
     2  {
     3  }
As a new FullUpException has no arguments, no more is needed than that. A new NotFoundException has one argument (the string which was used as reference) so a constructor method for it is necessary.

An implementation of interface Database

Any class, so long as it has methods with the same headers as in the Database interface, may implement that interface. Here is the code for StudentDatabase1 which implements it using an unordered array:
     1  class StudentDatabase1 implements Database
     2  {
     3  // Implemented with an unordered array
     5   private static final int MaxStudents=100;
     6   private Student[] array;
     7   private int numStudents;
     9   public StudentDatabase1()
    10   {
    11    numStudents=0;
    12    array = new Student[MaxStudents];
    13   }
    15   public void insert(Object obj) throws FullUpException
    16   {
    17    if(numStudents<MaxStudents)
    18       array[numStudents++]=(Student)obj;
    19    else
    20       throw new FullUpException();
    21   }
    23   public void delete(String key) throws NotFoundException
    24   {
    25    int i;
    26    for(i=0;i<numStudents;i++)
    27       if(array[i].equalKey(key))
    28          break;
    29    if(i==numStudents)
    30       throw new NotFoundException(key);
    31    for(int j=i+1;j<numStudents;j++)
    32       array[j-1]=array[j];
    33    numStudents--;
    34   }
    36   public Object retrieve(String key) throws NotFoundException
    37   {
    38    int i;
    39    for(i=0;i<numStudents;i++)
    40       if(array[i].equalKey(key))
    41          break;
    42    if(i==numStudents)
    43       throw new NotFoundException(key);
    44    return array[i];
    45   }
    47   public void list()
    48   {
    49    for(int i=0; i<numStudents; i++)
    50       System.out.println(array[i]);
    51   }
    53  }
Note that in order to assign a value of type Object to a variable of type Student it is necessary to use type conversion. This is done on line 71 of StudentDatabaseUse1 where the object retrieved from the database is converted from the general Object type which is the return type of retrieve to the specific Student type. It is also done on line 15 of StudentDatabase1. Although the database in StudentDatabase1 is meant to store Student objects, the type of the argument to insert and the return value of retrieve have to be Object in order for it to implement Database.

Although StudentDatabase1 stores student records in an array, the array is private so only a StudentDatabase1 object can access it either to look at or alter its content. StudentDatabase1 objects also have a private NumStudents field giving the number of students, which is also the portion of the array which is actually in use. When a new StudentDatabase1 object is created, the array is created, but numStudents is set to 0 indicating that none of the array is in use in a newly created database. The length of the array in a StudentDatabase1 object is declared as a static final variable, meaning there is just one copy of it shared by all objects of type StudentDatabase1 and its value may not be changed by any of them. These declarations and the constructor method for creating new StudentDatabase1 objects are given on lines 5-13.

Inserting a new student record (done using method insert on lines 15-21 of StudentDatabase1) is easy - it is just put in the next unused space in the array, the one indexed by numStudents, and numStudents is increased by one. The only difficulty is that since the array is of fixed length, attempting to store more student records than its length could cause problems. If an unchecked attempt was made to store more student records than the maximum set by MaxStudents, an ArrayIndexOutOfBoundsException would be caused. However, in this example before that happens, a FullUpException is produced and thrown. This is caught on line 89 of the "front-end" class, StudentDatabaseUse1 and an appropriate error message is printed.

The delete and retrieve methods (lines 23-34 and 36-45 respectively) both go through the array one element at a time using a for-loop, breaking if an element is found on which the equalKey method with the string supplied as its argument returns true. It is assumed that with student records, if S is of type Student then S.equalKey(nm) will return true if the surname of the student is equal to key, false otherwise. If the loop in delete or retrieve finishes without break being executed, it can only have done so if no student with the given name has been found, in which case a new NotFoundException is created and thrown. In the case of delete, a further loop (lines 31-32) is needed to move all the student records after the deleted one back one space in the array in order not to leave a "hole". This is one of the major inefficiencies of this method of representing the database (note however that since all objects are actually references, "moving" a student record involves copying only a reference to the data, not the data itself). Another source of inefficiency is the need to look through all the records to find one for a particular name. It would obviously be more convenient if the records were stored in alphabetic order.

As we have made quite a few changes to the class Student in a piecemeal fashion, here is the version used now:

     1  import java.util.*;
     2  import*;
     4  class Student extends Person
     5  {
     6   protected static int count=10000;
     7   protected static final int MAXMARKS=30;
     8   protected int numSubjects,studentNum;
     9   protected int[] marks;
    10   protected String firstNames;
    12   public Student(int d,int m, int y,String n1,String n2,int num,int marks [])
    13   throws PersonException
    14   {
    15    super(d,m,y,n1);
    16    numSubjects=num;
    17    this.marks=marks;
    18    firstNames=n2;
    19    studentNum=++count;
    20   }
    22   public static Student read(BufferedReader reader)
    23   throws IOException,PersonException
    24   {
    25    int day,month,year,numMarks;
    26    String name,marksString,dateString,nameString,firstNames;
    27    StringTokenizer tokens;
    28    int[] marks;
    29    nameString=reader.readLine();
    30    if(nameString==null)
    31       throw new IOException();
    32    tokens = new StringTokenizer(nameString);
    33    firstNames = tokens.nextToken();
    34    name=tokens.nextToken();
    35    while(tokens.hasMoreTokens())
    36       {
    37        firstNames+=" "+name;
    38        name=tokens.nextToken();
    39       }
    40    dateString=reader.readLine();
    41    tokens = new StringTokenizer(dateString,"/");
    42    day=Integer.parseInt(tokens.nextToken());
    43    month=Integer.parseInt(tokens.nextToken());
    44    year=Integer.parseInt(tokens.nextToken());
    45    marks = new int[MAXMARKS];
    46    marksString=reader.readLine();
    47    tokens = new StringTokenizer(marksString);
    48    numMarks=0;
    49    while(tokens.hasMoreTokens())
    50        marks[numMarks++]=Integer.parseInt(tokens.nextToken());
    51    return new Student(day,month,year,name,firstNames,numMarks,marks);
    52   }
    54   public static Student promptedRead(BufferedReader reader)
    55   throws IOException,PersonException
    56    {
    57    int day,month,year,numMarks;
    58    String name,marksString,dateString,nameString,firstNames;
    59    StringTokenizer tokens;
    60    int[] marks;
    61    System.out.println("Enter name (first names followed by surname on one line):");
    62    nameString=reader.readLine();
    63    if(nameString==null)
    64       throw new IOException();
    65    tokens = new StringTokenizer(nameString);
    66    firstNames = tokens.nextToken();
    67    name=tokens.nextToken();
    68    while(tokens.hasMoreTokens())
    69       {
    70        firstNames+=" "+name;
    71        name=tokens.nextToken();
    72       }
    73    System.out.println("Enter date of birth (in dd/mm/yy format):");
    74    dateString=reader.readLine();
    75    tokens = new StringTokenizer(dateString,"/");
    76    day=Integer.parseInt(tokens.nextToken());
    77    month=Integer.parseInt(tokens.nextToken());
    78    year=Integer.parseInt(tokens.nextToken());
    79    marks = new int[MAXMARKS];
    80    System.out.println("Enter marks (all one one line):");
    81    marksString=reader.readLine();
    82    tokens = new StringTokenizer(marksString);
    83    numMarks=0;
    84    while(tokens.hasMoreTokens())
    85        marks[numMarks++]=Integer.parseInt(tokens.nextToken());
    86    return new Student(day,month,year,name,firstNames,numMarks,marks);
    87    }
    89   public String toString()
    90   {
    91    String marksString="";
    92    for(int i=0;i<numSubjects;i++)
    93       marksString+=" "+marks[i];
    94    return "Name: "+firstNames+" "+name+
    95           "\nDate of birth: "+dateOfBirth+
    96           "\nStudent number: "+studentNum+
    97           "\nMarks: "+marksString+"\n";
    98   }
   100   public int totalMarks()
   101   {
   102    int myMarks=0;
   103    for(int i=0;i<numSubjects;i++)
   104       myMarks+=marks[i];
   105    return myMarks;
   106   }
   108   public double averageMark()
   109   {
   110    return (double)totalMarks()/numSubjects;
   111   }
   113   public boolean lowerTotalMarksThan(Student s)
   114   {
   115    return (totalMarks()<s.totalMarks());
   116   }
   118   public boolean lowerTotalMarksThan(int n)
   119   {
   120    return (totalMarks()<n);
   121   }
   123   public boolean lowerAverageMarkThan(Student s)
   124   {
   125    return (averageMark()<s.averageMark());
   126   }
   128   public boolean lowerAverageMarkThan(double d)
   129   {
   130    return (averageMark()<d);
   131   }
   133   public boolean equalKey(String key)
   134   {
   135    return name.equals(key);
   136   }
   138  }
Note there are two methods for reading a student record. One, called read, on lines 22-52 is intended for reading the records from a file, and so issues no prompts. The other is intended for reading a student record as entered by the user of the program, so prompts for each separate piece of information. This second method, called promptedRead is on lines 54-87.

An implementation of Database using an ordered array

Here is another implementation of the Database interface, still using an array, but this time storing the student records in alphabetical order of name:
     1  class StudentDatabase2 implements Database
     2  {
     3  // Implemented with an array ordered by name
     5   private static final int MaxStudents=100;
     6   private Student[] array;
     7   private int numStudents;
     9   public StudentDatabase2()
    10   {
    11    numStudents=0;
    12    array = new Student[MaxStudents];
    13   }
    15   public void insert(Object obj) throws FullUpException
    16   {
    17    Student student=(Student)obj;
    18    int i,j;
    19    if(numStudents==MaxStudents)
    20       throw new FullUpException();
    21    else
    22       {
    23        for(i=0;i<numStudents&&array[i].beforeAlphabetically(student);i++);
    24        for(j=numStudents;j>i;j--)
    25           array[j]=array[j-1];
    26        array[i]=student;
    27        numStudents++;   
    28       }
    29   }
    31   public void delete(String key) throws NotFoundException
    32   {
    33    int i;
    34    for(i=0;i<numStudents&&array[i].name.compareTo(key)<0;i++);
    35    if(i==numStudents||array[i].name.compareTo(key)>0)
    36       throw new NotFoundException(key);
    37    for(int j=i+1;j<numStudents;j++)
    38       array[j-1]=array[j];
    39    numStudents--;
    40   }
    42   public Object retrieve(String key) throws NotFoundException
    43   {
    44    int i;
    45    for(i=0;i<numStudents&&array[i].name.compareTo(key)<0;i++)
    46    if(i==numStudents||array[i].name.compareTo(key)>0)
    47       throw new NotFoundException(key);
    48    return array[i];
    49   }
    51   public void list()
    52   {
    53    for(int i=0; i<numStudents; i++)
    54       System.out.println(array[i]);
    55   }
    57 }
This time, since student records can't be inserted just after all the other records, but instead have to be put in their correct space in the array, the insert method has to move all records after the point where the new one is inserted up a place. The delete method has to move them down a place still. When we are retrieving or deleting a record, we know that if we have passed the place where it would be in the alphabetic ordering it can't be there, so we throw a NotFoundException without looking further. The StudentDatabaseUse program can be modified to use the ordered rather than the unordered array representation simply by replacing line 27 with:
database = new StudentDatabase2();
The only difference that will be noted in the running of the program if this change is made is what happens when the student records are listed. Both implementations print the students in the order they are in the array, so you will see that replacing the database implementation will change the order in which the student records are printed from the order in which they were inserted to the alphabetical order. For comparison, the file gives a version in which the student records are ordered by age. Inserting a student record has to ensure it is put in the right place, but as the records aren't ordered by name, retrieving and deleting a record involves looking through the whole array, until we have found it or got to the end of the data.

The method used to retrieve a student record from the array of records ordered by name, as given above is very inefficient. Suppose we were looking for a name in a telephone directory. The way that retrieve does it in StudentDatabase2 is like looking at the first name in the telephone directory and then looking at every name in turn until we either find the one we are looking for, or go past where it would be in alphabetical ordering. However, the more usual way to find a name in a telephone directory is to open it somewhere in the middle. If the name we are looking for comes before the point we have opened, we concentrate on the pages on the left-hand side, if it comes after we concentrate on the pages on the right-hand side. Then we repeat the operation with the pages we have in our hand, picking a place in the middle, and cutting the pages in half, down until we have just the right page.

This leads us naturally onto a recursive way of locating a record with a given name in an array ordered by name. We generalise the problem to locating the position between two limits (equivalent to searching just one chunk of pages in a telephone directory). We look at the midpoint - if the record we are looking for happens to be there, we have found it. Otherwise we apply the operation recursively, changing the limits to limit search to either those places in the array below the midpoint or those places above it. If the limits become equal then we have nowhere left to search, so no object with the given name occurs in the array, and a NotFoundException is thrown. Instead of going through the array one at a time so on average looking at half the records in the array to find the one being searched for, this way (known as binary search) cuts the array in half each time. It is easy to see this means looking at far fewer records to find the one being searched for, in fact the maximum will be the logarithm to the base 2 of the number of records in the array (consider, for example that 2 to the power of 10 is 1024, so the logarithm of 1024 to the base 2 is 10, or in other words, you can cut 1024 in half ten times to get to one element, so at most you would need to look at 10 records to find the one you are looking for given a name and the records ordered by name).

Here is a version of the student database class using binary search to locate records in the array:

     1  class StudentDatabase4 implements Database
     2  {
     3  // Implemented with an array ordered by name
     5   private static final int MaxStudents=100;
     6   private Student[] array;
     7   private int numStudents;
     9   public StudentDatabase4()
    10   {
    11    numStudents=0;
    12    array = new Student[MaxStudents];
    13   }
    15   public void insert(Object obj) throws FullUpException
    16   // Insert an object in the array, keeping it ordered alphabetically by name
    17   {
    18    Student student=(Student)obj;
    19    int i,j;
    20    if(numStudents==MaxStudents)
    21       throw new FullUpException();
    22    else
    23       {
    24        for(i=0;i<numStudents&&array[i].beforeAlphabetically(student);i++) ;
    25        for(j=numStudents;j>i;j--)
    26           array[j]=array[j-1];
    27        array[i]=student;
    28        numStudents++;   
    29       }
    30   }
    32   public void delete(String key) throws NotFoundException
    33   // Delete an object in the array whose name is equal to key
    34   {
    35    int i = locate(key,0,numStudents);
    36    for(int j=i+1;j<numStudents;j++)
    37       array[j-1]=array[j];
    38    numStudents--;
    39   }
    41   public Object retrieve(String key) throws NotFoundException
    42   // Return an object in the array whose name is equal to key
    43   {
    44    return array[locate(key,0,numStudents)];
    45   }
    47   public void list()
    48   // Print the entire contents of the database
    49   {
    50    for(int i=0; i<numStudents; i++)
    51       System.out.println(array[i]);
    52   }
    54   private int locate(String key,int from,int before) throws NotFoundException
    55   // Locate the position of an object with name field equal to key
    56   // in the array locations starting at from and up to but not including
    57   // before.
    58   {
    59    int mid,compare;
    60    if(from>=before)
    61      throw new NotFoundException(key);
    62    mid=(from+before)/2;
    63    compare=array[mid].name.compareTo(key);
    64    if(compare==0)
    65       return mid;
    66    else if(compare>0)
    67       return locate(key,from,mid);
    68    else
    69       return locate(key,mid+1,before);
    70   }
    72  }
Again, simply changing line 27 in the StudentDatabaseUse program will cause this version of the database to be used. Note that the method locate is private, so it can be used within class StudentDatabase4, called by delete on line 35, and retrieve on line 44, but it may not be used by methods in any other class.
Matthew Huntbach

These notes were produced as part of the course Introduction to Programming as it was given in the Department of Computer Science at Queen Mary, University of London during the academic years 1998-2001.

Last modified: 1 Dec 1998