Results 1 to 6 of 6
  1. #1
    Join Date
    Jan 2013
    Posts
    354
    Provided Answers: 1

    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. #2
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Provided Answers: 1
    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.
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

  3. #3
    Join Date
    Jan 2013
    Posts
    354
    Provided Answers: 1
    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. #4
    Join Date
    Jun 2003
    Location
    Ohio
    Posts
    12,592
    Provided Answers: 1
    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.
    If it's not practically useful, then it's practically useless.

    blindman
    www.chess.com: "sqlblindman"
    www.LobsterShot.blogspot.com

  5. #5
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    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
    In theory, theory and practice are identical. In practice, theory and practice are unrelated.

  6. #6
    Join Date
    Feb 2004
    Location
    In front of the computer
    Posts
    15,579
    Provided Answers: 54
    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
    In theory, theory and practice are identical. In practice, theory and practice are unrelated.

Posting Permissions

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