Read Date and Pascal.

Still can't really get a handle on the higher NFs. Anybody got a succint way
of explaining them?

Mike

[ Post a follow-up to this message ]

Fourth Normal Form (4NF) makes use of multi-valued dependencies.  The
problem it solves is that the table has too many of them.  For example,
consider a table of departments, their projects, and the parts they
stock.  The MVD's in the table would be:

department ->> projects

department ->> parts

Assume that department d1 works on jobs j1, and j2 with parts p1 and
p2; that department d2 works on jobs j3, j4, and j5 with parts p2 and
p4; and that department d3 works on job j2 only with parts p5 and p6.
The table would look like this:

department job part
=============
d1   j1   p1
d1   j1   p2
d1   j2   p1
d1   j2   p2
d2   j3   p2
d2   j3   p4
d2   j4   p2
d2   j4   p4
d2   j5   p2
d2   j5   p4
d3   j2   p5
d3   j2   p6

If you want to add a part to a department, you must create more than
one new row.

Likewise, to remove a part or a job from a row can destroy information.
Updating a part or job name will also require multiple rows to be
changed.

The solution is to split this table into two tables, one with
(department, projects) in it and one with (department, parts) in it.
The definition of 4NF is that we have no more than one MVD in a table.
If a table is in 4NF, it is also in BCNF.

Fifth Normal Form (5NF), also called the Join-Projection Normal Form or
the Projection-Join Normal Form, is based on the idea of a lossless
JOIN or the lack of a join-projection anomaly.  This problem occurs
when you have an n-way relationship, where n > 2.  A quick check for
5NF is to see if the table is in 3NF and all the candidate keys are
single columns.

As an example of the problems solved by 5NF, consider a table of house
notes that records the buyer, the seller, and the lender:

HouseNotes
buyer     seller    lender
==================================
Smith     Jones     National Bank
Smith     Wilson    Home Bank
Nelson    Jones     Home Bank

This table is a three-way relationship, but because many CASE tools
allow only binary relationships it might have to be expressed in an E-R
diagram as three binary relationships, which would generate CREATE
TABLE statements leading to these tables:

BuyerLender
buyer     lender
=============================
Smith      National Bank
Smith      Home Bank
Nelson     Home Bank

SellerLender
seller    lender
=======================
Jones     National Bank
Wilson    Home Bank
Jones     Home Bank

BuyerSeller
buyer   seller
================
Smith   Jones
Smith   Wilson
Nelson  Jones

The trouble is that when you try to assemble the original information
by joining pairs of these three tables together, thus:

SELECT BS.buyer, SL.seller, BL.lender
FROM BuyerLender AS BL,
SellerLender AS SL,
BuyerSeller AS BS
WHERE BL.buyer = BS.buyer
AND BL.lender = SL.lender
AND SL.seller = BS.seller;

you will recreate all the valid rows in the original table, such as
('Smith', 'Jones', 'National Bank'), but there will also be false rows,
such as ('Smith', 'Jones', 'Home Bank'), which were not part of the
original table.  This is called a join-projection anomaly.

There are also strong JPNF and overstrong JPNF, which make use of JOIN
dependencies (JD for short).  Unfortunately, there is no systematic way
to find a JPNF or 4NF schema, because the problem is known to be NP
complete.

As an aside, Third Normal Form is very popular with CASE tools and most
of them can generate a schema where all of the tables are in 3NF.  They
obtain the FDs from an E-R (entity-relationship) diagram or from a
statistical analysis of the existing data, then put them together into
tables and check for normal forms.

The bad news is that it is often possible to derive more than one 3NF
schema from a set of FDs.  Most of CASE tools that produce an E-R
diagram will find only one of them, and go no further.  However, an ORM
(Object Role Model) tool properly, the schema will be in 5NF.  I
suggest strongly that you get any of the books by Terry Halpin on this
technique.

