BDE2SQL Project

Join Loop Macro

User's Manual

Version 1.0

Course: 91.523 - Software Engineering I
Semester: Fall '96
Instructor: R. Lechner
Date: December 10,1996

Team: bde2sql

Contents: User's Manual

1. Introduction
2. Basic Notion
3. Binary Join Loop Macro

4. Join Ternary Loop Macro

5. References

1. Introduction

The Join operation is one of the essential operations of relational Algebra. It is a binary operation that allows the user to compose two relations in a generalized way. The Join is one of the most difficult operations to implement efficiently in relational DBMS.
The version 1.0 of these Join Loop macros were created by the 96f523/bde2sql team (December 12, 1996) as a goal to extend the Chgen CASE tool in order to provide the capability of doing join of tables.
This first version contains a description of the join_2_loop macro which allows the user to perform matching between two tables, and the description of the join_3_loop macro to make join operations between three tables. Both using the navigational capabilities of a pr_load VMNetDB, assuming pre-ordered lists of tuples of tables-rows.

2. Basic Notions

Databases serve many applications and thus should be application-neutral. The maintenance task is shifted to a DBMS, which makes available application-specific views of the database. In a database environment, there is a separation between database functions performed by the DBMS and application functions.

Some of the many advantages to database functions being independent of applications are:

Some of the basic operations that can be performed over a database are:

RESTRICTION

PROJECTION

PRODUCT

UNION

DIFFERENCE

ASSIGNMENT

These basic operations are useful to design derived operations such as join, intersection, or division, which are useful and frequently used in applications, so instead of having the user design them it is convenient that the DBMS supports them directly.

Only an explanation of the join operation will be provided since it is the principal objective of this project.

Join is the most important derivation function and it involves the joining of tables if they have a domain in common. The result of a join operation is a wider table in which each row is formed by joining together two rows, one from each of the original tables, such that the two rows concerned have the same value in the common domain. There are several types of joining operations:

The most useful being the natural join. Natural join is a nesting of product, restriction and projection, yielding a result that has:

Semi-join is a special case of natural join in which the join is projected on the columns of only one of the tables being joined.

Equi-join matches values using the = operator. Natural join is a special case of this join.

Theta-join is a more general case since it compares values using not only the = operator but also the <=, <, >, <= operators.

3. Binary Join Loop Macro

3.1. Description

The principal objective of this project is to design a binary join macro: join_2_loop between two tables that have a domain in common. This domain can be seen as a foreign key or attribute. The join_2_loop macro will transverse both tables pointing to those rows which match in the fields that belong to the common domain. It is the application which will produce a new table in which each row is formed by the joining together of the two rows, one from each of the original tables, selecting only the fields chosen by the user.

BINARY JOIN LOOP Diagram Example

         
                            ________________
                           |                |
                          ----------------  |
                         |                | |
                         |  Parent Table  |_|
                         |                |
                          ---------------- 
                            /   Table Id [ptt1]    
                           /      attr  1      
                          /       attr  2    
                         /         ....    
                        \/          ....    
          ________________        attr  n
         |                |       
        ----------------  |        
       |                | |        
       |  Child Table   |_|        
       |                |          
        ----------------           
    Table Id [ptt1]               
      attr  1                     
      attr  2                     
       ....                       
       ....                       
      attr  m                     
                            ________________ 
                           |                |
                          ----------------  |
                         |                | |
                         |    Join Table  |_|
                         |                | 
                          ---------------- 
                             Table Id
                               Fkey Table 1
                               Fkey Table 2
                                  attr  1    
                                  attr  2    
                                   ....   
                                   ....   
                                  attr  p

3.2. Pseudocode

To implement the join loop it is required to have access to the following:


   Parent table                                    
   Child table                                     
   Common Domain in both Parent and Child Tables   


   - table_loop to transverse the parent table
        - table_loop to transverse the child table 
             - If the parent->field matches the child->field the variables:

   Note:
     pcurr and ccurr will be pointing to the rows in the
     corresponding table that satisfy the matching.

3.3 Name Conventions Used.
The name convention used to denote the parameters of the join_2_loop macro. and can be adopted for all Chgen generated macros are:

     p      = parent,
     c      = child,
     cfield = field in child table
     pfield = field in parent table

3.4 Definition of the join_2_loop Macro

#define join_2_loop(viewname, p, c, pfield, cfield, fcnt_cmp) \
table_loop(viewname, p) \
table_loop(viewname, c) \
if(fcnt_cmp(&p##curr->pfield, &c##curr->cfield) == 0)

3.5 Specifications for the join_2_loop Macro

a) Requires

Parameters:

b) Ensures.

c) Alters.

When using the macro join_2_loop in the application of the product of two sparse matrices it is necessary to call the macro twice since three tables need to be joined. These tables are RO, CO and EL which contain the row, column and element information respectively. The call of the macro would look as follows:

First Call:

join_2_loop(view_name, RO, EL, ROid, ROid, key_compare)

{
/* application selects the fields to be included in join table: JA */
/* for example: */

     
     join_2_loop(view_name, RO, EL, ROid, ROid, key_compare)
       {
	 if(key_compare(&ROcurr->MAid, MAcurr) == 0)
	   {
	     JA_elt = pr_create(JA);
	  
	     pr_set_key(JA_elt, MAid,   ROcurr->MAid);
	     pr_set_key(JA_elt, ROid,   ROcurr->ROid);
	     pr_set_int(JA_elt, rowndx, ROcurr->rowndx); 
	     pr_set_key(JA_elt, ELid,   ELcurr->ELid);
	     pr_set_key(JA_elt, COid,   ELcurr->COid);
	     pr_set_int(JA_elt, evalue, ELcurr->evalue); 
	  
	     pr_add(view_name,JA,JA_elt);
	   }
       }
     join_2_loop(view_name, JA, CO, COid, COid, key_compare)
       {
	 pr_set_key(JAcurr, COid,   COcurr->COid);
	 pr_set_int(JAcurr, colndx, COcurr->colndx); 
       }
   }

