Dependency(application)

A. Fifth Edition

This is the fifth edition of my "dependency" and it is also a practical application of it with my comp353 project

and I changed some serious bugs in it. Actually this is a 5.5 version as I corrected one bug from 5th edition.

Thank you for Vincent!

B.The problem

QAR(employee_sin, employee_name, employee_address, employee_phone, employee_hire_date, employee_type, customer_licence,
customer_name, customer_address, customer_phone, car_licence, modal, service_type, service_description, 
difficulty_level, service_price, service_name, frequency_paid, wage, employee_type, commission, 
payment_method, discount, service_time, service_date, order_id, order_issue_date, order_due_date,
order_status, payment_date, payment_id, payment_amount, part_order_quantity, 
part_order_date,required_part_quantity, part_id, part_name, stock_quantity, quit_date);

employee_type -> commission difficulty_level wage frequency_paid;
payment_method -> discount;
order_id car_licence service_type -> service_time service_date employee_sin;
employee_sin order_id car_licence service_type -> service_time service_date;
order_id -> order_issue_date order_due_date order_status payment_date customer_licence;
payment_id -> payment_method payment_amount discount order_id payment_date;
part_id -> part_name stock_quantity;
part_id service_type -> required_part_quantity;
part_id part_order_date -> part_order_quantity;

employee_sin -> employee_name employee_address employee_phone employee_type employee_hire_date wage 
frequency_paid difficulty_level commission quit_date;
customer_licence -> customer_name customer_address customer_phone;
car_licence -> modal customer_licence;
service_type -> service_description service_price difficulty_level service_name;

D.The major functions

There are few points to mention except that I removed one of my proud implementation of recognizing the "attribute"

name. Originally I want to allow people to write attributes like following: "AaB" where "A" and "Aa" are both 

valid attributes. But there is problems that I still don't know when the name ends. i.e. "employee_id",

"employee_name", when should I stop searching by character? So, I decide to restrict names to be separated by 

space.

Another problems is "combine" which will miss some dependency to combine after immediately delete some dependency.

What else? Too many bugs to mention.

E.Further improvement

F.File listing

1. rules.h 

2. rules.cpp

3. set.h

4. set.cpp

5. main.cpp (main)

file name: set.h

#ifndef SET_H
#define SET_H

#include <iostream>
#include <bitset>

using namespace std;


const int MaxAttrNumber=50;

class Set
{
	//this is a long-pain for me, I have no other way to 
	//let compiler recognize this "friend" function outside declaration
	friend ostream& operator<<(ostream& out, const Set& dummy)	
	{
		for (int i=0; i<dummy.size; i++)
		{
			if (dummy.theSet.test(i))
			{
				out<<'1';
			}
			else
			{
				out<<'0';
			}
		}
		return out;
	}
private:
	bitset<MaxAttrNumber> theSet;
	int size;
	int current;
public:
	void setSize(const Set& dummy);
	int getSize(){ return size;}
	int next(int current) const;
	int first() const;	
	int count() const;
	Set intersection(const Set& dummy) const;
	Set unionSet(const Set& dummy) const;
	Set difference(const Set& dummy) const;
	
	//I am crazy about operator overloading!!!:)
	Set operator-(const Set& dummy) const;
	Set operator+(const Set& dummy) const;
	Set operator*(const Set& dummy) const;
	void operator=(const Set& dummy);
	bool operator==(const Set& dummy) const;
	bool operator!=(const Set& dummy) const;
	bool operator>(const Set& dummy) const;
	bool operator>=(const Set& dummy) const;
	bool operator<(const Set& dummy) const;
	bool operator<=(const Set& dummy) const;
	void set(int pos);
	void forEachSubSet(Set& dummy) const;//must be called before "eachSub()"
	bool eachSub(Set& dummy) const;
	void set();
	void reset(int pos);
	void reset();
	bool test(int pos) const;
	bool isIn(const Set& dummy) const;
	void setSize(int theSize) {size=theSize;}
	Set(int theSize=10);
};

#endif

file name: set.cpp

#include "Set.h"

bool Set::isIn(const Set& dummy) const
{
	for (int i=0; i<size; i++)
	{
		if (theSet.test(i))
		{
			if (!dummy.test(i))//here I use Set.test() instead of set.test()
			{
				return false;
			}
		}
	}
	return true;		
}

