I'm reading the book "Fundamental of Database Systems" for a Database course and I'd need some directions.
I've tried hard to understand this from the book, but I can't wrap my mind around it, as I think it doesn't make sense from anything in logic I've learnt before. The author presents this query:
{e.Lname, e.Fname | EMPLOYEE(e) AND ((∀x)(NOT(PROJECT(x)) OR NOT (x.Dnum=5) OR ((∃w)(WORKS_ON(w) AND w.Essn=e.Ssn AND x.Pnumber=w.Pno))))}
And states that this equals to -> List the names of employees who work on all the projects controlled by department number 5.
I just can't see how.
In words, this is how I interepret the line query: All e's in the range of the Employee relation that's not part of any project in the range of the Project relation or where any x in the project relation does not equal to 5 ( NOT x.Dnum = 5) or where it exists some w in the WORKS_ON range that matches the ssn of the employee AND matches the Pnumber number of any project x.
What I don't understand here, is how to evaluate this. I'm thinking in programming terms, evalute left to right, if something is TRUE stop and the condition is TRUE. Basically with that logic, if I choose any project that does not have Dnum=5, the condition will be TRUE and we get the result that's not appropiate according to the sentence as we want to find the names of employees who work on all the projects controlled by department number 5. Please, could someone help me make sense of this? It just won't go in and I think it's because of lack of concrete examples.
EDIT: See my answer below and how I interpret this logically.
So finally with some help from the comments, I could understand this fully. I have seen others asked similar questions before and I will leave this here for them to save some time.
To solve this problem, let's do it step-by-step
Let's break the above query down into parts:
$F$ = EMPLOYEE(e) AND F1
$F_1$ = (∀x)(NOT(PROJECT(x)) OR NOT (x.Dnum=5) OR ((∃w)(WORKS_ON(w) AND $F_2$)
$F_2$ = (∃w)(WORKS_ON(w) AND w.Essn=e.Ssn AND x.Pnumber=w.Pno)
If you are a programmer like me, imagine a finite set of EMPLOYEE($e$) that you just do a for loop over, one at a time. When we are at the first $e$, we will only return that e IF AND ONLY IF $F_1$ returns TRUE.
When does F1 return TRUE? When ALL projects $x$ in condition F1 returns TRUE, else it will always return FALSE.
Imagine that F1 is a nested For loop, so for $e = 1$, we need to check every tuple in the universe (We can think of this as an infinite set minus our finite set), but fortunately because of how the query is written infinitely many of them (minus the finite ones we have) will turn to TRUE, so we don't even have to consider them at all. Because remember, in order for $∀x$ to return true, ALL $x$'s in the universe needs to satisfy this set. So what will happen, depending on the size of your finite set, is that maybe some project $x$ for some employee $e$ will be false and that will be enough for NOT returning that specific one employee i.e $F_1$ = FALSE.
So we check for every $x$ in the "infinite" set of tuples, where most will return TRUE because it's not part of the range PROJECT or it does not have the department attribute = 5. This leads to the final OR statement in those cases. As I said earlier, the logic here is that when looking at the expression, we can simply just exclude everything that's not in the range PROJECT($x$) and those that does not have the attribute of department = 5, because they are already TRUE.
Then when we get to the final OR statement $F_2$, now we can loop through the whole relation/set of WORKS_ON, but we can stop as soon as we find a $w$ that satisfy the expression. Because of $∃w$, we only need to find one $w$ that satisfy the condition.
To make an example of when this would return FALSE, let's say we have an employee, $e = 1$, and we are evaluating some arbitary project, by index $x = 6$ (of infinitely many). This project is part of department 5 AND is in the range PROJECT, this means that we will have 2 false before reaching $F_2$ for evaluation. Inside $F_2$, let's say we look through every $w$ and we can't find one with the project number $x$.Pnumber, that means that we will also get FALSE for $F_2$. Now we can stop the $F_1$ loop because, One FALSE = FALSE for the whole condition! (Remember that the $∀x$ "loop" will only evaluate to TRUE if all $x$'s are TRUE).
To make an example of when this would return TRUE, well, let's say that all $x$'s we have already evaluated have been TRUE and we are at the last $x$ (project tuple) in the loop $F_1$. If $x$ is in range of Project AND x.Dnum = 5, we have two false and must evaluate the last $F_2$. The project has the attribute Dnum = 5 and if this particular employee is assigned to this project in some $w$ (THERE EXISTS), we will return TRUE here. As this was the LAST $x$, the whole condition $F_1$ will finally return TRUE.
The condition is simply, the employee needs to be assigned to ALL projects when we reach this particular state with two falses first in $F_1$, so that $F_2$ always evaluate to TRUE. So to simplify things, exclude all the stuff we are not interested by the first NOT statements in $F_1$ in and check if every $x$ holds for the last condition $F_2$.