Second Call:

join_2_loop(view_name, CO, JA, COid, COid, key_compare)

{
/* application selects the fields to be included in join table: JB */
/* for example: */

     
     join_2_loop(view_name, CO, EL, COid, COid, key_compare)
       {
	 if(key_compare(&COcurr->MAid, MAcurr) == 0)
	   {
	     JB_elt = pr_create(JB);
	  
	     pr_set_key(JB_elt, MAid,   COcurr->MAid);
	     pr_set_key(JB_elt, COid,   COcurr->COid);
	     pr_set_int(JB_elt, colndx, COcurr->colndx); 
	     pr_set_key(JB_elt, ELid,   ELcurr->ELid);
	     pr_set_key(JB_elt, ROid,   ELcurr->ROid);
	     pr_set_int(JB_elt, evalue, ELcurr->evalue); 
	     
	     pr_add(view_name,JB,JB_elt);
	   }
       }
     join_2_loop(view_name, JB, RO, ROid, ROid, key_compare)
       {
	 pr_set_key(JBcurr, ROid,   ROcurr->ROid);
	 pr_set_int(JBcurr, rowndx, ROcurr->rowndx); 
       }
   }

3.6 Example of an application

3.6.1 Input Files

Original data of the following matrices:


              1  2  3        10  40
              4  5  6        20  50
                             30  60

Data File:


	MA010001 MATRIX_A   10  10
	MA010002 MATRIX_B   10  10
	RO010001 MA010001  1
	RO010002 MA010001  2 
	RO010003 MA010002  1
	RO010004 MA010002  2
	RO010005 MA010002  3
	CO010001 MA010001  1
	CO010002 MA010001  2
	CO010003 MA010001  3
	CO010004 MA010002  1
	CO010005 MA010002  2
	EL010001 RO010001 CO010001 1  
	EL010002 RO010001 CO010002 2 
	EL010003 RO010001 CO010003 3 
	EL010004 RO010002 CO010001 4 
	EL010005 RO010002 CO010002 5 
	EL010006 RO010002 CO010003 6 
	EL010007 RO010003 CO010004 10
	EL010008 RO010003 CO010005 20
	EL010009 RO010004 CO010004 30
	EL010010 RO010004 CO010005 40 
	EL010011 RO010005 CO010004 50
	EL010012 RO010005 CO010005 60

3.6.2 Source code of the Application

The following is the application program implementing the joinloop macro.

/*-----------------------------------------------------------------------*/
/* University of Massachusetts Lowell                                    */
/* Department of Computer Science                                        */
/*                                                                       */    
/*                                                                       */ 
/* File   :  newmatrixtest.c                                             */
/* Summary:  This file uses the files generated by chgen                 */
/*-----------------------------------------------------------------------*/

#define MAIN
#include 
#include "matrix.h"



struct MA *MA_elt;
struct RO *RO_elt;
struct CO *CO_elt;
struct JA *JA_elt;
struct JB *JB_elt;

void InitSystem        (char *, char *);
void LoadDatabase      (char *, char *);
void PrintMatrices     (char *);
void MultiplyMatrices2 (char *, char *, char *, char *);
void GetDimensions     (char *, char *, int *, int *);
void AddMatrix         (char *, char *, int, int);
void AddRow            (char *, char *, int);
void AddColumn         (char *, char *, int);
void AddElement        (char *, char *, int, int, int);
void JoinLoop2_MA      (char *, char *);
void JoinLoop2_MB      (char *, char *);
void FirstElmtJA       (char *, char *);
void FirstElmtJB       (char *, char *);
void AdvJAcurr         (struct JA *);
void AdvJBcurr         (struct JB *);




void main (int arc, char *argv[])
{
     char* view_name;

     InitSystem("matrix.viewdefs","matrix2.dat");
     LoadDatabase("Matrices","matrix2.dat");
     PrintMatrices("Matrices");
     printf(" \n");    
     JoinLoop2_MA("Matrices", "MATRIX_A");
     JoinLoop2_MB("Matrices", "MATRIX_B");
     pr_dump("Matrices","matrix2a.dat",1,"w");
     MultiplyMatrices2("Matrices","MATRIX_A","MATRIX_B","MATRIX_C");
     pr_dump("NewMatrices","matrix2b.dat",1,"w");
     PrintMatrices("Matrices");  
     printf("==== T H E      E N D ====\n");
} /* main */

void InitSystem(view_defs, filename)
     char *view_defs, *filename;
{
     printf("Initialization:\n");
     printf("---------------\n");
     pr_init(view_defs, filename);
} /* InitSystem */

void LoadDatabase(view_name,filename)
     char *view_name, *filename;
{
     printf("Load existing Database: %s\n",filename);
     pr_load(view_name,filename);
     printf("Finished loading existing database: %s\n\n",filename);
} /* LoadDatabase */

void PrintMatrices(view_name)
     char *view_name;
{
     table_loop(view_name, MA)
       {
	 printf("\n\nMatrix: %s BY ROWS\n", MAcurr->mname);
	 child_loop(MA, RO, ROid, MAid)
	   {
	     child_loop(RO, EL, ELid, ROid)
	       {
		 printf("ROW index: %d   ", ROcurr->rowndx);
		 printf("ELEMENT value: %d\n", ELcurr->evalue);
	       }
	   }
	 
	 printf("\n\nMatrix: %s BY COLUMNS\n", MAcurr->mname);
	 child_loop(MA, CO, COid, MAid)
	   {
	     child_loop(CO, EL, ELid, COid)
	       {
		 printf("CO index: %d   ", COcurr->colndx);
		 printf("ELEMENT value: %d\n", ELcurr->evalue);
	       }
	   }
       }
     printf("\n");
} /* PrintMatrices */