bool Set::test(int pos) const
{
	return (pos<size&&theSet.test(pos));
}

//current=-1;//initialize to -1 to prepare for being called
int Set::next(int current) const
{
	for (int i=current+1; i<size; i++)//include situation current>=size
	{
		if (theSet.test(i))
		{
			return i;
		}
	}
	return -1;//not found
}

bool Set::operator !=(const Set& dummy)const
{
	return !(this->operator ==(dummy));
}

bool Set::operator <(const Set& dummy)const
{
	return (this->isIn(dummy)&&this->operator !=(dummy));
}

bool Set::operator <=(const Set& dummy)const
{
	return isIn(dummy);
}

bool Set::operator >(const Set& dummy)const
{
	return !(this->operator <=(dummy));
}

bool Set::operator >=(const Set& dummy)const
{
	return !(this->operator <(dummy));
}

bool Set::operator ==(const Set& dummy)const
{
	for (int i=0; i<(size>dummy.size?size:dummy.size); i++)
	{
		if (test(i)^dummy.test(i))
		{
			return false;
		}
	}
	return true;
}

void Set::setSize(const Set& dummy)
{
	size=dummy.size;
}

void Set::operator =(const Set& dummy)
{
	size=dummy.size;
	for (int i=0; i<size; i++)
	{
		if (dummy.test(i))
		{
			theSet.set(i);
		}
		else
		{
			theSet.reset(i);
		}
	}
}


Set::Set(int theSize)
{
	size=theSize;
	reset();
}

void Set::reset()
{
	for (int i=0; i<size; i++)
	{
		theSet.reset(i);
	}
}

void Set::reset(int pos)
{
	if (pos<size)
	{
		theSet.reset(pos);
	}
}

void Set::set()
{
	theSet.set();
}

void Set::set(int pos)
{
	theSet.set(pos);
}
	
void Set::forEachSubSet(Set& dummy) const
{
	dummy.size=size;
	dummy.reset();//emptyset
}


bool Set::eachSub(Set& dummy) const
{
	int index=first();//starting from very first

	while (index!=-1)//not exceeding boundery
	{
		if (dummy.test(index))
		{
			dummy.reset(index);
			index=next(index);
		}
		else
		{
			dummy.set(index);
			if (dummy<*this)
			{
				return true;
			}
		}
	}
	return false;
}

int Set::first()const
{
	return next(-1);
}

int Set::count()const
{
	return theSet.count();
}

Set Set::unionSet(const Set& dummy) const
{
	Set result;
	result.size=size>dummy.size?size:dummy.size;
	for (int i=0; i<result.size; i++)
	{
		if (test(i)||dummy.test(i))
		{
			result.set(i);
		}
	}
	return result;//this is a temparory object;
}

Set Set::difference(const Set& dummy) const
{
	Set result;
	result.size=size>dummy.size?size:dummy.size;
	for (int i=0; i<result.size; i++)
	{
		if (test(i)&&!dummy.test(i))
		{
			result.set(i);
		}
	}
	return result;
}

Set Set::operator +(const Set& dummy) const
{
	return unionSet(dummy);
}

Set Set::operator -(const Set& dummy) const
{
	return difference(dummy);
}

Set Set::intersection(const Set& dummy) const
{
	Set result;
	result.size=size<dummy.size?size:dummy.size;
	for (int i=0; i<result.size; i++)
	{
		if (test(i)&&dummy.test(i))
		{
			result.set(i);
		}
	}
	return result;
}

Set Set::operator *(const Set& dummy) const
{
	return intersection(dummy);
}

file name: rules.h 

#include <iostream>
#include <bitset>
#include "set.h"

using namespace std;

//make it simple, the first line must list all variables or attributes
//"relation"(A,B,C...)
const int MaxNameLength=30;
const int MaxRuleNumber=200;
const int MaxKeyNumber=15;
const int MaxComposition=20;




class Rule
{
	friend class Rules;
private:
	Set lhs;
	Set rhs;	
public:	
	Rule();
	bool test(int pos, bool isLeft);
	void lhsSet(int pos);
	void rhsSet(int pos);
	void setSize(int theSize);
	void set(int pos, bool isLeft);
	void setRule(const Set& left, const Set& right);
	void operator=(const Rule& dummy);
	bool operator==(const Rule& dummy);
};

