Minirel frontend system

Project Report

Advisor
Michael Carey and Raghu Ramakrishnan
Department of Computer Science
University of Wisconsin, Madison

• Introduction
• Minirel GUI and utilities
• Overview
• External interface
• Internal design
• Retrospect
• QBE->SQL translator
• Overview
• External interface
• Design layout
• Translator architecture
• Translator Data structure
• Translation algorithm
• Mechanism for translating DML queries
• Implementation status
• Retrospect
• Accomplishments
• Testing
• Acknowledge
• Reference

# include "maincatalog.h"
# include "util.h"
# include "db.h"

#ifndef BROWSER_H
#define BROWSER_H

#define WORKINGDIR "/afs/cs.wisc.edu/u/grad/dmw/cs784/proj"

// Browser class only exists as an instance of a utility operation
class Browser {

 private:
 // internal bookkeeping
 // char DBname[MAXLENGTH];
 // char RELname[MAXLENGTH];
 // char ATTRname[MAXLENGTH];

 // some state info.
 Error   error;
 DB*     OpenedDB ;
 RelCatalog* OpenedRelCat ;
 AttrCatalog* OpenedAttrCat ;
 IndexCatalog* OpenedIndexCat ;

 public:
 // Open DB, RelCat, and Attr Cat
 Browser();

 // clean up all opened stuffs, if any
 ~Browser();

 // return list of databases available
 Status GetDBList(char* dblist);

 // return list of relations in the opened db
 Status GetDBInfo(char* dbname, char** rellist, int &dbcnt, int MAXCOUNT);

 // return list of attr. in the opened relation
 Status GetRELInfo(char* attrname, char** attrlist, int &relcnt, int MAXCOUNT);

 // return specific info on an attr.
 Status GetATTRInfo(char* relname, char* attrname,int &cnt,IndexType *indexrec);

 // prints record in an opened relation
 Status Print();

 // return pointer to current DB, relations, attributes, respectively
 DB* CurrentDB() { return OpenedDB;}
 RelCatalog* CurrentREL() { return OpenedRelCat;}
 AttrCatalog* CurrentATTR() { return OpenedAttrCat; }
 IndexCatalog* CurrentINDEX() { return OpenedIndexCat;}

 Status ResetStates();
};
#endif BROWSER_H

#include "tclExtend.h"
#include "catalog.h"
#include "util.h"
#include "browser.h"
#include "db.h"
#include "error.h"

#ifndef GUI_H
#define GUI_H

// initialize browser
int
Init_Browser(ClientData  clientdata, Tcl_Interp *interp,int argc,char* argv[]);

// clean up browser
int
Close_Browser(ClientData  clientdata, Tcl_Interp *interp,int argc,char* argv[]);

// set of tclcreate_cmd extensions to tcl
int MR_CreateCmd(Tcl_Interp* interp) ;

// calling misc functions to init GUI
int Init_GUI(Tcl_Interp* interp) ;

// init all managers
Status Init_Minirel();

// open the db
int DBopen(ClientData  clientdata, Tcl_Interp *interp, int argc,char* argv[]);

// close the db
int DBclose(ClientData  clientdata, Tcl_Interp *interp, int argc,char* argv[]);

int ExecuteQuery(ClientData  clientdata, Tcl_Interp *interp,
int argc,char* argv[]);

int getRELinfo(ClientData  clientdata, Tcl_Interp *interp,
int argc,char* argv[]);

int getDBinfo(ClientData  clientdata, Tcl_Interp *interp,
int argc,char* argv[]);

int getATTRinfo(ClientData  clientdata, Tcl_Interp *interp,
int argc,char* argv[]);

// get relation info without browser
int QRELinfo(ClientData  clientdata, Tcl_Interp *interp,int argc,char* argv[]);

// define some global variables
#define GLOBAL_DB       db
#define GLOBAL_ERROR    error
#define GLOBAL_RELCAT   relCat
#define GLOBAL_ATTRCAT  attrCat
#define GLOBAL_INDEXCAT indCat

