# Thread: New way to do a T-JOIN, anyone?

1. Registered User
Join Date
Jan 2013
Posts
359

## Unanswered: New way to do a T-JOIN, anyone?

Here is an old problem and I have several answers to it, but I have the feeling that teh newer features in SQL can get a better anwer. Anyone want to try it?

In the Second Version of the relationnal model in 1990, Dr. E. F. Codd introduced a set of new theta operators, called T-operators, which were based on the idea of a best-fit or approximate equality (Codd 1990). The algorithm for the operators is easier to understand with an example modified from Dr. Codd.

The problem is to assign the classes to the available classrooms. We want (class_size < room_size) to be true after the assignments are made. This will allow us a few empty seats in each room for late students.

The gimmick is that this is a bin-packing problem and such problems are known to be NP complete. And even worse, we can have more than one answer. We have to decide how we can limit the problem to something we can do. We can do this in one of two ways. The first way is to sort the tables in ascending order by classroom size and the number of students in a class. We start with the following tables:

CREATE TABLE Rooms
(room_nbr CHAR(3) NOT NULL PRIMARY KEY,
room_size INTEGER NOT NULL);

CREATE TABLE Classes
(class_nbr CHAR(3) NOT NULL PRIMARY KEY,
class_size INTEGER NOT NULL);
\
INSERT INTO Classes (class_nbr,class_size)
VAlUES ('c1',80),('c2',70),('c3',65),
('c4',55),('c5',50),('c6',40);

INSERT INTO Rooms (room_nbr,room_size)
VALUES ('r1',70), ('r2',40), ('r3',50),
('r4',85), ('r5',30), ('r6',65),
('r7',55);

The goal of the T-JOIN problem is to assign a class which is smaller than the classroom given it (class_size < room_size). Dr. Codd gives two approaches to the problem.

1) Ascending Order Algorithm

Sort both tables into ascending order. Reading from the top of the Rooms table, match each class with the first room that will fit.

room_nbr class_nbr room_size class_size
'r5' 30
'r2' 'c6' 40 40
'r3' 'c5' 50 50
'r7' 'c4' 55 55
'r6' 'c3' 65 65
'r1' 'c2' 70 70
'r4' 'c1' 85 80

2) Descending Order Algorithm

Sort both tables into descending order. Reading from the top of the Classes table, match each class with the first room that will fit.

room_nbr class_nbr room_size class_size
'r5' 30
'r2' 40
'r3' 'c6' 50 40
'r7' 'c5' 55 50
'r6' 'c4' 65 55
'r1' 'c3' 70 65
'r4' 'c1' 85 80

Notice that the answers are different! Dr. Codd has never given a definition in relational algebra of the T-Join, so I proposed that we need one. Informally, for each class, we want the smallest room that will hold it, while maintaining the T-JOIN condition. Or for each room, we want the largest class that will fill it, while maintaining the T-JOIN condition. These can be two different things, so you must decide which table is the driver. But either way, I am advocating a "best fit" over Codd's "first fit" approach.

Other theta conditions can be used in place of the "less than" shown here. If "less than or equal" is used, all the classes are assigned to a room in this case, but not in all cases. This is left to the reader as an exercise.

If you do a little arithmetic on the data, you find that we have 360 students and 395 seats, 6 classes and 7 rooms. Clearly if you have more studetns than chairs or more classes than rooms, they are not going to fit exactly.

2. World Class Flame Warrior
Join Date
Jun 2003
Location
Ohio
Posts
12,595
Your criteria that for each class be assigned to the smallest room that will hold it seems to conflict with the limitation (presuming the classes are simultaneous) that no classroom be assigned to more than one class.

3. Registered User
Join Date
Jan 2013
Posts
359
That was the assumption. The class is monolithic block; one class, one room; the class the whole class and nothing but the class. This is an old problem from Dr. Codd, based on bin packing problems. I have lots of answers from decades ago, but they did not use current SQL. The Croatian solution was a VIEW (now a CTE?) of the possible rooms for each class, followed by another VIEW of the best fit in the first view. Then some way to resolve conflicts.

