-3

We have 3-Relation:

Students(sid, sname)
Courses(cid, cname, dept)
take(sid, cid, grade)

Who Can Describe these relational algebra for me?

enter image description here

Is equivalent to second one: enter image description here

1 Answers1

1

The first expression is incorrect or undefined, according to the definition of most popular database books, since the second operand of the division should have attributes that are a subset of the attributes of the first operand (this first paragraph has been edited according to the comments below).

The second expression is a regular division that returns the sid of the students that have taken all the courses of 'CS'.

The third expression first calculates the cartesian product of all the sid of students with the cid of all the 'CS' courses, and from those set removes all the pairs (sid,cid) present in take. So, at the end, the set will contains the couples sid, cid where sid identifies a student a cid a 'CS' course not taken by that student. Finally this set is projected over sid, so that this expression returns all the students that did not taken all the 'CS' courses. In other words, the complement of the second expression.

Edited

The fourth expression is equivalent to the second one, and this is very easy to prove: consider that this expression is simply equal to:

πsid(students) - (the third expression)

and since the third expression returns the sid of all the students that did not taken all the 'CS' courses, subtracting this set from the sid of all the students we found again all (and only) the students that have taken all the 'CS' course. In other words, the complement of the complement, i.e. the original set obtained by the division, that is the second expression.

Renzo
  • 26,848
  • 5
  • 49
  • 61
  • Sorry I add another picture. how this is possible that the new picture is equivalent to second one ? it's complex fomula. –  Feb 14 '16 at 23:37
  • @LoveComplexity & Renzo Wikipedia is wrong. Codd's division R / S is defined on all pairs of relations & gives the same answer as for R / π common attributes (S). (See his [Relational Completeness paper](http://www.iai.uni-bonn.de/III/lehre/vorlesungen/Informationssysteme/WS05/materialien/Codd72a.pdf).) Date misunderstood and popularized the version with attributes of R a superset of S's. (See his [Database Explorations book Division chapter](http://www.dcs.warwick.ac.uk/~hugh/TTM/Database-Explorations-revision-2.pdf).) Definitions ok for Date's are not always ok for Codd's. So 1st = 2nd. – philipxy Feb 18 '16 at 04:57
  • @philipxy, thanks, this is very interesting, at least from historical point of view. However I think that the Date definition is what is used in current database courses, as a lot of database books testify, for instance: Molina-Ullman-Widom, Database Systems, 2nd ed, p.58; Ramakrishnan-Gehrke, Database Management Systems, 3rd ed., p.109; Silberschatz-Korth-Sundarshan Database System Concepts, 6th ed., p.250; Connolly-Bag, Database Systems, 4th ed., p.150; Abiteboul-Hull-Vianu, Foundations of Databases, 1995, p.99; Elmasri-Navathe, Fundamentals of Database Systems, 6th ed., p.163. – Renzo Feb 18 '16 at 08:38
  • @Renzo But the 1st expression has S's header *not* a subset of R's. So it is not using Date's version. And all those references, defining the Date version, like it are *undefined* in this case. Only Wikipedia allows for arbitrary relations, Codd's version, and it is confused. The actual reason why "it is usually required that the attribute names in the header of S are a subset of those of R" is it's Date's version. Not "because otherwise the result of the operation will always be empty" with Codd's version, because it won't. Rather, when there are no common attributes then the result is empty. – philipxy Feb 18 '16 at 10:31
  • @philipxy ok, thanks again, I will rephrase my answer, and so, maybe, you should consider correcting the Wikipedia page? – Renzo Feb 18 '16 at 10:46
  • Isn't the second one "all sid that have taken the course of CS"? rather than "the sid of the students that have taken all the courses of 'CS'." Maybe it is the same, I'm not native... – Revolucion for Monica Feb 19 '16 at 12:41
  • @Marine1, 'CS' is a department (for instance, Computer Science), that has many courses... So the query is "all sid that have taken *all* the courses of that department". This is the idea of the division operator, which has relation with the universal quantifier "all" (you can see this other [answer](http://stackoverflow.com/a/34979122/2382734), for instance). – Renzo Feb 19 '16 at 12:54
  • @Marine1 & Renzo: Actually division returns students who have taken all the courses of that department *and have taken at least one course*. The difference is, if that department doesn't offer any courses then students that have taken all the courses of that department include the students who have taken no courses but division doesn't. – philipxy Feb 22 '16 at 04:26