#endif GUI_H

		# initialize the query editor
		Init_QueryEditor {}

		# initialize the condition box
		Init_ConditionBox {}

		# initialize the relation tables
		Init_Tables {}

		# translate the entered QBE queries into SQL and execute the query
		ProcessQueries {}

		# translate the entered QBE queries into SQL and display the query
		ReloadQueries {}

0) Read the command column to check for P., if found, it is a special case to project all attributes in a relation table, format the entry as if a P. is placed at every column

1) Read the command column to check for I. or D., if found, call corresponding GetInsertEntryCmd/GetDeleteEntryCmd, and send the result to the base

2) If there is no info.in command column, read in all the available attribute column entries pack them in the form of  pair for each entry, empty ones have ; 

3) check for U. in the list of  pairs, 
	if found, call correspond GetUpdateEntryCmd, send result to base, 
	If not found, just pack the entry info with command UNKNOWN. to the base, and let it decide

1) Request stage:

		The base gathers entry information from all opened relation table by sending each active table a send data request, as described above.

2) Receive stage:

		The base arranges the received information by placing the ones with commands to the beginning of the list.  As a result, entry lists with UNKNOWN. as commands are placed at the end. This is needed because entries list with command UNKNOWN. do not  contain commands, These entries only help in forming the queries. The stage ends when all local parsers have responded with their respectively entry info. 

3) Parse stage:

		After collecting all the commands from all opened relation tables, the base processes the command list by checking if there is incompatible commands , then determine the command to be performed and invokes the corresponding ProcessXXXCmd routine with the entry lists gathered.

4) Translate stage:

	Depending on the query command, this lengthy stage can be very different, let's examine the processing of DML queries in detail. Notice that in case that other query command is found, the corresponding GetXXXEntryCmd will be invoked instead.

	This routine begins by checking if the DML requires an union.  This can be determined by checking if command P. is found at more than one row in a relation table.  If so, the answer is yes, no otherwise.

If a union is not required, then it proceeds through the following 	steps:
	1) Do the variable substitutions,
	2) Process any negation commands,
	3) Extract projection attributes,
	4) Extract selection constrains,
	5) Extract condition box entries,
	6) Extract aliases of relation used for negation and projection,
	7) Perform string manipulation to put the information together to form a valid SQL statement

	The following is a summary of the features that current implementation of the parser support/not support:

	Supported features
	1)	P. with any combination of constants, variables, unions, negation, using unnamed columns,and/or condition box entries.	
	2)	I.D.U. multi-statement, constants and/or variables, limited form of subquery, as mentioned above.
	3)	G., group by clause, a sample implementation for a simple extension of the parser to handle aggregate commands and qualifiers.
	4)	limited error checking

	Not supported features:
	1) aggregate functions - i.e. SUM. AVE. MIN. MAX. CNT.
	2) qualifiers - i.e. UN. ALL. AO. DO.
	3) union and negation in subqueries of insert, delete, and update queries
	4) queries that require nested select's
	5) total error detection

	Comments
		Before waving our hands to these neglected/incomplete features in QBE, let us constructively suggest how these features can be extended into the current implementation of the parser.

	1) aggregate functions -  can extend the parser by adding a preprocessing stage to replace these key words with corresponding SQL keywords and put a bracket enclosing the next item in the entry

	2) qualifiers - can extend the parser by setting various flags in the projection processing routines to generate an additional keyword in the SQL statement, since basically quantifiers are simply additional keywords in the SQL statements at a predefined location
		
	3) union and negation in insert, delete, and update subqueries - require  some modification of structure as mentioned in the section above
				
	4) nested select's -  we are not aware of any valid QBE queries that require nested select's in corresponding SQL statements yet, but we are not ready to disprove it either

	5) total error detection - it basically requires ad-hoc ways to check every entry and then conflicting entries.  Additionally, each entry input must be processed.  Due to time constrain, this feature is incomplete. This is also not the main purpose of the project.  We will leave this to future work section, if desired.