Ronald Fagin defined Domain/Key Normal Form (DKNF) in 1981 as a schema
having all of the domain constraints and functional dependencies
enforced.  There is not yet a general algorithm that will always
generate the DKNF solution given a set of constraints.  We can,
however, determine DKNF in many special cases and it is a good guide to
writing DDL in the real world.

You also need to look up articles by Tom Johnston on non-normal form
redundancy problems.

[ Post a follow-up to this message ]

> department job part
> =============
> d1   j1   p1
> d1   j1   p2
> d1   j2   p1
> d1   j2   p2
> d2   j3   p2
> d2   j3   p4
> d2   j4   p2
> d2   j4   p4
> d2   j5   p2
> d2   j5   p4
> d3   j2   p5
> d3   j2   p6
>
> The solution is to split this table into two tables, one with
> (department, projects) in it and one with (department, parts) in it.

Below script shows an similar solution using an eXperimental Db:

// Create departments
CREATE *dept.item ~in = dir;
CREATE *d1.cls = dept;
CREATE *d2.cls = dept;
CREATE *d3.cls = dept;

// Create projects
CREATE *project.item ~in = dir;
CREATE *j1.cls = project;
CREATE *j2.cls = project;
CREATE *j3.cls = project;
CREATE *j4.cls = project;
CREATE *j5.cls = project;
CREATE *j6.cls = project;

// Create products
CREATE *product.item ~in = dir;
CREATE *p1.cls = product;
CREATE *p2.cls = product;
CREATE *p3.cls = product;
CREATE *p4.cls = product;
CREATE *p5.cls = product;
CREATE *p6.cls = product;

// Create dept projects
CREATE d1.project = j1;
CREATE d1.project = j2;

CREATE d2.project = j3;
CREATE d2.project = j4;
CREATE d2.project = j5;

CREATE d3.project = j2;

// Create dept project products
CREATE (d1.project=j1).product = p1;
CREATE (d1.project=j1).product = p2;

CREATE (d1.project=j2).product = p1;
CREATE (d1.project=j2).product = p2;

CREATE (d2.project=j3).product = p2;
CREATE (d2.project=j3).product = p4;

CREATE (d2.project=j4).product = p2;
CREATE (d2.project=j4).product = p4;

CREATE (d2.project=j5).product = p2;
CREATE (d2.project=j5).product = p4;

CREATE (d3.project=j2).product = p5;
CREATE (d3.project=j2).product = p6;

// Find all products used by dept1's project2
// Finds p1 and p2.
SELECT (d1.project=j2).product=%;

// One view in tree appears as follows:
dept
__d1
____j1
______p1
______p2
____j2
______p1
______p2
__d2
____j3
______p2
______p4
____j4
______p2
______p4
____j5
______p2
______p4
__d3
____j2
______p5
______p6

[ Post a follow-up to this message ]

Normalisation

Normalisation degrees of relational database tables have been defined
and include:

First normal form (1NF). This is the "basic" level of normalisation and
generally corresponds to the definition of any database, namely: It
contains two-dimensional tables with rows and columns. Each row
represents a unique instance and must be different in some way from any
other row (that is, no duplicate rows are possible). All entries in any
column must be of the same kind. For example, in the column labelled
"Employee," only employee names or numbers are permitted.

Second normal form (2NF). At this level of normalisation, Each column
(non-key column) should be fully dependent of the key-column For
example, in a table with three columns containing employee name, rate
category, and hourly rate are dependent of employee id not directly
with project id.

Third normal form (3NF). At the second normal form, modifications are
still possible where a non-key column is a function of another non-key
column. For example, using the employee table, removing a row
describing an employee hourly rate, will also remove the fact that the
rate category has a certain hourly rate. In the third normal form,
these tables would be divided into two tables so that rate category
would be tracked separately.

Domain/key normal form (DKNF). A key uniquely identifies each row in a
table. A domain is the set of permissible values for an attribute. By
enforcing key and domain restrictions, the database is assured of being
freed from modification inconsistency.


De-Normalised Information

