Query System by C
Date: 1995/06/11
Message-ID: <3rffoi$a1s_at_news.uncc.edu>
I have built a database engin of query system implemented by Prolog and SQL, but I'm having difficulties in C. Here is an example of query format to retrieve such that:
QUERY: (Name, John) OR (Sex, F) AND [NOT {NOT (Name, Tom) OR (Eyes, blue)}
Using an algorithms of Binary Tree, the above query can be translated into an internal representation such that:
QUERY: (Name, John) OR (S,ex, F) AND (Name, Tom) AND {NOT (Eyes, blue)}
As see an example that NOT {NOT (Name, Tom)} = (Name, Tom)
NOT {OR (Eyes, blue)} = AND {NOT (Eyes, blue)} ,NOT has to be a leaves in the Binary Tree.
If there is a buddy who has programmed a query system in C or has seen a book shows an example implemented in C language, could you email me jkoh_at_unccsun.uncc.edu directly to help me?
Any response would be SINCERELY appreciated.
Attached are a unfinished source program works well as a part the engin I expect, and a data file(Table) to test it's query.
/*********************** source prog. ***************************************/#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
/* define the lengths of the database attributes */
#define ID_L 3
#define NAME_L 8
#define AGE_L 4
#define HGT_L 5
#define WGT_L 4
#define SEX_L 4
#define EYES_L 6
#define RACE_L 10
#define PROF_L 10
#define ADDR_L 14
#define CRIME_L 11
/* define the structure of the link node */
typedef struct node
{
char id[ID_L+1];
char name[NAME_L+1];
char age[AGE_L+1]; char hgt[HGT_L+1]; char wgt[WGT_L+1]; char sex[SEX_L+1]; char eyes[EYES_L+1]; char race[RACE_L+1];
char prof[PROF_L+1];
char addr[ADDR_L+1];
char crime[CRIME_L+1];
struct node *next;
} query;
/* function to print one member of the structure 'query' at a time */
void padz( char *s, int iL)
{
char fmt[10];
char s1[30];
memcpy(s1,s,iL);
sprintf(fmt,"%c-%ds ",'%',iL);
s1[iL]=0;
printf(fmt,s1);
}
int match(char *str1, char *str2, int iL,int ifg) {
/* function to find out if any match is found with the user given query * and the data base. It returns 1 if match is found, otherwise it returns * 0 if no match is found */
char *p;
char str[20];
int retcode = 0;
int negation = 0,i=0;
if(ifg == 0) return 1; /* returns 1 if user has not given any input */ /* corresponding to attribute 'str1' */ /* ie, no attempt is made to match this attribute */while(*str1==' ')str1++;
while(*str2==' ')str2++;
memcpy(str, str1, iL);
i = iL-1; /* trailing spaces or '\n' characters are removed */ while(str[i] == ' ' || str[i]=='\n' ) str[i--]=0;
p = strstr(str2, str); /* searches 'str1' anywhere in the string 'str2' */
if(p) if(*(p-1)=='~') retcode = 0; if((p==NULL) && strchr(str2,'~'))retcode = 1; /* check if negation */ if(p) if( *(p-1) != '~') retcode = 1;
return retcode;
}
/* function to read user query line. If no input is given for this attribute * set ifg=0, otherwise ifg=1 */
void rinput(char *str, int *ifg)
{
fflush(stdin);
gets(str);
if(strlen(str) ==0) *ifg = 0;
else *ifg = 1;
}
int matchid(char *str1, char *str2, int iL, int ifg) {
/* function to find if user given ID is found in the database */ /* return 1 if user is interested for this ID */ /* otherwise return 0. */
int iL1,i,j, negation=0;
int id1, id2;
char str[10], str3[10];
if(ifg == 0) return 1;
while(*str1==' ')str1++;
while(*str2==' ')str2++;
memcpy(str3, str1, iL);
str3[iL]=0;
sscanf(str3,"%d",&id1); /* convert id into a integer */
j=0;
iL1 = strlen(str2);
while(j < iL1)
{
sscanf((str2+j),"%s",str);
j = j + strlen(str);
while(str[j]==' ')j++;
negation = 0;
if(str[0]=='~')
{
negation =1; /* set ngation =1 if negation is asked */ str[0]=' '; /* mask ~ character if exist */}
sscanf(str,"%d",&id2); /* id2 is user given id expressed in integer */
if(negation && id1 == id2 ) return 0;
if(negation && id1 != id2 ) return 1;
if (!negation && id1 == id2 )return 1;
}
return 0;
}
/* define global variables */
int idf,namef,agef,hgtf,wgtf,sexf,eyesf,racef,proff,addrf,crimef;
query *head,*db;
static int cur = 0;
int answer_query(void);
void initialize_dbase(void)
{
typedef struct ABC
{
char id[ID_L+1];
char name[NAME_L+1];
char age[AGE_L+1]; char hgt[HGT_L+1]; char wgt[WGT_L+1]; char sex[SEX_L+1]; char eyes[EYES_L+1]; char race[RACE_L+1];
char prof[PROF_L+1];
char addr[ADDR_L+1];
char crime[CRIME_L+1];
} PERSON;
PERSON info;
char dummy[100];
int count,iP;
FILE *fp;
query *temp;
/* open the database file */
if ((fp = fopen("db_file", "r")) == NULL)
{
printf("initialize_temp: CANNOT OPEN! db_file\n");
exit(1);
}
fgets(dummy,100,fp); /* skip the first line of the file which is */ /* name of the attributes */ /* printf("size of query = %d\n",sizeof(query)); */ while(!feof(fp)) /* main while loop to build the linklist */{
temp=(query *)calloc(1,sizeof(query)); if(temp == NULL)
{
printf("initialize_temp: NO MORE STORAGE AVAILABLE !\n"); exit(1);
}
fgets(dummy,100,fp); /* read the entire line upto the new line character */
/* copy different fields into the structure 'query' */iP=0;
memcpy(temp->id, &dummy[iP], ID_L); iP += ID_L; memcpy(temp->name, &dummy[iP], NAME_L); iP += NAME_L; memcpy(temp->age, &dummy[iP], AGE_L); iP += AGE_L; memcpy(temp->hgt, &dummy[iP], HGT_L); iP += HGT_L; memcpy(temp->wgt, &dummy[iP], WGT_L); iP += WGT_L; memcpy(temp->sex, &dummy[iP], SEX_L); iP += SEX_L; memcpy(temp->eyes, &dummy[iP], EYES_L); iP += EYES_L; memcpy(temp->race, &dummy[iP], RACE_L); iP += RACE_L; memcpy(temp->prof, &dummy[iP], PROF_L); iP += PROF_L; memcpy(temp->addr, &dummy[iP], ADDR_L); iP += ADDR_L; memcpy(temp->crime, &dummy[iP], CRIME_L);
if(!feof(fp))
{
if(head == NULL) { head = temp; /* remember the link head */ db = temp; } else { db->next = temp; /* store the new node into the link list */ db = db->next; /* advance the link pointer */ }
}
}
fclose(fp);
}
int showlist(void)
{
/* function to display the entire link list after it has been build from * the database file. it is required only for debugging purpose. */
struct node *temp;
temp = head;
while(temp != NULL)
{
printf("%s %s %s %s %s %s %s %s %s %s %s\n", temp->id, temp->name, temp->age, temp->hgt, temp->wgt, temp->sex, temp->eyes, temp->race, temp->prof, temp->addr, temp->crime); temp = temp->next; /* advance the link pointer */}
return 1;
}
int answer_queries(void)
{
/* function to answer the user query */
struct node *cur;
int notfound = 1;
char string[200];
int i,j,nid,nname,nage,nhgt,nwgt,nsex,neyes,nrace,nprof,naddr,ncrime;
char sid[100], sname[100],sage[100], shgt[100],swgt[100], ssex[100];
char seyes[100],srace[100],sprof[100],saddr[100],scrime[100];
query *temp;
/* read all input from user */
printf("Enter an id : ");
rinput(sid, &idf);
printf("Enter a name : ");
rinput(sname, &namef);
printf("Enter an age : ");
rinput(sage, &agef);
printf("Enter a height : ");
rinput(shgt, &hgtf);
printf("Enter an weight : ");
rinput(swgt, &wgtf);
printf("Enter a sex : ");
rinput(ssex, &sexf);
printf("Enter a color of eyes : ");
rinput(seyes, &eyesf);
printf("Enter a race : ");
rinput(srace, &racef);
printf("Enter a profession : ");
rinput(sprof, &proff);
printf("Enter a name of city : ");
rinput(saddr, &addrf);
printf("Enter a crime : ");
rinput(scrime, &crimef);
/* end of user input section */
temp = head;
while(temp != NULL) /* main while loop for searching the entire */
/* linked list to satisfy the user query. */ { if((matchid(temp->id,sid, ID_L, idf)) && (match(temp->name, sname,NAME_L, namef)) && (match(temp->age, sage, AGE_L,agef)) && (match(temp->hgt, shgt,HGT_L,hgtf)) && (match(temp->wgt, swgt,WGT_L,wgtf)) && (match(temp->sex, ssex, SEX_L,sexf)) && (match(temp->eyes,seyes,EYES_L,eyesf)) && (match(temp->race, srace,RACE_L,racef)) && (match(temp->prof, sprof, PROF_L,proff)) && (match(temp->addr, saddr,ADDR_L,addrf)) && (match(temp->crime, scrime, CRIME_L,crimef)) ) { padz(temp->id, ID_L); /* print the information if query is */ padz(temp->name, NAME_L);/* is satisfied. */ padz(temp->age, AGE_L); padz(temp->hgt, HGT_L); padz(temp->wgt, WGT_L); padz(temp->sex, SEX_L); padz(temp->eyes, EYES_L); padz(temp->race, RACE_L); padz(temp->prof, PROF_L); padz(temp->addr, ADDR_L); padz(temp->crime, CRIME_L); printf("\n"); notfound = 0; } temp = temp->next;
}
if(notfound) /* display this message if query is not satisfied */ printf("------ query not found ------\n");return 1;
}
void main (void)
{
int opt;
initialize_dbase();
for(;;) /* ask user for query repeatedly unless he/she selects to quit. */ {
printf("1. Answer queries\n" "2. Quit\n" "PLEASE SELECT A NUMBER: \n");scanf("%d",&opt);
switch (opt)
{
case 1: answer_queries(); break; case 2: exit(1); break; default: break;
}
}
}
/********** the end of the prog. **********************/ /************** a data file ***************************/ ID NAME AGE HGT WGT SEX EYES RACE PROF ADDR CRIME 1 John 25 6.01 180 M blue oriental plumber Detroit murder 2 Claude 25 5.11 170 M green caucasian b.keeper Houston rape 3 Robert 27 6.01 250 M hazel oriental sailer Los Angelas hijacking 4 Nancy 13 5.04 130 F blue caucasian secretary Boston Homicide 5 Ingmar 39 5.07 160 M black caucasian student Chicago rape 6 Roberto 31 6.03 220 M black negro barber New York murder 7 Marcel 42 5.01 180 M green eurasian actor New York hijacking 8 Johanna 21 5.05 150 F blue eurasian student Los Angelas drug push 9 Jurgen 13 5.11 190 M hazel caucasian actor Houston kidnapping 10 Tom 65 6.00 200 M blue caucasian mechanic San Francisco armed rob. 11 Albert 13 5.09 250 M black negro barber Detroit rape 12 Mark 24 5.01 150 M brown erasian b.keeper Los Angelas murder 13 Valerie 25 5.08 200 F hazel caucasian actor Chicago armed rob. 14 George 65 4.01 150 M green caucasian plumber San Francisco hijacking 15 Gary 31 5.10 170 M black eurasian sailer Houston drug push 16 Peter 65 5.01 200 M black oriental student New York hijacking 17 Rudy 25 6.03 210 M green caucasian b.keeper San Francisco homicide 18 Homer 32 5.09 180 M black oriental student Chicago murder 19 Jeff 30 5.11 250 M black cucasian plumber Los Angelas rape 20 Julia 24 5.05 150 F hazel caucasian plumber Boston Homicide 21 Karen 13 5.08 250 F blue eurasian secretary Houston murder 22 Steve 29 6.02 190 M brown oriental b.keeper Detroit kidnapping 23 Gerald 32 4.01 160 M black cauacsian sailer Boston armed rob. 24 Margot 13 5.09 180 F black negro secretary Detroit hijacking 25 Frank 48 5.10 190 M hazel eurasian barber New York rape 26 Laurie 21 5.11 190 F green caucasian secretary Los Angelas murder 27 Donald 26 6.01 220 M hazel eurasian plumber New York drug push 28 Adrian 28 5.09 180 M black caucasian b.keeper Chicago murder 29 Ronald 21 5.10 150 M brown oriental sailer New York Homicide 30 Jean 26 5.07 160 F black negro student Detroit armed rob./* the end of the data file * Received on Sun Jun 11 1995 - 00:00:00 CEST