class Rules
{
private:
	Set leftSet;
	Set rightSet;
	Set attrClosure[MaxAttrNumber];
	char attributes[MaxAttrNumber][MaxNameLength+1];
	char relationName[MaxNameLength+1];
	bool needKey;//this is needed for checklossless
	int keyCount;
	int attrCount;
	int attrFound[MaxAttrNumber];
	int numberFound;
	int searchByName(const char* name);
	int searchByChar(char ch, int step);
	void ruleReading(FILE* stream);
	Rule rules[MaxRuleNumber];
	int ruleNumber;
	void displayRule(int index);
	void removeRule(int index);
	void calcClosure();
	void addRule(const Set& left, const Set& right);
	int extractNames(FILE* stream, char* delimeters, char endChar='\n');
	void closure(Set& attrSet, int maskedRule) const;
	bool checkAttr(int index);
	bool checkRule(int index);
	void split();
	void combine();
	//"this" relation imply "dummy" relation
	bool imply(const Rules& dummy) const;
	void showMatrix(const Set* matrix, int row);
public:	
	void canonical();
	void displayRules();
	void decomposition();	
	Set candidateKey[MaxKeyNumber];
	void addRule(const Rule& dummy);
	void readFile(const char* fileName);
	void display();
	void display(const Set& attrSet);
	int findKey();
	bool checkLossless();
	bool eachKey(Set& dummy);
	bool operator==(const Rules& dummy) const;
	Rules();
};

file name: rules.cpp 

#include "Rules.h"

void Rules::decomposition()
{
	bool keyFound=false;
	Set dummy;
	findKey();
	canonical();
	for (int i=0; i<ruleNumber; i++)
	{
		dummy=rules[i].lhs+rules[i].rhs;
		cout<<"\ndecomposition #"<<i+1<<":";
		display(dummy);
		cout<<"\ndependency is:";
		displayRule(i);
		cout<<endl;
		for (int j=0; j<keyCount; j++)
		{
			if (candidateKey[j]<=dummy)
			{
				keyFound=true;//some decomposition contains some key
			}
		}
	}
	if (!keyFound)
	{
		cout<<"\ndecomposition #"<<ruleNumber+1<<":";
		display(candidateKey[0]);
		cout<<"\nthe key has no particular dependency\n";
	}
	needKey=!keyFound;
}
	
	
//English can be ambiguous: this function really means:
//"this" relation imply "dummy" relation
bool Rules::imply(const Rules& dummy) const
{
	Set left;
	//for all dependency in "dummy" relation...
	for (int i=0; i<dummy.ruleNumber; i++)
	{
		left=dummy.rules[i].lhs;
		//if the closure of that particular dependency under
		//dependency of "this" relation
		//cannot contains its rhs in that dependency in "dummy" 
		//relation, we say...
		closure(left, -1);
		if (!(dummy.rules[i].rhs<=left))
		{
			//we say "dummy" relation is not implied by "this" relation
			return false;
		}
	}
	//can we?????
	return true;
}

//the "secret" name for this function is "equivalent"
bool Rules::operator ==(const Rules& dummy) const
{
	return imply(dummy)&&dummy.imply(*this);
}



void Rules::canonical()
{
	int i;
	bool found;
	split();
	//cout<<"\nafter split";
	//display();
	do
	{
		i=0; 
		found=false;
		while (i<ruleNumber)
		{
			//displayRule(i);
			if (checkAttr(i))
			{
				found=true;				
			}
			i++;
		}
	}while (found);
	//cout<<"\nafter checkattr";
	//display();
	i=0;
	while (i<ruleNumber)
	{	
		if (!checkRule(i))
		{
			i++;
		}		
	}
	//cout<<"\nafter check rule";
	//display();
	//displayRules();
	combine();
	//displayRules();
	
}

void Rules::displayRules()
{
	for (int i=0; i<ruleNumber; i++)
	{
		displayRule(i);
	}
}

void Rules::combine()
{
	int j;
	for (int i=0; i<ruleNumber-1; i++)
	{
		j=i+1;
		while (j<ruleNumber)
		{
			if (rules[i].lhs==rules[j].lhs)
			{	
				/*
				cout<<"\ncombine rules of \n";
				displayRule(i);
				displayRule(j);
				cout<<"\nfinish\n";
				*/
				rules[i].rhs=rules[i].rhs+rules[j].rhs;
				removeRule(j);
				j=i;//restart is safe!!!
				//Please note here: without j++;
				//I will test "j" again in case originally
				//j+1 is also the same rule to combine!!!!!
			}		
			j++;		
		}
	}
}