Employee_project table
Project number	Project name	Employee number	Employee name	Rate
category	Hourly rate
1023	Madagascar travel site	11	Vincent Radebe	A	$60
1023	Madagascar travel site	12	Pauline James	B	$50
1023	Madagascat travel site	16	Charles Ramoraz	C	$40
1056	Online estate agency	11	Vincent Radebe	A	$60
1056	Online estate agency	17	Monique Williams	B	$50


The definition of 1st normal form
1.	there are no repeating groups
2.	all the key attributes are defined
3.	all attributes are dependent on the primary key

Employee_project table (1NF)
Project number	Employee number	Project name	Employee name	Rate
category	Hourly rate
1023	11	Madagascar travel site	Vincent Radebe	A	$60
1023	12	Madagascar travel site	Pauline James	B	$50
1023	16	Madagascat travel site	Charles Ramoraz	C	$40
1056	11	Online estate agency	Vincent Radebe	A	$60
1056	17	Online estate agency	Monique Williams	B	$50


Definition of 2nd normal form
Table is in 1st normal form
It includes no partial dependencies (where an attribute is dependent on
only a part of a primary key).

Project table (2NF)
Project number	Project name
1023	Madagascar travel site
1056	Online estate agency

Employee table (2NF)
Employee number	Employee name	Rate category	Hourly rate
11	Vincent Radebe	A	$60
12	Pauline James	B	$50
16	Charles Ramoraz	C	$40
17	Monique Williams	B	$40


The definition of 3rd normal form
Table is in 2nd normal form
It contains no transitive dependencies (where a non-key attribute is
dependent on another non-key attribute).

Project table (3NF)
Project number	Project name
1023	Madagascar travel site
1056	Online estate agency


Employee table (3NF)
Employee number	Employee name	Rate category
11	Vincent Radebe	A
12	Pauline James	B
16	Charles Ramoraz	C
17	Monique Williams	B

Rate table (3NF)
Rate category	Hourly rate
A	$60
B	$50
C	$40



Mike MacSween wrote:
> Read Date and Pascal.
>
> Still can't really get a handle on the higher NFs. Anybody got a
succint way
> of explaining them?
>
> Mike

[ Post a follow-up to this message ]

Thanks Joe

I'll keep studying and try to get it.

But let's say that I don't want to and just want to know that the table is
in 5NF. Is there a rule of thumb? Yes, rubbish isn't it, but just go with
me. Like you know somethings in BCNF if it's in 3NF and it's only got single
column keys, yes? Is there an easy to remember one for 5NF?

And is that table 'all key'?

I'll investigate DKNF and ORM.

Cheers, Mike


