Relational algebra question

relational-theory

Here is the relational schema given :

employee (person-name , street, city)
works (person-name, company-name, salary)
company (company-name, city)
manages (person-name, manager-name)

Q: Find the names of all employees who live in the same city and on the same street as do their managers.

I find the solution somewhere :

but solution seems wrong which is just after second natural-join sign there is no select statement sign and just after that sign, a predicate appears 0_o , in that, from where does that manager-name attribute comes from?. I am completely lost.

My solution seems to be long since I used the Cartesian-product , and the query is bit long (of which I'm not even sure it's right or wrong) 🙁

Best Answer

DISCLAIMER : Never Learned Relational Algebra but it looks interesting

From the schema given and your question, this is what the SQL should be:

SELECT
    emp_mgr.person_name
FROM
    manages emp_mgr
    INNER JOIN employee emp ON emp_mgr.person_name  = emp.person_name
    INNER JOIN employee mgr ON emp_mgr.manager_name = mgr.person_name
WHERE
    emp.street = mgr.street AND
    emp.city = mgr.city
;

Here is another query that only uses JOINs, no WHERE clause:

SELECT
    emp.person_name
FROM
    (SELECT A.person_name,B.street,B.city FROM manages A
    INNER JOIN employee B ON A.person_name = B.person_name) emp
    NATURAL JOIN
    (SELECT A.manager_name,B.street,B.city FROM manages A
    INNER JOIN employee B ON A.manager_name = B.person_name) mgr
;

The first query gets all employees who are managed and their managers in the form of a Cartesian Product. Then, it looks for a common street and city.

The second query collects personnel records (name,street,city) of employees and their managers and performs a NATURAL JOIN between the employess and their managers using (street,city).

If you can transalate both queries back to Relational Algebra, I think you will have what you are looking for. I believe the second may be of better help.

Related Solutions

Beginner questions about SQL and relational algebra

Your sql query is wrong:

- Assume there is a student s1 who has passed one exam 
  after '2000-01-01' and none before. 
  Your query results in {s1} - {} = {s1}. This will be a false positive.

- Assume there is a student s1 that passed three exams 
  after '2000-01-01' and one exam before. 
  Your query results in {s1} - {s1} = {}. This will be a false negative.

I'm having a bit of trouble reading your algebra expressions, but the first one looks ok. It should not matter that you do the selection (topic = "motorcycle") after the join instead of joining on the selection.

The second one can't be right. Assume there's a newspaper that published both an article on motorcycle and an article on something else. Your expression will pick the article on something else and therefore return that newspaper (incorrectly).

Relational Algebra Queries – How to Approach Problems

I think you're on the right track, but I'm not seeing a provision for restricting the results to employees who are actually working on two projects and the rename notation is confusing to me. You'll probably want to leverage a theta-join on a self join to accomplish this.

To start out, I would rename the relevant attributes in the work table in preparation for a self-join:

ρ_{sin/emp_sin,project_number1/project_number} works_on

Then project just those attributes for simplicity's sake:

π_{sin,project_number1} ( ρ_{sin/emp_sin,project_number1/project_number} works_on )

For visualization purposes, the equivalent SQL here would be something along the lines of:

SELECT  emp_sin 
            AS sin,
        project_number
            AS project_number1
FROM    works_on;

I'd then prepare for the self join by creating another relationship, renaming the project_number differently:

π_{sin,project_number2} ( ρ_{sin/emp_sin,project_number2/project_number} works_on )

At this point, a theta-join can be applied, exploiting the maximum of 2 carnality as defined in the assumption. This theta-join creates a relationship with both project_numbers by emp_sin:

( π_{sin,project_number1} ( ρ_{sin/emp_sin,project_number1/project_number} works_on ) ) ⋈_{sin, project_number1 < project_number2} ( π_{sin,project_number2} ( ρ_{sin/emp_sin,project_number2/project_number} works_on ) )

In effect, this is similar to SQL as follows:

SELECT  *
FROM (  SELECT  emp_sin 
                    AS sin,
                project_number
                    AS project_number1
        FROM    works_on ) AS w1
INNER JOIN (
        SELECT  emp_sin 
                    AS sin,
                project_number
                    AS project_number2
        FROM    works_on ) AS w2 
    ON  w1.sin = w2.sin
    AND w1.project_number1 < w2.project_number2;

The little exploit in the requirements here lets us do a natural join and a final projection to finish up ( since I've already renamed the emp_sin attribute to sin ):

π_{emp_name, project_number1, project_number2} ( employee ⋈ ( π_{sin,project_number1} ( ρ_{sin/emp_sin,project_number1/project_number} works_on ) ) ⋈_{sin, project_number1 < project_number2} ( π_{sin,project_number2} ( ρ_{sin/emp_sin,project_number2/project_number} works_on ) ) )

Again, as visual proof, this is approximately the equivalent of the following SQL, shown in action in this SQL Fiddle:

SELECT  e.emp_name, w1.project_number1, w2.project_number2
FROM    dbo.employee e
INNER JOIN (
        SELECT  emp_sin 
                    AS sin,
                project_number
                    AS project_number1
        FROM    dbo.works_on ) AS w1
    ON  e.sin = w1.sin
INNER JOIN (
        SELECT  emp_sin 
                    AS sin,
                project_number
                    AS project_number2
        FROM    dbo.works_on ) AS w2 
    ON  w1.sin = w2.sin
    AND w1.project_number1 < w2.project_number2;

Best Answer

Related Solutions

Beginner questions about SQL and relational algebra

Relational Algebra Queries – How to Approach Problems

Related Question