void Rules::removeRule(int index)
{
	if (index<ruleNumber)
	{
		ruleNumber--;
		for (int i=index; i<ruleNumber; i++)
		{
			rules[i]=rules[i+1];
		}
	}	
}



bool Rules::checkRule(int index)
{
	Set dummy;
	dummy=rules[index].lhs;

	//displayRule(index);
	closure(dummy, index);
	//display(dummy);
	if (rules[index].rhs<=dummy)
	{
		removeRule(index);
		return true;
	}
	return false;
}


bool Rules::checkAttr(int index)
{
	Set dummy;
	//for the out parameter "dummy", you cannot modify it!
	rules[index].lhs.forEachSubSet(dummy);

	while (rules[index].lhs.eachSub(dummy))
	{
		Set old;	
		//so, you have to use a copy of dummy to calc closure of it
		old=dummy;
		closure(old, index);
	
		if (rules[index].rhs<=old)
		{	
			rules[index].lhs=dummy;
			//if this new rule already exists...
			for (int i=0; i<ruleNumber; i++)
			{
				if (i!=index)
				{
					if (rules[i]==rules[index])
					{
						//found repeat
						removeRule(index);
					}
				}
			}
			
			//otherwise do nothing
			return true;
		}
	}
	return false;
}


int Rules::findKey()
{
	Set theLeft, theRight;
	bool isSub;
	leftSet.setSize(attrCount);
	rightSet.setSize(attrCount);
	leftSet.set();//the universal set
	rightSet.reset();//the empty set
	for (int i=0; i<ruleNumber; i++)
	{
		rightSet= rightSet+rules[i].rhs;
	}
	rightSet=leftSet-rightSet;//rightSet is the minimum part of candidate key
	leftSet=leftSet-rightSet;//leftSet is the difference of rightSet,should be added to key
	keyCount=0;
	theRight=rightSet;
	theLeft=leftSet;

	closure(theRight, -1);
	if (theRight.count()==attrCount)//the only key
	{
		candidateKey[keyCount++]=rightSet;		
	}
	else
	{
		leftSet.forEachSubSet(theLeft);
		while (leftSet.eachSub(theLeft))
		{
			isSub=false;
			theRight=rightSet;
			theRight=theRight+theLeft;
			for (int i=0; i<keyCount; i++)
			{
				//display(theRight);
				//display(candidateKey[i]);
				if (candidateKey[i]<theRight)
				{
					isSub=true;
					break;
				}
			}
			if (isSub)
			{
				continue;//if subset of any candidate key, no need to test
			}
			Set temp;
			temp=theRight;
			closure(temp, -1);
			if (temp.count()==attrCount)
			{
				candidateKey[keyCount++]=theRight;
			}

		}
	}	
	return keyCount;
}

void Rules::showMatrix(const Set* matrix, int row)
{
	for (int j=0; j<attrCount; j++)
	{
		cout<<"\t"<<attributes[j];
	}
	cout<<"\n";
	for (int i=0; i<row; i++)
	{
		displayRule(i);
		cout<<"\t"<<matrix[i]<<endl;
	}
}

//this is a standard algorithm and it makes sure
//that all dependency agree with each other
//or in good English that there is some common agreement 
//between all dependency. Is this good enough? I doubt it.
bool Rules::checkLossless()
{
	int row=needKey?ruleNumber+1:ruleNumber;
	
	Set* matrix=new Set[row];
	for (int i=0; i<row; i++)
	{
		if (needKey&&i==row-1)
		{
			matrix[i]=candidateKey[0];	
		}
		else
		{
			matrix[i]=rules[i].lhs+rules[i].rhs;
		}
	}
	//showMatrix(matrix, row);
	int index;
	bool found;
	do
	{
		index=0;
		found=false;
		while (index<row)
		{
			for (int j=0; j<ruleNumber; j++)
			{
				if (j!=index)
				{
					if (rules[j].lhs<=matrix[index])
					{
						if (!(rules[j].rhs<=matrix[index]))
						{
							matrix[index]=matrix[index]+rules[j].rhs;
							found=true;
						}
					}
				}
			}
			index++;
		}
	}while(found);
	showMatrix(matrix, row);
	for (index=0; index<row; index++)
	{
		if (matrix[index].count()==attrCount)
		{
			delete []matrix;
			return true;
		}
	}
	delete [] matrix;
	return false;
}


