File Structures
HEURISTIC OPTIMIZATION
Trainee(SSN, I_SSN, Name)
Instructor(I_SSN, Name)
Department(DNO, I_SSN)
A trainee has one instructor; each department is managed by only one instructor.
Context: 1000 trainees; 100 instructors (1 per 10 trainees); 50 departments.
SELECT S.NAME
FROM TRAINEE S, INSTRUCTOR I, DEPARTMENT D
WHERE S.I_SSN = I.I_SSN
AND I.I_SSN = D.I_SSN AND D.DNO = 5
1
HEURISTIC OPTIMIZATION
Context: 1000 trainees; 100 instructors (1 per 10 trainees); 50 departments.
Solution 1: (without the intermediate projections)
πS.NAME(TRAINEE S.I_SSN = I.I_SSN
(INSTRUCTOR I.I_SSN=D.I_SSN (σD.DNO=5DEPARTMENT)))
Step 1: search over 50 department; Find 1 (No. 5)
Step 2: search over 100 instructors; Find 1 (manager of Dept No. 5)
Step 3: search over 1000 trainees; Find up to 10 (whose instructor is manager of
Dept No.5)
2
HEURISTIC OPTIMIZATION
Context: 1000 trainees; 100 instructors (1 per 10 trainees); 50 departments.
Solution 2: (without the intermediate projections)
πS.NAME (σD.DNO=5DEPARTMENT) D.I_SSN=D.I_SSN (TRAINEE S.I_SSN = I.I_SSN INSTRUCTOR)
Step 1: find the instructors for all trainees; 1000 (trainee-instructor) pairs
Step 2: find the Dept. 5; 1 tuple
Step 3: search over the 1000 pairs the 10 trainees whose instructor is manager of Dept
No.5
3
4
Solution 1 with the intermediate projections
HEURISTIC OPTIMIZATION
Context: 1000 trainees; 100 instructors (1 per 10 trainees); 50 departments.
SELECT S.NAME
FROM TRAINEE S, DEPARTMENT D
WHERE S.I_SSN = D.I_SSN AND D.DNO = 5
πS.NAME(TRAINEE S.I_SSN=D.I_SSN (σD.DNO=5DEPARTMENT)))
5
SELECT S.NAME
FROM TRAINEE S, INSTRUCTOR I, DEPARTMENT D
WHERE S.I_SSN = I.I_SSN
AND I.I_SSN = D.I_SSN AND D.DNO = 5
HEURISTIC OPTIMIZATION
Context: 1000 trainees; 100 instructors (1 per 10 trainees); 50 departments.
Solution 3: (without the intermediate projections)
πS.NAME(TRAINEE S.I_SSN=D.I_SSN (σD.DNO=5DEPARTMENT)))
Step 1: search over 50 department; Find 1 (No. 5)
Step 2: search over 1000 students; Find up to 10 (whose instructor is manager of
Dept No.5)
6