CS245A LAB #1
Due by 5pm, Tuesday, January 27, 1998.
Your first programming lab is to implement a very simple database program using the ndbm library (described in the NDBM libray handout). Your program will be able to load a database from a text file and perform searches in the database for attributes that match an equality condition. In the next programming lab, you will add ``joins'' to your program.


Storing the Data in a ndbm database

Your program will store the database records in a ndbm database. All records in a given database have the same format, but they have variable size. The only data format for attributes that you need to support is strings.

The library ndbm manages data files that contain pairs of key and data record with a single attribute. To support multiple attributes, you need to pack them in a single record using the approach explained in class for fixed format and variable length records. For simplicity (in this and in the next lab), you can put the attribute that you are using as the key also in the data record. For example, if you have a Movie database with schema Movie( Key char(6), Name char(60), Year char(4), Ranking char(3), Score char(3)), a possible way of storing the data is to use Key as the ndbm key and a string of 81 bytes as the data record (6+60+4+3+3=76 bytes for the five data attributes and 5 additional bytes to store the actual length of each data attribute). You should consider other ways of storing the records and justify your choice in the documentation.


Header Files

The database engine interface should be specified in the header file dbe.h, which you will later ``#include'' in the main program. The dbe.h should export the following functions:

int CreateDB( char* dbName, char* datafile );

int PrintDB( char* dbName );

int RecordScan( char* dbName, int attrNumber, char* value );

int KeyScan( char* dbName, char* value );

void error( int rc );

All functions that return an int, return a ``0'' when the operation was successful or error codes (defined by you) in any other case.


DBE Functions

int CreateDB( char* dbName, char* datafile );

This function should create a database with name dbName and populate it with the data from datafile. The file datafile holds the data to be loaded in the database in ASCII format. The first line of the file defines the maximum length of each attribute. After that, every tuple to be inserted is on a seperate line in the file, with attribute values separated by ampersands (&). The first attribute value is the key of the relation. You may assume that the attribute values will not contain ampersands. Character strings in the file that are longer than the length specified in the first line should be truncated.

In the Movie database described above, the data file will have the format: 6&60&4&3&3

97141&Star Wars&1977&1&8.9

92383&Shawshank Redemption, The&1994&2&8.9

107712&Usual Suspects, The&1995&3&8.7


int PrintDB( char* dbName )

This function should print all keys and records of the database dbName in a human readable form.

int RecordScan( char* dbName, int attrNumber, char* value );

This function should print all keys and record of the database dbName for which the attribute in the attrNumber position (starting at zero) has the same value as the null-terminated string pointed by value. The function should return an error if there are less than attrNumber attributes. Note that this function must work on all attributes of the relation, including the one that you are using as the key of the ndbm database.

int KeyScan( char* dbName, char* value );

This function should print the record of the database dbName that have a key with the same value as the string pointed by value.

void error( int rc );

This function should print the error message associated with the error code rc and terminate the execution of the program


Sample Application

Following is an application that uses your databases engine to creates a database from the Movie data file defined in the previous section (assume the file is called movies.txt), prints all records in the database, prints all records with score of 8.9, and prints the record of the movie with `107712'' as key.

#include "dbe.h"

main() {

  int rc;

  if (rc=CreateDB( "mydb", "movies.txt" )) { error(rc); }

  if (rc=PrintDB("mydb")) { error(rc); }

  if (rc=RecordScan( "mydb", 4, "8.9" )) { error(rc); }

  if (rc=KeyScan( "mydb", "107712" )) { error(rc); }




Each student is expected to submit a 1 page description of your design in a plain text file called dbe.doc, and to include comments in the code.



The grade of your program will be based on three aspects:


Testing and Submission

Submission of the assignment will take place electronically. Detailed instructions for the submission process are available in a separate handout. Your dbe.doc documentation file will be submitted with your code.



We would like to bring to your attention the existence of software, designed and implemented by Prof. Alex Aiken of Berkeley, to detect plagiarism in programming projects. We are certain that nobody in the class would engage in any such behavior (which is also an Honor Code violation). However, the capability to use Aiken's software on code submitted for CS245A projects, both from this winter and from last summer, exists.