void Rules::calcClosure()
{
	for (int i=0; i<attrCount; i++)
	{
		attrClosure[i].setSize(attrCount);
		attrClosure[i].reset();
		attrClosure[i].set(i);
		closure(attrClosure[i], -1);
	}
}

void  Rules::closure(Set& attrSet, int maskedRule) const
{
	bool found=false;
	int i=0;
	do 
	{
		i=0;
		found=false;
		while (i<ruleNumber)
		{
			if (i!=maskedRule)//this rule will not be calculated
			{
				if (rules[i].lhs<=attrSet)//lhs is contained
				{
					if ((attrSet*rules[i].rhs)!=rules[i].rhs)
					{
						attrSet=attrSet+rules[i].rhs;
						found=true;
					}
				}
			}
			i++;
		}
	}
	while (found);
}

void Rules::display(const Set& attrSet)
{
	bool first=true;
	cout<<"{";
	for (int i=0; i<attrCount; i++)
	{
		
		if (attrSet.test(i))
		{
			if (first)
			{
				first=false;
			}
			else
			{
				cout<<",";
			}
			cout<<attributes[i];
		}
	}
	cout<<"}";
}

void Rules::display()
{
	cout<<"\nnow display\n";
	cout<<relationName<<"(";
	for (int i=0; i<attrCount; i++)
	{
		cout<<attributes[i];
		if (i!=attrCount-1)
		{
			cout<<",";
		}
		else
		{
			cout<<");\n";
		}
	}
	for (i=0; i<ruleNumber; i++)
	{
		displayRule(i);
	}
}


bool Rule::test(int pos, bool isLeft)
{
	if (isLeft)
	{
		return lhs.test(pos);
	}
	else
	{
		return rhs.test(pos);
	}
}


void Rules::displayRule(int index)
{
	for (int i=0; i<attrCount; i++)
	{
		if (rules[index].test(i, true))
		{
			cout<<attributes[i]<<" ";
		}
	}
	cout<<" -> ";
	for (i=0; i<attrCount; i++)
	{
		if (rules[index].test(i, false))
		{
			cout<<attributes[i]<<" ";
		}
	}
	cout<<";\n";
}


void Rule::set(int pos, bool isLeft)
{
	if (isLeft)
	{
		lhsSet(pos);
	}
	else
	{
		rhsSet(pos);
	}
}

void Rule::rhsSet(int pos)
{
	rhs.set(pos);
}

void Rule::lhsSet(int pos)
{
	lhs.set(pos);
}

Rule::Rule()
{
	lhs.reset();
	rhs.reset();
	
}


void Rules::readFile(const char* fileName)
{
	FILE* stream;
	stream=fopen(fileName, "r");
	attrCount=extractNames(stream, ",()\n ", ';');//ignore the first relation name
	ruleReading(stream);

}

int Rules::searchByName(const char* name)
{
	for (int i=0; i<attrCount; i++)
	{
		if (strcmp(name, attributes[i])==0)
		{
			return i;
		}
	}
	return -1;
}

/*
void Rules::ruleReading(FILE* stream)
{
	char ch;
	char buffer[MaxNameLength+1];
	int step=0;
	int result;
	ruleNumber=0;//initialize
	bool isLeft=true;
	rules[ruleNumber].setSize(attrCount);//do twice!!
	while (!feof(stream))
	{		
		ch=fgetc(stream);
		if (ch==';'||ch==',')
		{
			ruleNumber++;
			rules[ruleNumber].setSize(attrCount);//do twice!!
			isLeft=true;
		}
		else
		{
			if (ch=='-'||ch=='>')
			{
				isLeft=false;
			}
			else
			{
				if (isalpha(ch)||ch=='_')
				{
					/*
					buffer[step]=ch;
					searchByChar(ch, step);
					if (numberFound!=1)
					{
						if (numberFound==0)
						{
							cout<<"undefined attributes encountered: ";
							buffer[step+1]='\0';
							cout<<buffer<<endl;
							exit(3);
						}
						if (step<MaxNameLength)
						{
							step++;
						}
						else
						{
							cout<<"ambuiguous attributes between ";
							for (int i=0; i<numberFound; i++)
							{
								cout<<attrFound[i]<<"\t";
							}
							exit(1);
						}
					}
					else
					{
						//first condition is that we look for the shortest
						//matched name
						buffer[step+1]='\0';
						if (searchByName(buffer))
						{
							step=0;							
							rules[ruleNumber].set(attrFound[0], isLeft);
						}
					}
					*/