-Introduction to Database System - QBE and QBF
-Introduction to Tcl/Tk
-QBE manual, IBM QMS Reference
-Jim Melton and Alan R. Simon, Understanding the new SQL
-PESTO, the GUI for Garlic

Appendix

	%Utilities command references
	- dbcreate [database name]
	- dbdelete [database name]
	- relcreate [database name] [relation name] [attribute datatype size] ...
		datatype = string, int, or real
	- reldelete [database name] [relation name]
	- indexcreate [database name] [relation name] [attribute indextype size]..
		indextype = hash or b_tree
	- recinsert [database name] [relation name] [attribute value] ...
	- recdelete [database name] [relation name] [attribute value]
	- bulkload [database name] [relation name] [file name]

	%Format of 
	attribute = (relation name(N)).(attribute name)  N = row#
	value = raw entry in the corresponding box

	%Format of :
	- P., or {} found:
		[cmd, [ [attribute, values] ] ]
			cmd = P. or UNKNOWN.
	- I., D., or U. found
		[insert, list of [insertcmd,list of [attribute values] pairs]
	insertcmd =  insertc, or insertv 
	deletecmd =  deletec, or deletev 
	updatecmd =  updatec, or updatev 

	%Outline of GetXXXEntryCmd [ XXX denotes command found ]
	
	- GetInsertEntryCmd

	Read the entries row by row
	
	Determine the type of insert by scanning each row to see if there is any variable involved:

	1) If not: tagged insertc to the data list, send to base
	2) If yes, tagged insertv to the data list, send to base

	The result of each row is appended together and sent to the base
	
	- GetDeleteEntryCmd

	Determine the type of delete by scanning each row to see if there is any variable involved:

	1) If not: tagged deletec to the data list, send to base
	2) If yes, tagged deletev to the data list, send to base

	The result of each row is appended together and sent to the base
	
	- GetUpdateEntryCmd

	Similar concept to GetInsertEntryCmd and GetDeleteEntryCmd, except that it must identify the attribute to be updated, and determine the type of update by scanning each row to see if there is any variable involved:

	1) If not: tagged updatec to the data list, send to base
	2) If yes, tagged updatev to the data list, send to base

	The result of each row is appended together and sent to the base

	%Outline of ProcessXXXCmd ( XXX denotes the command found )
	
	- ProcessInsertCmd

	From the local parser, the base obtains a list of insert queries, tagged with insertc or insertv command, therefore, for each insert query:
	1) If tagged with insertc, invoke ProcessInsertConstantCmd
	2) If tagged with insertv, invoke ProcessInsertVariableCmd

	ProcessInsertConstantCmd
	This module handles with inserts that do not require subquery, given the entry lists
	1) Extract all constants
	2) Extract all attributes
	3) Extract name of the relation to do insertion
	4) Perform string manipulation to put the information together to form a valid SQL insertion query

	ProcessInsertVariableCmd
	Sometimes insert commands require subqueries to allow users to combine projection and selection query and insert commands into one step. Local parser will conclude that insertion requires a subquery as soon as it finds a variable in the row where a insert command, I., is found. The module is basically a combination of ProcessProjCmd and ProcessInsertConstantCmd, except that for simplicity, no union nor negation is supported in the subquery part ( it should be a very easy modification of this module to incorporate the union and negation, and it will be done if time permits)

	1) Extract update attributes	
	2) Variable substitution
	3) Subquery generation following the case of projection
	4) Repeat the 4 steps in the case that only constants are used

	- ProcessDeleteCmd/ProcessUpdateCmd

	Formation of delete and update queries, conceptually, are very similar.  

	1)	Specified constrains are first extracted
	2)	Formation of a subquery in case variables are found
	3)	Eliminate the aliasing of relations,
	4)	Put the pieces together

	Essentially there are only differences in command names used, i.e. deletec and deletev, instead of updatec and updatev, and the syntax of the SQL statement. Interested readers are advised to compare the section of delete modules with update modules for understanding the differences.