0

Consider a table of employee IDs at a restaurant and the shifts that they work. If I have a data scheme given as Shifts(ShiftID, EmployeeID) where Shift and EmployeeID together form a key for the relation, how can I find all of the pairs of employees that only ever work together. That is, I want the tuples (A, B) and (B, A) if employee A works only when employee B works and viceversa.

Is this possible with basic relational algebra operators (select, project, cross product, natural join, rename) and set operations (union, intersect, difference)?

Sample input:

Shift Employee

1 A

1 B

2 A

2 B

3 C

Expected output

Employee1 Employee2

A B

B A

My attempt:

First take the cross product of Shifts and select all the tuples where the ShiftID is the same but the EmployeeID differs (i.e. get all the pairs of employees working the same shift).

Then I tried taking the cross product of the above resulting relation with itself and choosing the tuples where the ShiftID is the same, the first EmployeeID is the same but the second EmployeeID differs. I was trying to get the "DifferentPairs" so I then select the first EmployeeID in the first copy and the second Employee ID in the second copy.

But then I got stuck because I realized that Pairs = DifferentPairs for employees with more than 1 pair since my second cross product could have employees (A, B | A, C) and (A, C | A, B) and so if I take the 1st and 4th IDs, I get (A, C) and (A, B) and now I'm back where I started (Not in the example I gave but just in general).

unicorn407
  • 21
  • 3
  • Look for useful queries. If x & y only ever work together, what are the people they don't work with, and if you knew z & w's sets of people they do & don't work with, how could that help you decide whether they only work together? PS This is likely a duplicate because you probably aren't the first person to ask it, right? Please also act on hits googling 'stackexchange homework'--show what you can do. PS [Re relational querying.](https://stackoverflow.com/a/24425914/3404097) – philipxy Oct 21 '18 at 04:46
  • I'm having difficulty using your advice because of the added Shift attribute. I'll update my post with my previous attempt. – unicorn407 Oct 21 '18 at 06:15
  • There are many different relational algebras--with different operators & notions of "relation". You must give yours--your textbook name & edition & where in it. PS My last comment begins by suggesting an ad hoc exploration but the PS gives the correct mostly mechanical approach to relational querying that [I'll have to quote in an answer](https://stackoverflow.com/search?q=user%3A3404097+%5Brelational-algebra%5D). So where do you get using it? I'll start: T is rows where "employee E works shift S"--shorthand T(E,S). rename E\E1 T is rows where "employee E1 works shift S"-- T(E1,S). You finish. – philipxy Oct 21 '18 at 08:33
  • I'm going to make a general suggestion for you. The sample data you gave is overly simplistic, and doesn't reveal the sort of edge cases which precisely your homework assignment it trying to flesh out. So, I suggest creating sample data which includes things like more than 2 employees working for one shift, with both positive and negative cases. Then, stare at that data for a while until it starts to click. – Tim Biegeleisen Oct 21 '18 at 13:41
  • I can't make sense of your comment re shifts even after your edit. In explaining your browsing queries, give each one in algebra & name its result & say what its tuples state in terms of the business and/or the base relations. (Ie give their predicates.) This gives you relations you can use to get others. (Although this is moot if you clearly state the input & output predicates per my link.) The clear statement of what rows are in a relation--without reference to algebraic operators--is key. And again: Give a reference to your algebra. – philipxy Oct 23 '18 at 00:04

1 Answers1

0

if employee A works only when employee B works and viceversa.

So we want to compare the set of shifts that A works in to the set that B works in.

Then it's good to use Relational Algebra, because relations are sets. Using SQL would be hard: tables are not sets (in general) and SQL has limited potential for set operators.

You don't mention which variety of RA you're using. So I'll take Tutorial D from Date & Darwen's text books. In particular the GROUP operator to project on a relation, holding the values from one of its attributes as a set. We'll put that in a a temp relation variable:

WITH ShiftSet := Shifts GROUP { ShiftID AS ShiftSet }

(That in effect groups by EmployeeID, so we'll get one tuple per Employee, with that Employee's shifts as a set in attribute named ShiftSet.)

Then we pair up Employee tuples with the same ShiftSet value; via the usual trick of a self-join (needing a rename)

ShiftSet JOIN (ShiftSet RENAME {EmployeeID as EmpID2})
WHERE EmployeeID NOT = EmpID2
{ALL BUT ShiftSet}

The WHERE condition is to weed out Employee tuples joined to themselves. The trailing {ALL BUT ...} is to project away the ShiftSet, so we get pairs of {EmployeeID, EmpID} as the result.

Is this possible with basic relational algebra operators?

Yes it's possible with the ones you list. Philipxy's first comment gives you the hints. You're essentially doing a relational divide: see wikipedia for an equivalent formulation with those operators. That's leading you to a variety of RA crippled so it doesn't embarrass SQL.

AntC
  • 2,623
  • 1
  • 13
  • 20