Relation Algebra: Containment

Question

Post reply

Relation Algebra: Containment

teds-250959

Old Hand

Points: 392
More actions
November 21, 2005 at 10:10 am

#92255

I am studying relational algebra and I cant find an example of containment. Could someone please give me or point me to an example of a query using containment?
Thanks!

Viewing 10 posts - 1 through 9 (of 9 total)

You must be logged in to reply to this topic. Login to reply

Carl Federl One Orange Chip Points: 25384 More actions · Answer 1

By containment do you mean division ?

The classic example of division is "What pilots can fly all planes in the hanger?"

There is also a "even" division: "What pilots can fly all plans in the hanger and only those planes?"

See Joe Celko's artice on Relational Division at

http://www.dbazine.com/ofinterest/oi-articles/celko1

SQL = Scarcely Qualifies as a Language

teds-250959 Old Hand Points: 392 More actions · Answer 2

Carl,

Thanks for the try but that’s not what I am looking for. As that article states there are 8 types of Relational Algebra and Containment is one of them. Division is another and they are two different things. I have examples of 7 out of the 8 types – containment being the one I am missing.

Carl Federl One Orange Chip Points: 25384 More actions · Answer 3

Here is my list of the eight relational operators.

What is the difference between this list and yours ?

1. Project - Subset of attributes

2. Extend - Add a attribute

3. Restrict - Subset of tuples

4. Product - all combinations of two tuples

5. Union - all tuples that appear in either or both of two relations

6. Difference - all tuples that appear in one relation but not in another relation.

7. Divide

8. Join - Actually derivable from applying restrict on a Product. e.g.

select * from A join B on A.c1 = B.c2

is equivalent to:

select * from A

CROSS JOIN -- alias for the PRODUCT operator

B WHERE A.c1 = B.c2 -- Restrict

I also found this link from University of Wisconsin on set containtment joins: http://www-db.cs.wisc.edu/dbseminar/fall00/talks/raghav.ppt

Their explanation appears to match "divide"

SQL = Scarcely Qualifies as a Language

teds-250959 Old Hand Points: 392 More actions · Answer 4

Great idea, let’s compare:

1) Project -check!

2) Extend -not on my list or any other list

3) Restrict -on my list as Selection which I think it more std - check!

4) Product -not on my list but on most lists as Cartesian Product

5) Union -check!

6) Difference -check!

7) Divide -check!

8) Join -check!

I don’t think your #2 is valid and you are missing Intersection so I think you should sub Intersection for your Extend.

By process of elimination my Containment must be Cartesian product! Yay! Found it! I have no idea where I got the term Containment

So a complete list would be:

1) Union (union all)

2) Difference (set difference - The rows that exist in A but not in B)

3) Cartesian Product (cross join)

4) Selection (restriction, where clause)

5) Projection (The selection of only particular columns from a table)

6) Intersection (Only the rows that are in both A and B)

7) Join (inner and outer joins)

8) Division (Find all rows of A that are related to each and every one of the rows of a B)

Good list:

http://oldweb.uwp.edu/academic/mis/baldwin/i69alg.htm

Odd lists that use Rename as one of the 8 (no way that is one):

http://www.cs.sfu.ca/CC/354/zaiane/material/notes/Chapter3/node7.html

http://en.wikipedia.org/wiki/Relational_algebra#Set_operations

Thanks so much for sticking with me Carl!

Carl Federl One Orange Chip Points: 25384 More actions · Answer 5

Glad to help and thanks for the links.

Wikipedia has another category titled "Operations for domain computations" which includes Aggregation and Extend, so I guess those should be excluded.

Codd also suggested a Theta-Join, sort of a "best fit" join that is move complicated than Division. Like 5th Normal Form, it is rare but when needed, knowledge that a solution exists is valuable.

SQL = Scarcely Qualifies as a Language

teds-250959 Old Hand Points: 392 More actions · Answer 6

Carl,

Do you have a simple example of a Theta-Join? I cant seem to find one.

Thanks!

Carl Federl One Orange Chip Points: 25384 More actions · Answer 7

See Joe Celko's article "Happier marriages through math"

at http://www.dbmsmag.com/9808d06.html

This is also known as the bin packing problem.

PS.

"A Relational Model of Data Large Shared Data Banks" can be found at: http://www.cs.wisc.edu/~nil/764/root/1_codd70.pdf

This is the University of Wisconsin (in Madison) have they have some very interesting material on their web site.

SQL = Scarcely Qualifies as a Language

Carl Federl One Orange Chip Points: 25384 More actions · Answer 8

Another example from Joe Celko is at

http://groups.google.com/group/microsoft.public.sqlserver.programming/browse_thread/thread/a99a5e606f6a8f38/b54521f82b9dd41a%23b54521f82b9dd41a?sa=X&oi=groupsr&start=1&num=3

"This is Dr. Codd's T-Join, which was introduced in his book on the second version of the relational model, which were based on the idea of a best fit or approximate equality."

Dr Codd's second paper can be found at

http://www.scism.sbu.ac.uk/~rmkemp/codd1979.pdf

http://groups.google.com/group/microsoft.public.sqlserver.programming/browse_thread/thread/a99a5e606f6a8f38/b54521f82b9dd41a%23b54521f82b9dd41a?sa=X&oi=groupsr&start=1&num=3

SQL = Scarcely Qualifies as a Language

teds-250959 Old Hand Points: 392 More actions · Answer 9

teds-250959

Old Hand

Points: 392

November 25, 2005 at 9:57 am

#605882

Thanks for the links!