Dependency

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

Concordia University

Department of Computer Science

COMP 353 ¨C Databases

Summer 2004

Main Project: QAR Management System

Project Description:

The QAR (Quebec Auto Repair) requires your team to design and implement a relational

database management system for its chain of auto repair shops in Quebec. Each QAR

shop has two basic types of employees, blue-collar workers and office people including a

manager. Manager is only responsible to manage the shop and plan daily schedule for the

blue-collar workers. Blue-collar workers are divided into apprentices and senior workers.

Each QAR shop offers four types of car services: oil change, tire rotation and mounting,

brake service, and replacement of mufflers. Junior apprentices are only allowed to change

oil. After their graduation to senior apprentices they are also allowed to do tire rotation

and mounting. The senior workers can provide any of the four car services. Each car

service takes exactly one hour and is offered for a fixed price (excluding applicable

taxes). However, the prices for the service types are different and increase in the

following order: oil change, tire rotation and mounting, brake service, replacement of

mufflers. Each employee works 8 hours a day. Each repair is performed by one bluecollar

worker and must be completed on the same day. The blue-collar workers get paid

weekly; the others get paid biweekly. The blue-collar workers have a fixed salary and

also get a 1.5% commission for each service.

The auto parts are stored in a remote warehouse and delivered to the shop within a day.

Only the parts necessary for one day¡¯s work can be stored in the shop.

Each customer receives a confirmation listing the ordered services and price quote. When

customers pick up their car, they receive a bill listing all services and their price.

Customers have to pay their bill immediately. They can use cash, debit cards, or credit

cards. In case of paying with cash or debit cards they receive a 3% discount off the total

bill.

Implementation Requirement:

Use the Oracle DBMS to implement the required system. Your model QAR shop has 1

boss, 2 office people, 2 junior and 2 senior apprentices, and 2 senior workers. The QAR

shop has an average of 40 orders per day. These can be roughly divided into ~55% oil

changes, ~15% tire rotation and mounting, ~20% break service, and ~10% muffler

replacements. On each day customers pay with cash (~25%), debit (~35%), and credit

cards (~40%).

Create a database, collect appropriate data and store them in the database. Your QAR

shop starts on May 01, 2004. It is open from Monday to Friday from 08:00 until 17:00

with a launch break from 12:00 to 13:00. The database should include data until June 10,

2004. Unfortunately, 1 junior apprentice quits her/his job after the first week and 1 new

senior apprentice is immediately hired as replacement. The requirements mentioned

above have to be observed when you populate the database but not for drive-in

customers. You should show the data integrity of your database at the demo time. You

have to use HTML and PHP to build interfaces supporting the following queries and

transactions.

1. Create forms for manipulating (entity) tables: insertion, deletion and update of

tuples.

2. Give a list of all workers who made an oil change on any day of the week and

where the customer paid with cash.

3. Compute the schedule of the next day for workers. List the percentage of

unallocated work time.

4. Compute pay cheques (salaries) for workers at each Friday.

5. Report on the car services planned for the next day.

6. Produce an order for supplies needed for the next day by considering what is

currently in stock and what will be needed for the next day. Make sure the local

store will have 20% more in stock than required for the next day.

7. Create an HTML form for new customers without an appointment. The form

should ask for the required services and return the next 2 available time slots

(name of worker, status). The customer have the option to sign up one of the time

slots.

8. Create an HTML form for registered customers with an appointment. The form

should identify the customer and return the car services planned for this customer.

Customers have the option to cancel their appointment(s).

9. Generate a detailed report for all services provided for a given car during a

specified period of time.

What you should hand in:

The deliverables consist of the followings:

Phase I: Design

Develop an E/R diagram for the entities and their relationships. Make logical/intelligent

assumption(s) to clarify the entities and their relationships. The design should be as

compact as possible without sacrificing the required objectives. Convert the E/R diagram

into a relational database scheme. Make refinements to the scheme (if necessary).

Identify the various integrity constraints in the scheme such as primary keys and foreign

keys, functional dependencies and referential integrity constraints. Make sure that your

database scheme is at least in 3NF.

Any ambiguities in this problem statement will have to be resolved. Some of these could

be done via discussions that hopefully lead to design decisions. Your report should give

rational explanations for all assumptions and decisions.

Phase II: Implementation

Write the SQL scripts to create the tables with the schemas and constraints developed in

Phase I. Populate your tables with data, numerous and varied enough to test and

demonstrate the functions implemented. Build an interface, using HTML and PHP, for

each of the functions listed earlier. A working version of the project should be

demonstrated at Oracle lab before your Lab Instructor during the last week of the term.

Every member of the group MUST be present during this demo. During demo, you must

hand-in a Report containing all the details of the design and implementation of your

Project work. If you need further clarification about deliverables, you need to consult

with your lab instructor.

Note 1:

Source code of the application can be copied into Floppy/CD or printed on

papers (based on your preference and suitability) and hand-in along with Report.

Note 2:

Your project report must be properly bound in a folder (or binder) with your

names, ID¡¯s and the identification of the team clearly appearing on the cover.

Inappropriate submissions will be penalized.

Note 3:

Give details of each member¡¯s contribution in this project, that is, give a table

that shows who (which student) did which part of the project. It is wise to be realistic

since the lab instructors will also have to evaluate each team member.

¡¡

C.The idea of program
¡¡
This is a practical application of how powerful my program is! You see, you even don't have to draw an E-R
¡¡
diagram. What you have to do is just name all possible attributes in the whole project and then write down as
¡¡
many dependency as possible. The more complete the set of dependencies you write down, the more accurate my
¡¡
program will do. It will calculate the canonical cover, do the decomposition to ensure a BCNF. Before that it
¡¡
of course calculates all the candidate keys. Since you have the decompositions based on canonical cover, create
¡¡
tables on them, set up keys with those dependency's lhs. That's it!
¡¡
The below is my dependency definition file:
¡¡

    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

    ¡¡