/*
					buffer[step]=ch;
					step++;
				}
				else
				{
					if (step!=0)
					{
						buffer[step]='\0';
						result=searchByName(buffer);
						if (result>=0)
						{
							step=0;		
							rules[ruleNumber].set(result, isLeft);
							//rules[ruleNumber].set(attrFound[0], isLeft);
						}
						else
						{
							cout<<"undefined attribute: "<<buffer<<endl;
							exit(2);
						}
					}
				}

			}
		

		}
	}
}
*/

void Rules::ruleReading(FILE* stream)
{
	char ch;
	char buffer[MaxNameLength+1];
	int step=0;
	int result;
	ruleNumber=0;//initialize
	bool isLeft=true;
	rules[ruleNumber].setSize(attrCount);//do twice!!
	while (!feof(stream))
	{		
		ch=fgetc(stream);
		if (ch=='-'||ch=='>')
		{
			isLeft=false;
		}
		if (isalpha(ch)||ch=='_')
		{			
			buffer[step]=ch;
			step++;
		}
		else//otherwise it is a new attribute
		{
			if (step!=0)//ignore space or change_new_line
			{
				buffer[step]='\0';
				result=searchByName(buffer);
				if (result>=0)
				{
					step=0;		
					rules[ruleNumber].set(result, isLeft);
					//rules[ruleNumber].set(attrFound[0], isLeft);
				}
				else
				{
					cout<<"undefined attribute: "<<buffer<<endl;
					exit(2);
				}
			}
			if (ch==';'||ch==',')
			{
				ruleNumber++;
				rules[ruleNumber].setSize(attrCount);//do twice!!
				isLeft=true;
			}
		}
	}
}


void Rule::setSize(int theSize)
{
	lhs.setSize(theSize);
	rhs.setSize(theSize);
}
	

int Rules::searchByChar(char ch, int step)
{
	if (step==0)//this is first time, and all attributes are searched
	{
		numberFound=0;
		for (int i=0; i<attrCount; i++)//
		{
			if (ch==attributes[i][step])
			{
				attrFound[numberFound]=i;
				numberFound++;
			}
		}
	}
	else
	{
		int number=0;//new 'attrFound' re-counting
		for (int i=0; i<numberFound; i++)
		{
			if (ch==attributes[attrFound[i]][step])
			{
				attrFound[number]=i;
				number++;
			}
		}
		numberFound=number;
	}
	return numberFound;
}


int findChar(char ch, char* str)
{
	int index=0;
	while (str[index]!='\0')
	{
		if (str[index]==ch)
		{
			return index;
		}
		index++;
	}
	return -1;
}

//extract names from a line delimetered by various chars, like ',','(',')'....
int Rules::extractNames(FILE* stream, char* delimeters, char endChar)
{
	int findChar(char ch, char* str);
	char ch;
	int nameIndex=0;
	char buffer[MaxNameLength+1];
	char* ptr=buffer;

	while (!feof(stream))
	{
		ch=getc(stream);
		if (ch==' '||ch==10||ch==9||ch==13)
		{
			continue;
		}
		if (ch==endChar)
		{
			if (ptr!=buffer)
			{
				*ptr='\0';
				if (searchByName(buffer)<0)
				{
					strcpy(attributes[nameIndex], buffer);
				}
				else
				{
					cout<<"found repeat attribute "<<buffer<<endl;
					exit(2);
				}
			}
			break;
		}

		if (findChar(ch, delimeters)>=0)//deli reached
		{
			//skip the consecutive deli
			if (ptr!=buffer)
			{
				*ptr='\0';	
				if (ch=='(')//the very first one
				{
					strcpy(relationName, buffer);
				}
				else
				{
					if (searchByName(buffer)<0)
					{
						strcpy(attributes[nameIndex], buffer);
						nameIndex++;
					}
					else
					{
						cout<<"found repeat attribute "<<buffer<<endl;
						exit(2);
					}					
				}
				ptr=buffer;//restart
			}
		}
		else
		{
			*ptr=ch;
			ptr++;
		}
	}
	return nameIndex;
}		