void JoinLoop2_MA(view_name, filename)
     char *view_name, *filename;
{
     find_str_loop(view_name, MA, mname, filename)
       {
	 break;
       }
     
     join_2_loop(view_name, RO, EL, ROid, ROid, key_compare)
       {
	 if(key_compare(&ROcurr->MAid, MAcurr) == 0)
	   {
	     JA_elt = pr_create(JA);
	  
	     pr_set_key(JA_elt, MAid,   ROcurr->MAid);
	     pr_set_key(JA_elt, ROid,   ROcurr->ROid);
	     pr_set_int(JA_elt, rowndx, ROcurr->rowndx); 
	     pr_set_key(JA_elt, ELid,   ELcurr->ELid);
	     pr_set_key(JA_elt, COid,   ELcurr->COid);
	     pr_set_int(JA_elt, evalue, ELcurr->evalue); 
	  
	     pr_add(view_name,JA,JA_elt);
	   }
       }
     join_2_loop(view_name, JA, CO, COid, COid, key_compare)
       {
	 pr_set_key(JAcurr, COid,   COcurr->COid);
	 pr_set_int(JAcurr, colndx, COcurr->colndx); 
       }
} /* JoinLoop2_MA */

void JoinLoop2_MB(view_name, filename)
     char *view_name, *filename;
{      
     find_str_loop(view_name, MA, mname, filename)
       {
	 break;
       }
     
     join_2_loop(view_name, CO, EL, COid, COid, key_compare)
       {
	 if(key_compare(&COcurr->MAid, MAcurr) == 0)
	   {
	     JB_elt = pr_create(JB);
	  
	     pr_set_key(JB_elt, MAid,   COcurr->MAid);
	     pr_set_key(JB_elt, COid,   COcurr->COid);
	     pr_set_int(JB_elt, colndx, COcurr->colndx); 
	     pr_set_key(JB_elt, ELid,   ELcurr->ELid);
	     pr_set_key(JB_elt, ROid,   ELcurr->ROid);
	     pr_set_int(JB_elt, evalue, ELcurr->evalue); 
	     
	     pr_add(view_name,JB,JB_elt);
	   }
       }
     join_2_loop(view_name, JB, RO, ROid, ROid, key_compare)
       {
	 pr_set_key(JBcurr, ROid,   ROcurr->ROid);
	 pr_set_int(JBcurr, rowndx, ROcurr->rowndx); 
       }
} /* JoinLoop2_MB */

void GetDimensions( view_name, matrix_name, nrow, ncol )
     char *view_name, *matrix_name;
     int  *nrow, *ncol;
{
     table_loop(view_name, MA)
       {
	 if ( !strcmp (matrix_name, MAcurr->mname) )
	   {
	     *nrow = MAcurr->rowdim;
	     *ncol = MAcurr->coldim;
	     return;
	   }
       }
} /* GetDimensions */

void AddMatrix (view_name, matrix_name, nrow, ncol)
     char *view_name, *matrix_name;
     int  nrow, ncol;
{     
     MA_elt = pr_create(MA);
	 
     pr_set_str ( MA_elt, mname, matrix_name);
     pr_set_int ( MA_elt, rowdim, nrow);
     pr_set_int ( MA_elt, coldim, ncol);
     pr_add ( view_name, MA, MA_elt );
       } /* AddMatrix */

void AddRow (view_name, matrix_name, nrow )
     char *view_name, *matrix_name;
     int  nrow;
{    
     RO_elt = pr_create(RO);

     pr_set_key ( RO_elt, MAid, pr_get_key(MA_elt, MAid) );
     pr_set_int ( RO_elt, rowndx, nrow ); 
     pr_add ( view_name, RO, RO_elt );
} /* AddRow */

void AddColumn (view_name, matrix_name, ncol )
     char *view_name, *matrix_name;
     int  ncol;
{    
     CO_elt = pr_create(CO);

     pr_set_key ( CO_elt, MAid, pr_get_key(MA_elt, MAid) );
     pr_set_int ( CO_elt, colndx, ncol ); 
     pr_add ( view_name, CO, CO_elt );
} /* AddColumn */

void AddElement(view_name, matrix_name, nrow, ncol, element)
     char *view_name, *matrix_name;
     int  nrow, ncol, element;
{
     struct EL *EL_elt = pr_create(EL);

     pr_set_key (EL_elt, ROid, pr_get_key(RO_elt, ROid));
     pr_set_key (EL_elt, COid, pr_get_key(CO_elt, COid));
     pr_set_int (EL_elt, evalue, element);
/*
     pr_set_int (EL_elt, rowidx, nrow);
     pr_set_int (EL_elt, colidx, ncol);
*/
     pr_add( view_name, EL, EL_elt);
} /* AddElement */