4. World Class Flame Warrior
Join Date
Jun 2003
Location
Ohio
Posts
12,595
Then the criteria would be to assign each class to the smallest room not already occupied by another class.
I would think that the "Ascending Order Algorithm" you mentioned would satisfy this.

5. Resident Curmudgeon
Join Date
Feb 2004
Location
In front of the computer
Posts
15,579
This is a "first cut" because it won't deal with ties on either room or class size, but how about:
Code:
```IF Object_Id('Classes') IS NOT NULL
DROP TABLE Classes
GO

IF Object_Id('Rooms') IS NOT NULL
DROP TABLE Rooms
GO

CREATE TABLE Classes (
class_nbr    CHAR(3)     NOT NULL
PRIMARY KEY
,  class_size   INTEGER     NOT NULL);

INSERT INTO Classes (
class_nbr, class_size
)  VAlUES ('c1',80), ('c2',70)
,     ('c3',65), ('c4',55)
,     ('c5',50),('c6',40);

CREATE TABLE Rooms (
room_nbr     CHAR(3)     NOT NULL
PRIMARY KEY,
room_size    INTEGER     NOT NULL
);

INSERT INTO Rooms (room_nbr, room_size)
VALUES ('r1',70), ('r2',40)
,     ('r3',50), ('r4',85)
,     ('r5',30), ('r6',65)
,     ('r7',55);

; WITH cte1 AS (
SELECT room_nbr, room_size, class_nbr, class_size
,  Row_Number() OVER (ORDER BY room_size DESC, class_size DESC, room_nbr DESC, class_nbr DESC) AS rn1
FROM rooms
JOIN classes
ON (class_size <= room_size)
), cte2 AS (
SELECT room_nbr, room_size, class_nbr, class_size
,     Row_Number() OVER (PARTITION BY room_nbr ORDER BY rn1, class_nbr) AS rn2
FROM cte1
)
SELECT *
FROM cte2
WHERE 1 = rn2```
-PatP

6. Resident Curmudgeon
Join Date
Feb 2004
Location
In front of the computer
Posts
15,579
I'll need to give this some more work, but that won't be tonight... I have servers to baby-sit tonight. Let me know what you think of this:
Code:
```IF Object_Id('Classes') IS NOT NULL DROP TABLE Classes
IF Object_Id('Rooms') IS NOT NULL DROP TABLE Rooms
GO

CREATE TABLE Classes (
class_nbr    CHAR(3)     NOT NULL       PRIMARY KEY
,  class_size   INTEGER     NOT NULL);

CREATE TABLE Rooms (
room_nbr     CHAR(3)     NOT NULL       PRIMARY KEY,
room_size    INTEGER     NOT NULL);
GO

INSERT INTO Classes (
class_nbr, class_size
)  VAlUES ('c1', 80), ('c2', 70)
,     ('c3', 65), ('c4', 55)
,     ('c5', 50),('c6', 40);

INSERT INTO Rooms (room_nbr, room_size)
VALUES ('r1', 70), ('r2', 40)
,     ('r3', 50), ('r4', 85)
,     ('r5', 30), ('r6', 65)
,     ('r7', 55);

-----

; WITH classes_cte AS (
SELECT class_nbr, class_size
,  Row_Number() OVER (ORDER BY class_size DESC, class_nbr) AS classes_rn
FROM Classes
), rooms_cte AS (
SELECT room_nbr, room_size
,  Row_Number() OVER (ORDER BY room_size  DESC, room_nbr) AS rooms_rn
FROM Rooms
), class_fit_cte AS (
SELECT room_size, class_size, room_nbr, class_nbr, classes_rn, rooms_rn
,  Row_Number() OVER (PARTITION BY rooms_rn ORDER BY classes_rn) AS pick_rn
FROM rooms_cte
JOIN classes_cte
ON (class_size <= room_size)
)
SELECT a.*
FROM class_fit_cte AS a
WHERE  1 = pick_rn```
-PatP

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•