"-CELKO-" <jcelko212@earthlink.net> wrote in message
news:1104892453.355647.121130@z14g2000cwz.googlegroups.com...
> Fourth Normal Form (4NF) makes use of multi-valued dependencies.  The
> problem it solves is that the table has too many of them.  For example,
> consider a table of departments, their projects, and the parts they
> stock.  The MVD's in the table would be:
>
> department ->> projects
>
> department ->> parts
>
> Assume that department d1 works on jobs j1, and j2 with parts p1 and
> p2; that department d2 works on jobs j3, j4, and j5 with parts p2 and
> p4; and that department d3 works on job j2 only with parts p5 and p6.
> The table would look like this:
>
> department job part
> =============
> d1   j1   p1
> d1   j1   p2
> d1   j2   p1
> d1   j2   p2
> d2   j3   p2
> d2   j3   p4
> d2   j4   p2
> d2   j4   p4
> d2   j5   p2
> d2   j5   p4
> d3   j2   p5
> d3   j2   p6
>
> If you want to add a part to a department, you must create more than
> one new row.
>
> Likewise, to remove a part or a job from a row can destroy information.
> Updating a part or job name will also require multiple rows to be
> changed.
>
> The solution is to split this table into two tables, one with
> (department, projects) in it and one with (department, parts) in it.
> The definition of 4NF is that we have no more than one MVD in a table.
> If a table is in 4NF, it is also in BCNF.
>
> Fifth Normal Form (5NF), also called the Join-Projection Normal Form or
> the Projection-Join Normal Form, is based on the idea of a lossless
> JOIN or the lack of a join-projection anomaly.  This problem occurs
> when you have an n-way relationship, where n > 2.  A quick check for
> 5NF is to see if the table is in 3NF and all the candidate keys are
> single columns.
>
> As an example of the problems solved by 5NF, consider a table of house
> notes that records the buyer, the seller, and the lender:
>
> HouseNotes
> buyer     seller    lender
> ==================================
> Smith     Jones     National Bank
> Smith     Wilson    Home Bank
> Nelson    Jones     Home Bank
>
> This table is a three-way relationship, but because many CASE tools
> allow only binary relationships it might have to be expressed in an E-R
> diagram as three binary relationships, which would generate CREATE
> TABLE statements leading to these tables:
>
> BuyerLender
> buyer     lender
> =============================
> Smith      National Bank
> Smith      Home Bank
> Nelson     Home Bank
>
> SellerLender
> seller    lender
> =======================
> Jones     National Bank
> Wilson    Home Bank
> Jones     Home Bank
>
> BuyerSeller
> buyer   seller
> ================
> Smith   Jones
> Smith   Wilson
> Nelson  Jones
>
> The trouble is that when you try to assemble the original information
> by joining pairs of these three tables together, thus:
>
> SELECT BS.buyer, SL.seller, BL.lender
> FROM BuyerLender AS BL,
> SellerLender AS SL,
> BuyerSeller AS BS
> WHERE BL.buyer = BS.buyer
> AND BL.lender = SL.lender
> AND SL.seller = BS.seller;
>
> you will recreate all the valid rows in the original table, such as
> ('Smith', 'Jones', 'National Bank'), but there will also be false rows,
> such as ('Smith', 'Jones', 'Home Bank'), which were not part of the
> original table.  This is called a join-projection anomaly.
>
> There are also strong JPNF and overstrong JPNF, which make use of JOIN
> dependencies (JD for short).  Unfortunately, there is no systematic way
> to find a JPNF or 4NF schema, because the problem is known to be NP
> complete.
>
> As an aside, Third Normal Form is very popular with CASE tools and most
> of them can generate a schema where all of the tables are in 3NF.  They
> obtain the FDs from an E-R (entity-relationship) diagram or from a
> statistical analysis of the existing data, then put them together into
> tables and check for normal forms.
>
> The bad news is that it is often possible to derive more than one 3NF
> schema from a set of FDs.  Most of CASE tools that produce an E-R
> diagram will find only one of them, and go no further.  However, an ORM
> (Object Role Model) tool properly, the schema will be in 5NF.  I
> suggest strongly that you get any of the books by Terry Halpin on this
> technique.
>
> Ronald Fagin defined Domain/Key Normal Form (DKNF) in 1981 as a schema
> having all of the domain constraints and functional dependencies
> enforced.  There is not yet a general algorithm that will always
> generate the DKNF solution given a set of constraints.  We can,
> however, determine DKNF in many special cases and it is a good guide to
> writing DDL in the real world.
>
> You also need to look up articles by Tom Johnston on non-normal form
> redundancy problems.
>

[ Post a follow-up to this message ]

The only rule I know for seeing 5NF at a glance is that if the table is
3NF and all candidate keys are simple (one column), then you have 5NF.
Ron Fagin proved that years ago and Chris date wrote it up in his old
column in DBP&D under the title "Theory is Practical!" in 1992.

[ Post a follow-up to this message ]

> HouseNotes
> buyer     seller    lender
> ==================================
> Smith     Jones     National Bank
> Smith     Wilson    Home Bank
> Nelson    Jones     Home Bank

Script below shows an alternate solution using an eXperimental Db:

// Create persons
CREATE *person.item ~in = dir;
CREATE *smith.cls = person;
CREATE *nelson.cls = person;
CREATE *jones.cls = person;
CREATE *wilson.cls = person;