void MultiplyMatrices2(view_name, matrix1, matrix2, matrix3)
     char *view_name, *matrix1, *matrix2, *matrix3; 
{
     int n, m, p, q, prod, s;
     struct JA *JAinit, *JAprev;
     struct JB *JBinit, *JBprev;

     GetDimensions(view_name, matrix1, &n,&p);
     GetDimensions(view_name, matrix2, &q,&m);

     if ( n==0 || m==0 || p==0 || q==0 || p!=q )
       {
          printf("Error: Can'not multiply %s(%d,%d) by %s(%d,%d)",
                  matrix1, n, p, matrix2, q, m);
          return;
       }

     AddMatrix(view_name, matrix3, n, m);

     FirstElmtJA(view_name, matrix1);
     FirstElmtJB(view_name, matrix2);

     JAinit = JAcurr;
     JBinit = JBcurr;

     prod = 0;

     while(JAcurr != NULL) /*  begin row file */  
       { /* new row */
	 JAprev = JAcurr; 
	 JBcurr = JBinit;

	 while(JBcurr != NULL) /* begin column file */
	   { /* new column */
	     JAcurr = JAprev;
	     JBprev = JBcurr;

	     while((JBcurr != NULL) &&                   /* not eof cols */
		   (JAcurr != NULL) &&                   /* not eof rows */
		   (JBcurr->colndx == JBprev->colndx) && /* same col? */
		   (JAcurr->rowndx == JAprev->rowndx))   /* same row? */
	       { /* same column */
		 /* check if there is a match */
		 if(JAcurr->colndx == JBcurr->rowndx)
		   {
		     prod  += JAcurr->evalue * JBcurr->evalue;
		     AdvJAcurr(JAcurr);  
		     AdvJBcurr(JBcurr);
		     s = 0;
		   }
		 else
		   {
		     s = 1;
		     if(JAcurr->colndx > JBcurr->rowndx)
		       { 			 
			 AdvJBcurr(JBcurr);		 
		       }
		     else
		       {
			 AdvJAcurr(JAcurr);  
		       }
		   }
	       } /* while */

	     if(prod != 0 )
	       {
		 /* add new row, col, evalue */
		 AddRow    (view_name, matrix3, JAprev->rowndx);
		 AddColumn (view_name, matrix3, JBprev->colndx);
		 AddElement(view_name, matrix3, JAprev->rowndx,
			    JBprev->colndx, prod);
		 prod = 0;
	       }

	     if(JAcurr == NULL)
	       { /* at eof of rows */
		 if(JBcurr == NULL)
		   { /* at eof of cols */
		     break;
		   }
		 else
		   { /* not at end of cols */
		     if((JBcurr->next_ptr == NULL) && (s == 0))
		       {/* already at end of col */
			 JBcurr = NULL; 
			 break;
		       }

		     if(JBcurr->colndx != JBprev->colndx)
		       { /* already in new column */
			 /* break; */ 
		       }
		     else
		       { /* advance to next column */
			 while((JBcurr->colndx == JBprev->colndx) && 
			       (JBcurr->next_ptr != NULL))
			   {
			     AdvJBcurr(JBcurr);  
			   } 
		       }
		   }
	       }
	     else
	       { /* not at eof of rows */
		 if(JBcurr == NULL)
		   { /* at eof of cols */
		     while((JAcurr->rowndx == JAprev->rowndx) && 
			   (JAcurr->next_ptr != NULL))
		       {
			 AdvJAcurr(JAcurr);  
		       } 
		     break;
		   }
		 else
		   { /* not at eof of cols */
		     if((JBcurr->next_ptr == NULL) && (s == 1))
		       {/* already at end of col */
			 JBcurr = NULL; 
			 break;
		       }
		     if(JBcurr->colndx != JBprev->colndx)
		       { /* already in new column */
			 /* don't do anything */
		       }
		     else
		       { /* advance to next column */
			 while((JBcurr->colndx == JBprev->colndx) && 
			       (JBcurr->next_ptr != NULL))
			   {
			     AdvJBcurr(JBcurr);  
			   } 
		       }
		   }
	       }
	   }/* end col file */
       } /* end row file */
} /* MultiplyMatrices2 */

void FirstElmtJA(view_name, filename)
     char *view_name, *filename;
{
     find_str_loop(view_name, MA, mname, filename)
       {
	 break;
       }

     find_key_loop(view_name, JA, MAid, MAcurr->MAid)
       {
	 break;
       }
} /* FirstElmtJA */

void FirstElmtJB(view_name, filename)
     char *view_name, *filename;
{
     find_str_loop(view_name, MA, mname, filename)
       {
	 break;
       }

     find_key_loop(view_name, JB, MAid, MAcurr->MAid)
       {
	 break;
       }
} /* FirstElmtJB */

void AdvJAcurr(JAc)
     struct JA *JAc;
{
     JAcurr = JAcurr->next_ptr; /* next elmt in row */
} /* AdvJAcurr */

void AdvJBcurr(JBc)
     struct JB *JBc;
{
     JBcurr = JBcurr->next_ptr; /* next elmt in col */
} /* AdvJBcurr */

3.6.3 Output Files

Tables after call to join:
JA and JB are the tables generated by the applicaton program using the the join loop macro. It should be noted that when there was no matching between the involved tables, a new row in the join table was not created.

It should be noted that the rows inserted in the tables as result of the join loop and of the matrix product are shown in bold italics


	 MA010001 MATRIX_A       10       10
	 MA010002 MATRIX_B       10       10
	 RO010001 MA010001        1
	 RO010002 MA010001        2
	 RO010003 MA010002        1
	 RO010004 MA010002        2
	 RO010005 MA010002        3
	 CO010001 MA010001        1
	 CO010002 MA010001        2
	 CO010003 MA010001        3
	 CO010004 MA010002        1
	 CO010005 MA010002        2
	 EL010001 RO010001 CO010001        1
	 EL010002 RO010001 CO010002        2
	 EL010003 RO010001 CO010003        3
	 EL010004 RO010002 CO010001        4
	 EL010005 RO010002 CO010002        5
	 EL010006 RO010002 CO010003        6
	 EL010007 RO010003 CO010004       10
	 EL010008 RO010003 CO010005       20
	 EL010009 RO010004 CO010004       30
	 EL010010 RO010004 CO010005       40
	 EL010011 RO010005 CO010004       50
	 EL010012 RO010005 CO010005       60
	 JA000001 MA010001        1        1        1
	 JA000002 MA010001        1        2        2
	 JA000003 MA010001        1        3        3
	 JA000004 MA010001        2        1        4
	 JA000005 MA010001        2        2        5
	 JA000006 MA010001        2        3        6
	 JB000007 MA010002        1        1       10
	 JB000008 MA010002        2        1       30
	 JB000009 MA010002        3        1       50
	 JB000010 MA010002        1        2       20
	 JB000011 MA010002        2        2       40
	 JB000012 MA010002        3        2       60

