Relational Algebra Expression

Relational Algebra Expression

Post by gamehac » Mon, 11 Feb 2008 01:32:00


Hi,

I've been trying to figure out how to use relational algebra to
extract some data from the following relation:
<Year, Name, Votes> where the primary key is Year+Name (composite
key). A sample table could contain the following entries:
1999 | Joe | 34
1999 | James | 45
2000 | Mike | 24
2001 | George | 17
2001 | Josh | 69

What I'm trying to do is extract all the years where we have more than
1 relation for the year. For the sample table, we need to get:
1999
2001

I tried to do in a couple of ways but I couldn't. I tried using a
projection on Year so that I can remove duplicates but then I can't
just use difference because the new relations are not compatible. Any
hints are greatly appreciated.

Thanks,
g
 
 
 

Relational Algebra Expression

Post by Bob Badou » Mon, 11 Feb 2008 01:47:26


Equijoin on year and inequality theta-join on name project on year.

 
 
 

Relational Algebra Expression

Post by gamehac » Mon, 11 Feb 2008 01:59:43


Hi,

I can't really understand what this means - can you bracket it so I
can see the results of each operation?

Thanks very much,
g
 
 
 

Relational Algebra Expression

Post by Bob Badou » Mon, 11 Feb 2008 02:12:00


Read it left to right, like you would any other english sentence, and
think about the result after each operation. How many of each year will
you have after each step?

Ask yourself whether it works for "more than 1".
Ask yourself whether it generalizes to "more than n".

Then, think about how you would write it in whatever algebraic syntax
you are using.
 
 
 

Relational Algebra Expression

Post by JOG » Mon, 11 Feb 2008 07:16:38


Well Bob gave you everything you needed, but I guess you're learning
the stuff at the moment (coursework?) so lets break down his
instructions:

1) EQUIJOIN R with itself (renamed B) where Year = B.Year
2) RESTRICT where Name != B.Name
3) PROJECT on Year

In terms of whats going on:
1 - Gives you a relation of any two rows with the same year
concatenated together
2 - Removes the years that were joined with themselves in 1.
3 - Gets rid of all attributes apart from Year. Because a relation is
a set this also eliminates any duplicates, and voila you are left with
the years that appeared more than once.

Note if you use SQL it can allow duplicates (which is of course
particularly brain-dead given a relation is a set), so you have to
specify you want distinct tuples:

SELECT DISTINCT Year FROM R, R as B
WHERE R.Year = B.Year AND R.Name != B.Name
 
 
 

Relational Algebra Expression

Post by Bob Badou » Mon, 11 Feb 2008 07:30:58


He mentioned relational algebra. I figured he would have to rename
attributes instead. In D, I would use "rename all but year prepending
'other_'" or something similar. I don't think that 'B.' *** flies with
relations.
 
 
 

Relational Algebra Expression

Post by JOG » Mon, 11 Feb 2008 08:05:57


You see what being faced with SQL every day does to someone!? It
addles the brain. I should sue.

Out of interest, here is an equivalent procedural solution to the OP's
problem:

std::set<int> results;
std::set<row>::iterator i;
std::set<row>::iterator j;

for(i = R.begin(); i != R.end(); ++i)
{
for(j = i + 1; j != R.end(); ++j)
{
if ( (*i).year == (*j).year)
{
results.insert((*i).year);
break;
}
}
}

nice isn't it ;)
 
 
 

Relational Algebra Expression

Post by Bob Badou » Mon, 11 Feb 2008 09:19:18


It would be just peachy keen if it didn't have a bug.
 
 
 

Relational Algebra Expression

Post by JOG » Mon, 11 Feb 2008 10:08:41

n Feb 10, 12:19 am, Bob Badour < XXXX@XXXXX.COM > wrote:

Bugs!? Clean as a whistle I tell you.
 
 
 

Relational Algebra Expression

Post by Bob Badou » Mon, 11 Feb 2008 12:10:46

OG wrote:


Why, so you are right! It would be just peachy keen if it didn't look so
much like it had a bug then.