Rules::Rules()
{
	numberFound=attrCount=0;
}
	
void Rule::operator =(const Rule& dummy)
{
	lhs=dummy.lhs;
	rhs=dummy.rhs;
}

void Rules::addRule(const Rule& dummy)
{
	rules[ruleNumber++]=dummy;
}

void Rules::addRule(const Set& left, const Set& right)
{
	rules[ruleNumber++].setRule(left, right);
}

void Rule::setRule(const Set& left, const Set& right)
{
	lhs=left;
	rhs=right;
}

void Rules::split()
{
	int index;
	for (int i=0; i<ruleNumber; i++)
	{
		if (rules[i].rhs.count()>1)
		{			
			index=rules[i].rhs.first();
			index=rules[i].rhs.next(index);//starting from second one
			while (index!=-1)
			{
				Set right;				
				right.setSize(rules[i].rhs);
				right.set(index);
				rules[i].rhs.reset(index);//remove from old rule
				addRule(rules[i].lhs, right);
				index=rules[i].rhs.next(index);
			}
		}
	}
}

bool Rule::operator ==(const Rule& dummy)
{
	return (lhs==dummy.lhs&&rhs==dummy.rhs);
}

file name: main.cpp (main)

#include "Rules.h"
#include "set.h"

int main()
{
	int number;
	Rules R;
	R.readFile("qar.txt");
	R.display();
	
	
	number=R.findKey();
	for (int i=0; i<number; i++)
	{
		R.display(R.candidateKey[i]);
		cout<<"\n";
	}

	R.canonical();
	cout<<"\nbefore decomposition\n";
	R.displayRules();
	R.decomposition();
	R.checkLossless();
	cout<<"\nfinal display\n";
	R.displayRules();

	return 0;
}

The result is like following:

now display
QAR(employee_sin,employee_name,employee_address,employee_phone,employee_hire_date,employee_type,cust
omer_licence,customer_name,customer_address,customer_phone,car_licence,modal,service_type,service_de
scription,difficulty_level,service_price,service_name,frequency_paid,wage,employee_type,commission,p
ayment_method,discount,service_time,service_date,order_id,order_issue_date,order_due_date,order_stat
us,payment_date,payment_id,payment_amount,part_order_quantity,part_order_date,required_part_quantity
,part_id,part_name,stock_quantity,quit_date);
employee_type  -> difficulty_level frequency_paid wage commission ;
payment_method  -> discount ;
car_licence service_type order_id  -> employee_sin service_time service_date ;
employee_sin car_licence service_type order_id  -> service_time service_date ;
order_id  -> customer_licence order_issue_date order_due_date order_status payment_date ;
payment_id  -> payment_method discount order_id payment_date payment_amount ;
part_id  -> part_name stock_quantity ;
service_type part_id  -> required_part_quantity ;
part_order_date part_id  -> part_order_quantity ;
employee_sin  -> employee_name employee_address employee_phone employee_hire_date employee_type diff
iculty_level frequency_paid wage commission quit_date ;
customer_licence  -> customer_name customer_address customer_phone ;
car_licence  -> customer_licence modal ;
service_type  -> service_description difficulty_level service_price service_name ;
{car_licence,service_type,employee_type,payment_id,part_order_date,part_id}

before decomposition
employee_type  -> difficulty_level frequency_paid wage commission ;
payment_method  -> discount ;
car_licence service_type order_id  -> employee_sin service_time service_date ;
order_id  -> customer_licence order_issue_date order_due_date order_status payment_date ;
payment_id  -> payment_method order_id payment_amount ;
part_id  -> part_name stock_quantity ;
service_type part_id  -> required_part_quantity ;
part_order_date part_id  -> part_order_quantity ;
employee_sin  -> employee_name employee_address employee_phone employee_hire_date employee_type quit
_date ;
customer_licence  -> customer_name customer_address customer_phone ;
car_licence  -> customer_licence modal ;
service_type  -> service_description difficulty_level service_price service_name ;

decomposition #1:{employee_type,difficulty_level,frequency_paid,wage,commission}
dependency is:employee_type  -> difficulty_level frequency_paid wage commission ;