Tables after computing the product of the matrices:


	 MA010001 MATRIX_A       10       10
	 MA010002 MATRIX_B       10       10
	 MA010003 MATRIX_C       10       10 
	 RO010001 MA010001        1
	 RO010002 MA010001        2
	 RO010003 MA010002        1
	 RO010004 MA010002        2
	 RO010005 MA010002        3
	 RO010006 MA010003        1
	 RO010007 MA010003        1
	 RO010008 MA010003        2
	 RO010009 MA010003        2 
	 CO010001 MA010001        1
	 CO010002 MA010001        2
	 CO010003 MA010001        3
	 CO010004 MA010002        1
	 CO010005 MA010002        2
	 CO010006 MA010003        1
	 CO010007 MA010003        2
	 CO010008 MA010003        1
	 CO010009 MA010003        2 
	 EL010001 RO010001 CO010001        1
	 EL010002 RO010001 CO010002        2
	 EL010003 RO010001 CO010003        3
	 EL010004 RO010002 CO010001        4
	 EL010005 RO010002 CO010002        5
	 EL010006 RO010002 CO010003        6
	 EL010007 RO010003 CO010004       10
	 EL010008 RO010003 CO010005       20
	 EL010009 RO010004 CO010004       30
	 EL010010 RO010004 CO010005       40
	 EL010011 RO010005 CO010004       50
	 EL010012 RO010005 CO010005       60
	 EL010013 RO010006 CO010006      220
	 EL010014 RO010007 CO010007      280
	 EL010015 RO010008 CO010008      490
	 EL010016 RO010009 CO010009      640 
	 JA000001 MA010001 EL010001 RO010001 CO010001        1        1        1
	 JA000002 MA010001 EL010002 RO010001 CO010002        1        2        2
	 JA000003 MA010001 EL010003 RO010001 CO010003        1        3        3
	 JA000004 MA010001 EL010004 RO010002 CO010001        2        1        4
	 JA000005 MA010001 EL010005 RO010002 CO010002        2        2        5
	 JA000006 MA010001 EL010006 RO010002 CO010003        2        3        6
	 JB000001 MA010002 EL010007 RO010003 CO010004        1        1       10
	 JB000002 MA010002 EL010009 RO010004 CO010004        2        1       30
	 JB000003 MA010002 EL010011 RO010005 CO010004        3        1       50
	 JB000004 MA010002 EL010008 RO010003 CO010005        1        2       20
	 JB000005 MA010002 EL010010 RO010004 CO010005        2        2       40
	 JB000006 MA010002 EL010012 RO010005 CO010005        3        2       60

This output can logically be viewed as follows:


Matrix: MATRIX_A

                  0   1   2   3   4   5   6   7   8   9
               ------------------------------------------
             0 |  0   0   0   0   0   0   0   0   0   0 |
             1 |  0   1   2   3   0   0   0   0   0   0 |
             2 |  0   4   5   6   0   0   0   0   0   0 |
             3 |  0   0   0   0   0   0   0   0   0   0 |
             4 |  0   0   0   0   0   0   0   0   0   0 |
             5 |  0   0   0   0   0   0   0   0   0   0 |
             6 |  0   0   0   0   0   0   0   0   0   0 |
             7 |  0   0   0   0   0   0   0   0   0   0 |
             8 |  0   0   0   0   0   0   0   0   0   0 |
             9 |  0   0   0   0   0   0   0   0   0   0 |
               ------------------------------------------


Matrix: MATRIX_B

                  0   1   2   3   4   5   6   7   8   9
               ------------------------------------------
             0 |  0   0   0   0   0   0   0   0   0   0 |
             1 |  0  10  20   0   0   0   0   0   0   0 |
             2 |  0  30  40   0   0   0   0   0   0   0 |
             3 |  0  50  60   0   0   0   0   0   0   0 |
             4 |  0   0   0   0   0   0   0   0   0   0 |
             5 |  0   0   0   0   0   0   0   0   0   0 |
             6 |  0   0   0   0   0   0   0   0   0   0 |
             7 |  0   0   0   0   0   0   0   0   0   0 |
             8 |  0   0   0   0   0   0   0   0   0   0 |
             9 |  0   0   0   0   0   0   0   0   0   0 |
               ------------------------------------------


Matrix: MATRIX_C

                  0   1   2   3   4   5   6   7   8   9
               ------------------------------------------
             0 |  0   0   0   0   0   0   0   0   0   0 |
             1 |  0 220 280   0   0   0   0   0   0   0 |
             2 |  0 490 640   0   0   0   0   0   0   0 |
             3 |  0   0   0   0   0   0   0   0   0   0 |
             4 |  0   0   0   0   0   0   0   0   0   0 |
             5 |  0   0   0   0   0   0   0   0   0   0 |
             6 |  0   0   0   0   0   0   0   0   0   0 |
             7 |  0   0   0   0   0   0   0   0   0   0 |
             8 |  0   0   0   0   0   0   0   0   0   0 |
             9 |  0   0   0   0   0   0   0   0   0   0 |
               ------------------------------------------

4. Ternary Join Loop Macro

In addition to the join loop macro defined before, it is convenient in some situations to make join operations between three tables, using the navigational capabilities of a pr_loaded VMNetDB, assuming pre-ordered list of tuples of table-rows. Thus, a new macro, called join_3_loop, is defined, which hides the details of sequencing through ordered lists and matching the join fields.

4.1. Description.
The join_3_loop macro is defined as a concurrent pair of child-loops over two child-sets. The child tables contains respective fields, by which the both tables are sorted, and whose equality is the join criterion.

The macro advances the pointers correctly when the join criterion is not satisfied, and ends when one or both of the child tables have been traversed completely. The following diagram shows a possible table configuration where the join_3_loop macro is applicable.


              ---------            ----------
              | ptt1  |            | ptt2   |
              |       |            |        |
              ---------            ----------
                      \            /
                       \          /
                       \/        \/
                       ------------
                       |ctt1/ctt2 |
                       |..........|
                       |  f1/f2   |
                       ------------