// Create buyers
CREATE *buyer.item ~in = dir;
CREATE smith.cls = buyer;
CREATE nelson.cls = buyer;

// Create sellers
CREATE *seller.item ~in = dir;
CREATE jones.cls = seller;
CREATE wilson.cls = seller;

// Create banks
CREATE *bank.item ~in = dir;
CREATE *national bank.cls = bank;
CREATE *home bank.cls = bank;

// Create lenders
CREATE *lender.item ~in = dir;
CREATE national bank.cls = lender;
CREATE home bank.cls = lender;

// Create house notes
CREATE *house note.item ~in = dir;

// Create 1st note
CREATE *;
CREATE it.cls = house note;
CREATE it.buyer = smith;
CREATE it.seller = jones;
CREATE it.lender = national bank;

// Create 2nd note
CREATE *;
CREATE it.cls = house note;
CREATE it.buyer = smith;
CREATE it.seller = wilson;
CREATE it.lender = home bank;

// Create 3rd note
CREATE *;
CREATE it.cls = (%.name=house note & %.item~in=dir);
CREATE it.buyer = (%.name=nelson & %.cls=buyer);
CREATE it.seller = (%.name=jones & %.cls=seller);
CREATE it.lender = (%.name=home bank & %.cls=lender);

// Find a note where buyer is smith,
// seller is wilson and lender is home bank.
// Finds 2nd house note.
SELECT %.cls=house note & %.buyer=smith & %.seller=wilson &
%.lender=home bank;

[ Post a follow-up to this message ]

Thanks. I'm sort of missing your point. Perhaps you could explain what this
all means.

Cheers, Mike

"Neo" <neo55592@hotmail.com> wrote in message
news:1104940488.918072.284480@c13g2000cwb.googlegroups.com... 
>
> Script below shows an alternate solution using an eXperimental Db:
>
> // Create persons
> CREATE *person.item ~in = dir;
> CREATE *smith.cls = person;
> CREATE *nelson.cls = person;
> CREATE *jones.cls = person;
> CREATE *wilson.cls = person;
>
> // Create buyers
> CREATE *buyer.item ~in = dir;
> CREATE smith.cls = buyer;
> CREATE nelson.cls = buyer;
>
> // Create sellers
> CREATE *seller.item ~in = dir;
> CREATE jones.cls = seller;
> CREATE wilson.cls = seller;
>
> // Create banks
> CREATE *bank.item ~in = dir;
> CREATE *national bank.cls = bank;
> CREATE *home bank.cls = bank;
>
> // Create lenders
> CREATE *lender.item ~in = dir;
> CREATE national bank.cls = lender;
> CREATE home bank.cls = lender;
>
> // Create house notes
> CREATE *house note.item ~in = dir;
>
> // Create 1st note
> CREATE *;
> CREATE it.cls = house note;
> CREATE it.buyer = smith;
> CREATE it.seller = jones;
> CREATE it.lender = national bank;
>
> // Create 2nd note
> CREATE *;
> CREATE it.cls = house note;
> CREATE it.buyer = smith;
> CREATE it.seller = wilson;
> CREATE it.lender = home bank;
>
> // Create 3rd note
> CREATE *;
> CREATE it.cls = (%.name=house note & %.item~in=dir);
> CREATE it.buyer = (%.name=nelson & %.cls=buyer);
> CREATE it.seller = (%.name=jones & %.cls=seller);
> CREATE it.lender = (%.name=home bank & %.cls=lender);
>
> // Find a note where buyer is smith,
> // seller is wilson and lender is home bank.
> // Finds 2nd house note.
> SELECT %.cls=house note & %.buyer=smith & %.seller=wilson &
> %.lender=home bank;
>

[ Post a follow-up to this message ]

> What sort of database is it?

It is a tomato. Some say it is a vegetable. Some say it is a fruit.
Others say it is a high school project.

> What are the pros and cons?
More flexible, kinda like LISP.
Less practical, kinda like LISP.

[ Post a follow-up to this message ]

Mikito,
Bravo!

[ Post a follow-up to this message ]