decomposition #2:{payment_method,discount}
dependency is:payment_method  -> discount ;


decomposition #3:{employee_sin,car_licence,service_type,service_time,service_date,order_id}
dependency is:car_licence service_type order_id  -> employee_sin service_time service_date ;


decomposition #4:{customer_licence,order_id,order_issue_date,order_due_date,order_status,payment_dat
e}
dependency is:order_id  -> customer_licence order_issue_date order_due_date order_status payment_dat
e ;


decomposition #5:{payment_method,order_id,payment_id,payment_amount}
dependency is:payment_id  -> payment_method order_id payment_amount ;


decomposition #6:{part_id,part_name,stock_quantity}
dependency is:part_id  -> part_name stock_quantity ;


decomposition #7:{service_type,required_part_quantity,part_id}
dependency is:service_type part_id  -> required_part_quantity ;


decomposition #8:{part_order_quantity,part_order_date,part_id}
dependency is:part_order_date part_id  -> part_order_quantity ;


decomposition #9:{employee_sin,employee_name,employee_address,employee_phone,employee_hire_date,empl
oyee_type,quit_date}
dependency is:employee_sin  -> employee_name employee_address employee_phone employee_hire_date empl
oyee_type quit_date ;


decomposition #10:{customer_licence,customer_name,customer_address,customer_phone}
dependency is:customer_licence  -> customer_name customer_address customer_phone ;


decomposition #11:{customer_licence,car_licence,modal}
dependency is:car_licence  -> customer_licence modal ;


decomposition #12:{service_type,service_description,difficulty_level,service_price,service_name}
dependency is:service_type  -> service_description difficulty_level service_price service_name ;


decomposition #13:{car_licence,service_type,employee_type,payment_id,part_order_date,part_id}
the key has no particular dependency
        employee_sin    employee_name   employee_address        employee_phone  employee_hire_date
employee_type   customer_licence        customer_name   customer_address        customer_phone  car_
licence modal   service_type    service_description     difficulty_level        service_price   serv
ice_name        frequency_paid  wage    employee_type   commission      payment_method  discount
service_time    service_date    order_id        order_issue_date        order_due_date  order_status
        payment_date    payment_id      payment_amount  part_order_quantity     part_order_date requ
ired_part_quantity      part_id part_name       stock_quantity  quit_date
employee_type  -> difficulty_level frequency_paid wage commission ;
        000001000000001001101000000000000000000
payment_method  -> discount ;
        000000000000000000000110000000000000000
car_licence service_type order_id  -> employee_sin service_time service_date ;
        111111111111111111101001111111000000001
order_id  -> customer_licence order_issue_date order_due_date order_status payment_date ;
        000000111100000000000000011111000000000
payment_id  -> payment_method order_id payment_amount ;
        000000111100000000000110011111110000000
part_id  -> part_name stock_quantity ;
        000000000000000000000000000000000001110
service_type part_id  -> required_part_quantity ;
        000000000000111110000000000000000011110
part_order_date part_id  -> part_order_quantity ;
        000000000000000000000000000000001101110
employee_sin  -> employee_name employee_address employee_phone employee_hire_date employee_type quit
_date ;
        111111000000001001101000000000000000001
customer_licence  -> customer_name customer_address customer_phone ;
        000000111100000000000000000000000000000
car_licence  -> customer_licence modal ;
        000000111111000000000000000000000000000
service_type  -> service_description difficulty_level service_price service_name ;
        000000000000111110000000000000000000000
service_type  -> service_name ;
        111111111111111111111111111111111111111

final display
employee_type  -> difficulty_level frequency_paid wage commission ;
payment_method  -> discount ;
car_licence service_type order_id  -> employee_sin service_time service_date ;
order_id  -> customer_licence order_issue_date order_due_date order_status payment_date ;
payment_id  -> payment_method order_id payment_amount ;
part_id  -> part_name stock_quantity ;
service_type part_id  -> required_part_quantity ;
part_order_date part_id  -> part_order_quantity ;
employee_sin  -> employee_name employee_address employee_phone employee_hire_date employee_type quit
_date ;
customer_licence  -> customer_name customer_address customer_phone ;
car_licence  -> customer_licence modal ;
service_type  -> service_description difficulty_level service_price service_name ;
Press any key to continue