4.2. Pseudocode.

   - "Initialize JOINMATCH (integer flag to indicate matching) to zero"
   - for ( "Initialize pointers to child-tables";
           "No end child-table1 and no end child-table2";
           "Advance pointers to child-tables if necessary" )
           if ( "Matching field-table1 with field-table2" )

4.3. Name conventions used.
A new name convention is used to denote the parameters of the join3 loop macro. It is suggested that this convention can be adopted for all Chgen generated macros.

     v = var, 
     ptr = pointer,
     p = parent,
     c = child,
     tt = table abbreviation,
     pkey = primary key,
     fkey = foreign key,
     cfkey2p = child's fkey to parent,
     pfkey2c = parent's fkey to child;

4.4. Definition of the join_3_loop macro.

When using the join_3_loop macro, it is required the following declaration before using the macro:
int JOINMATCH =0;


#define join_3_loop(ptt1,vpptr1,ptt2,vpptr2,ctt1,vcptr1,cfkey2p1,\
                                           ctt2,vcptr2,cfkey2p2,f1,f2)\
        for(vcptr1=vpptr1->ctt1##id_fcp, vcptr2=vpptr2->ctt2##id_fcp;\
           ((struct ptt1 *)vcptr1!=vpptr1) && ((struct ptt2 *)vcptr2!=vpptr2);\
            (vcptr1 = (JOINMATCH || (vcptr1->f1 < vcptr2->f2))\
            ?(struct ctt1 *)vcptr1->cfkey2p1##_fpp : vcptr1),\
           (vcptr2 = (JOINMATCH || (vcptr1->f1 > vcptr2->f2))\
            ?(struct ctt2 *)vcptr2->cfkey2p2##_fpp : vcptr2))\
           if((JOINMATCH=(vcptr1->f1==vcptr2->f2)))

4.5. Specifications for the join_3_loop Macro

a) Requires:

   Declaration: int JOINMATCH=0;

   Parameters:

     ptt1     - parent table 1,
     vpptr1   - variable parent pointer 1,
     ptt2     - parent table 2,
     vpptr2   - variable parent pointer 2,
     ctt1     - child table 1,
     vcptr1   - variable child pointer 1,
     cfkey2p1 - child's foreign key to parent 1,
     ctt2     - child table 2,
     vcprt2   - variable child pointer 2,
     cfkey2p2 - child's foreign key to parent 2,
     f1       - field name child 1 to be matched,
     f2       - field name child 2 to be matched.

b) Ensures.

c) Alters.

4.6. Example of an application: Sparse Matrix Multiplication.
The join_3_loop macro is applied to the sparse matrix multiplication problem. It is assumed that the first matrix (MAtrix1) is previously sorted by rows, and the second matrix (MAtrix2) is sorted by columns in ascending order.

A matrix product can be built by concurrently iterating over rows RO of MAtrix1 and columns CO of MAtrix2, and for each RO,CO pair performing the dot product by looping simultaneously over the RO->EL child set and the CO->EL child set.

4.6.1 Data Schema Model.
The data schema model to represent sparse matrices is shown below.

                            
                         ------------
                         |    MA    |
                         |..........| 
                         | MAid     |
                         | mname    |
                         | rowdim   |
                         | coldim   |
                         ------------
                          |       |
               ------------       -------------
               |                              |
              \/                              \/
         -----------                     ------------
         |   RO    |                     |    CO    |
         |.........|                     |..........|
         | ROid    |                     | COid     |
         | MAid    |                     | MAid     |
         | rowndx  |                     | colndx   |
         -----------                     ------------
              |                                |
              |                                |
              -------------        -------------
                          |        |
                         \/        \/
                         -------------
                         |    EL     |
                         |...........|
                         | ELid      |
                         | ROid      |
                         | COid      |
                         | evalue    |
                         | rowidx    |
                         | colidx    |
                         -------------

4.6.2 Input Files.
The input file contains the appropriate data to populate the data schema shown above. An example of an input which contains the definition of two sparse matrices (MATRIX_A and MATRIX_B) is listed below.

MA010001 MATRIX_A   10  10
MA010002 MATRIX_B   10  10
RO010001 MA010001  1
RO010002 MA010001  3
RO010003 MA010001  6
RO010004 MA010002  0
RO010005 MA010002  2
RO010006 MA010002  3
RO010007 MA010002  4
RO010008 MA010002  8
RO010009 MA010002  9
CO010001 MA010001  0
CO010002 MA010001  2
CO010003 MA010001  3
CO010004 MA010001  4
CO010005 MA010001  5
CO010006 MA010001  8
CO010007 MA010001  9
CO010008 MA010002  0
CO010009 MA010002  4
CO010010 MA010002  6
EL010001 RO010001 CO010003 1 1 3  
EL010002 RO010002 CO010001 2 3 0
EL010003 RO010002 CO010002 3 3 2
EL010004 RO010002 CO010004 4 3 4
EL010005 RO010002 CO010005 5 3 5
EL010006 RO010002 CO010006 6 3 8
EL010007 RO010002 CO010007 7 3 9
EL010008 RO010003 CO010001 8 6 0
EL010009 RO010003 CO010007 9 6 9
EL010010 RO010006 CO010008 30 3 0
EL010011 RO010004 CO010009 10 0 4
EL010012 RO010005 CO010009 20 2 4
EL010013 RO010008 CO010009 50 8 4
EL010014 RO010009 CO010009 60 9 4
EL010015 RO010007 CO010010 40 4 6

4.6.3 Source Code of the Application.
The source code for the application which multiplies two sparse matrices using the join_3_loop macro defined above is shown below.


/*-----------------------------------------------------------------------*/
/* University of Massachusetts Lowell                                    */
/* Department of Computer Science                                        */
/*                                                                       */    
/*                                                                       */ 
/* File   :  matrixtest.c                                                */
/* Summary:  This file uses the files generated by chgen                 */
/*-----------------------------------------------------------------------*/

#define MAIN
#include 
#include "matrix.h"

struct MA *MA_elt;
struct RO *RO_elt;
struct CO *CO_elt;

void InitSystem       (char *, char *);
void LoadDatabase     (char *, char *);
void PrintMatrices    (char *);
void MultiplyMatrices (char *, char *, char *, char *);
void GetDimensions    (char *, char *, int *, int *);
void AddMatrix        (char *, char *, int, int);
void AddRow           (char *, char *, int);
void AddColumn        (char *, char *, int);
void AddElement       (char *, char *, int, int, int);

void main (int arc, char *argv[])
{
    InitSystem("matrix.viewdefs","matrix.dat");
    LoadDatabase("Matrices","matrix.dat");
    PrintMatrices("Matrices");
    MultiplyMatrices("Matrices","MATRIX_A","MATRIX_B","MATRIX_C");
    PrintMatrices("Matrices");
}  

void InitSystem(view_defs, filename)
     char *view_defs, *filename;
{
     printf("Initialization:\n");
     printf("---------------\n");
     pr_init(view_defs, filename);
}


void LoadDatabase(view_name,filename)
     char *view_name, *filename;
{
     printf("Load existing Database: %s\n",filename);
     pr_load(view_name,filename);
     printf("Finished loading existing database: %s\n\n",filename);
}

void PrintMatrices(view_name)
     char *view_name;
{

     table_loop(view_name, MA)
      {
	printf("\n\nMatrix: %s BY ROWS\n", MAcurr->mname);
	child_loop(MA, RO, ROid, MAid)
	   {
	      child_loop(RO, EL, ELid, ROid)
		 {
		    printf("ROW index: %d   ", ROcurr->rowndx);
		    printf("ELEMENT value: %d\n", ELcurr->evalue);
		 }
	}

	printf("\n\nMatrix: %s BY COLUMNS\n", MAcurr->mname);
	child_loop(MA, CO, COid, MAid)
	   {
	      child_loop(CO, EL, ELid, COid)
		 {
		    printf("CO index: %d   ", COcurr->colndx);
		    printf("ELEMENT value: %d\n", ELcurr->evalue);
		 }
	   }
      }
      printf("\n");
} 


void MultiplyMatrices(view_name, matrix1, matrix2, matrix3)
     char *view_name, *matrix1, *matrix2, *matrix3; 
{
     int n, m, p, q;

     struct RO *ROcurr_aux;
     struct CO *COcurr_aux;

     struct EL *ELptr1, *ELptr2;
     struct MA *MAcurr_aux;

     GetDimensions(view_name, matrix1, &n,&p);
     GetDimensions(view_name, matrix2, &q,&m);

     if ( n==0 || m==0 || p==0 || q==0 || p!=q )
       {
          printf("Error: Can'not multiply %s(%d,%d) by %s(%d,%d)",
                  matrix1, n, p, matrix2, q, m);
          return;
       }

     AddMatrix(view_name, matrix3, n, m);

     table_loop(view_name, MA)
      {
       if ( !strcmp (matrix1, MAcurr->mname) )
	 {
	   child_loop(MA, RO, ROid, MAid)
	     {
               ROcurr_aux = ROcurr;
               MAcurr_aux = MAcurr;

               table_loop(view_name, MA)
                 {
	           if ( !strcmp (matrix2, MAcurr->mname) )
	             {
	                child_loop(MA, CO, COid, MAid)
	                 {
                            int dotprod=0, JOINMATCH=0;

                            COcurr_aux = COcurr;

                            join_3_loop(RO,ROcurr_aux,CO,COcurr_aux,\
                                        EL,ELptr1,ROid,\
                                        EL,ELptr2,COid,\
                                        colidx,rowidx)
                              {
                                 dotprod += ELptr1->evalue * ELptr2->evalue;
			      }
		            if ( dotprod != 0 )
                              {      
                                AddRow    (view_name, matrix3, ROcurr->rowndx);
                                AddColumn (view_name, matrix3, COcurr->colndx);
                                AddElement(view_name, matrix3,ROcurr->rowndx,
                                           COcurr->colndx, dotprod);
			      }      
                            COcurr = COcurr_aux; /*reset pointer to CO table */
                         }
                     }
	         }
               ROcurr = ROcurr_aux; /* reset pointer to RO table */
               MAcurr = MAcurr_aux; /* reset pointer to MA table */
	     }
	 }
      }
}


void GetDimensions( view_name, matrix_name, nrow, ncol )
     char *view_name, *matrix_name;
     int  *nrow, *ncol;
{
     table_loop(view_name, MA)
      {
       if ( !strcmp (matrix_name, MAcurr->mname) )
	 {
	    *nrow = MAcurr->rowdim;
            *ncol = MAcurr->coldim;
            return;
         }
      }
}

void AddMatrix (view_name, matrix_name, nrow, ncol)
     char *view_name, *matrix_name;
     int  nrow, ncol;
{     
     MA_elt = pr_create(MA);

     pr_set_str ( MA_elt, mname, matrix_name);
     pr_set_int ( MA_elt, rowdim, nrow);
     pr_set_int ( MA_elt, coldim, ncol);
     pr_add ( view_name, MA, MA_elt );
}

void AddRow (view_name, matrix_name, nrow )
     char *view_name, *matrix_name;
     int  nrow;
{    
     RO_elt = pr_create(RO);

     pr_set_key ( RO_elt, MAid, pr_get_key(MA_elt, MAid) );
     pr_set_int ( RO_elt, rowndx, nrow ); 
     pr_add ( view_name, RO, RO_elt );
}

void AddColumn (view_name, matrix_name, ncol )
     char *view_name, *matrix_name;
     int  ncol;
{    
     CO_elt = pr_create(CO);

     pr_set_key ( CO_elt, MAid, pr_get_key(MA_elt, MAid) );
     pr_set_int ( CO_elt, colndx, ncol ); 
     pr_add ( view_name, CO, CO_elt );
}


void AddElement(view_name, matrix_name, nrow, ncol, element)
     char *view_name, *matrix_name;
     int  nrow, ncol, element;
{
     struct EL *EL_elt = pr_create(EL);

     pr_set_key (EL_elt, ROid, pr_get_key(RO_elt, ROid));
     pr_set_key (EL_elt, COid, pr_get_key(CO_elt, COid));
     pr_set_int (EL_elt, evalue, element);
     pr_set_int (EL_elt, rowidx, nrow);
     pr_set_int (EL_elt, colidx, ncol);
     pr_add( view_name, EL, EL_elt);
}

4.6.4 Output Files.
The application multiplies two sparse matrices and generates and stores the resulting matrix in the tables MA, RO, CO, and EL. Afterwards, the matrices are printed resulting in the following output.


Matrix: MATRIX_A BY ROWS
ROW index: 1   ELEMENT value: 1
ROW index: 3   ELEMENT value: 2
ROW index: 3   ELEMENT value: 3
ROW index: 3   ELEMENT value: 4
ROW index: 3   ELEMENT value: 5
ROW index: 3   ELEMENT value: 6
ROW index: 3   ELEMENT value: 7
ROW index: 6   ELEMENT value: 8
ROW index: 6   ELEMENT value: 9

Matrix: MATRIX_A BY COLUMNS
CO index: 0   ELEMENT value: 2
CO index: 0   ELEMENT value: 8
CO index: 2   ELEMENT value: 3
CO index: 3   ELEMENT value: 1
CO index: 4   ELEMENT value: 4
CO index: 5   ELEMENT value: 5
CO index: 8   ELEMENT value: 6
CO index: 9   ELEMENT value: 7
CO index: 9   ELEMENT value: 9

Matrix: MATRIX_B BY ROWS
ROW index: 0   ELEMENT value: 10
ROW index: 2   ELEMENT value: 20
ROW index: 3   ELEMENT value: 30
ROW index: 4   ELEMENT value: 40
ROW index: 8   ELEMENT value: 50
ROW index: 9   ELEMENT value: 60

Matrix: MATRIX_B BY COLUMNS
CO index: 0   ELEMENT value: 30
CO index: 4   ELEMENT value: 10
CO index: 4   ELEMENT value: 20
CO index: 4   ELEMENT value: 50
CO index: 4   ELEMENT value: 60
CO index: 6   ELEMENT value: 40

Matrix: MATRIX_C BY ROWS
ROW index: 1   ELEMENT value: 30
ROW index: 3   ELEMENT value: 800
ROW index: 3   ELEMENT value: 160
ROW index: 6   ELEMENT value: 620


Matrix: MATRIX_C BY COLUMNS
CO index: 0   ELEMENT value: 30
CO index: 4   ELEMENT value: 800
CO index: 6   ELEMENT value: 160
CO index: 4   ELEMENT value: 620

This output can logically be viewed as follows:

Matrix: MATRIX_A

                  0   1   2   3   4   5   6   7   8   9
               ------------------------------------------
             0 |  0   0   0   0   0   0   0   0   0   0 |
             1 |  0   0   0   1   0   0   0   0   0   0 |
             2 |  0   0   0   0   0   0   0   0   0   0 |
             3 |  2   0   3   0   4   5   0   0   6   7 |
             4 |  0   0   0   0   0   0   0   0   0   0 |
             5 |  0   0   0   0   0   0   0   0   0   0 |
             6 |  8   0   0   0   0   0   0   0   0   9 |
             7 |  0   0   0   0   0   0   0   0   0   0 |
             8 |  0   0   0   0   0   0   0   0   0   0 |
             9 |  0   0   0   0   0   0   0   0   0   0 |
               ------------------------------------------


Matrix: MATRIX_B

                  0   1   2   3   4   5   6   7   8   9
               ------------------------------------------
             0 |  0   0   0   0  10   0   0   0   0   0 |
             1 |  0   0   0   0   0   0   0   0   0   0 |
             2 |  0   0   0   0  20   0   0   0   0   0 |
             3 | 30   0   0   0   0   0   0   0   0   0 |
             4 |  0   0   0   0   0   0  40   0   0   0 |
             5 |  0   0   0   0   0   0   0   0   0   0 |
             6 |  0   0   0   0   0   0   0   0   0   0 |
             7 |  0   0   0   0   0   0   0   0   0   0 |
             8 |  0   0   0   0  50   0   0   0   0   0 |
             9 |  0   0   0   0  60   0   0   0   0   0 |
               ------------------------------------------


Matrix: MATRIX_C

                  0   1   2   3   4   5   6   7   8   9
               ------------------------------------------
             0 |  0   0   0   0   0   0   0   0   0   0 |
             1 | 30   0   0   0   0   0   0   0   0   0 |
             2 |  0   0   0   0   0   0   0   0   0   0 |
             3 |  0   0   0   0 800   0 160   0   0   0 |
             4 |  0   0   0   0   0   0   0   0   0   0 |
             5 |  0   0   0   0   0   0   0   0   0   0 |
             6 |  0   0   0   0 620   0   0   0   0   0 |
             7 |  0   0   0   0   0   0   0   0   0   0 |
             8 |  0   0   0   0   0   0   0   0   0   0 |
             9 |  0   0   0   0   0   0   0   0   0   0 |
               ------------------------------------------

5 References

An Introduction to ANSI C on UNIX

An Introduction to Database Systems

Understanding Relational Databases with

Examples in SQL-92, John Wiley & Sons Inc., USA, 1993,
pp. 90, 184-189, 229, 264

5.4. VALDURIEZ Patrick and Georges Gardarin, Analysis and

Comparison of Relational Database System Addison-Wesley
Publishing Company, USA, 1989, pp 94, 130-192

5.5. LECHNER R., email Oct 10, 1.996. Subject: JOIN_LOOP for query

Support. Umass Lowell