Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 

Celko's SQL Stumper: The Class Scheduling Problem

By Joe Celko,

What can we use in SQL instead of E. F. Codd's T theta operators for best-fit? Joe Celko returns with another puzzle that isn't new, in fact it already features “Swedish”, “Croatian” and “Colombian” solutions in chapter 17 of Joe's 'SQL for Smarties' book. These were all written before CTEs or the new WINDOW functions. Is there now a better solution? Was there one even then?  We leave it to the readers to provide the answer!

In the book “The Relational Model, Version Two” (1990, ISBN13: 978-0201141924), 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. The name never caught on and nobody invented special syntax for them.

One problem is that they were defined by a procedural algorithm and not a set-oriented definition. It 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. 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 simplified tables:

CREATE TABLE Rooms

(room_nbr CHAR(2) NOT NULL PRIMARY KEY,

 room_size INTEGER NOT NULL

  CHECK (room_size > 0));

 

CREATE TABLE Classes

(class_nbr CHAR(2) NOT NULL PRIMARY KEY,

 class_size INTEGER NOT NULL

  CHECK (class_size > 0));

These tables have the following rows in them:

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 in ascending order. Reading from the top of the Rooms table, match each class with the first room that will fit.

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

This gives us ...

Results
class_nbr class_size room_nbr room_size
=======================================
'c2'      70         'r4'     85
'c3'      65         'r1'     70
'c4'      55         'r6'     65
'c5'      50         'r7'     55
'c6'      40         'r3'     50

2) Descending Order Algorithm

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

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

and ...

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

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 almost fill it, while maintaining the T-JOIN condition. These can be two different things, because these are not "best fit" solutions "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. Nor is the solution always unique. Here is a (class_size <= room_size) answer for this data. Room 'r5' is too small to match any class.

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

In the third edition of SQL FOR SMARTIES, I gave “Swedish”, “Croatian” and “Colombian” solutions, named for the countries of the submitters. They were all written without CTEs or the new WINDOW functions (that is the technical name for the OVER() clause on aggregate functions). Obviously, if two rooms or two classes are the same size, they can be swapped with each other. Let's make life easier by adding a UNIQUE constraint to room_size and class_size.

The problem is write an SQL statement that gives a T-Join.

WARNING: some of you already know this, but finding an optimal solution is an NP-complete problem. The bigger the data set gets, the effort it takes to solve the problem increase beyond any reasonable limit. You can Google for "Knapsack Problem" or  "Bin Packing Problem" if you want the details.

The best answer to each stumper will be given a prize of a $100 Amazon voucher. The stumper will be run simultaneously on SQL Server Central and Simple-Talk. To see all the comments so far, you will need to visit both sites.

 We will take entries for a week after the first Monday of publication, posted as comments to the articles.

Two weeks after the challenge is sent out, the judge's decision and comments will be sent out in the newsletter, and published on the site. Joe Celko and Phil Factor will judge the answers to this puzzle. Your answer should :Your answer should :

  1. Solve the problem -- Duh!
  2. Avoid proprietary features in SQL Server that will not port or be good across all releases, present and future.
  3. Use Standard features in SQL Server that will be good across all releases, present and future. Extra points for porting code.
  4. Be clever but not obscure.
  5. Explain how you got your answer.
Total article views: 1581 | Views in the last 30 days: 2
 
Related Articles
BLOG

First Foundation Class Review

The first Pragmatic Works Foundation class concluded today and I think it was a great success!  Each...

ARTICLE

Bring Solutions

In today's world, technology workers need to point out solutions, not problems.

BLOG

SSIS Training class by Andy Leonard

    Andy Leonard (b | t | l | f) of Linchpin People, has announced a new training class called ...

ARTICLE

Data Archiving: Problems and Solutions

SQL Server does an exceptional job at managing your data and making it available for your users and ...

FORUM

Auto Answer

Auto answer for popular problems

 
Contribute

Join the most active online SQL Server Community

SQL knowledge, delivered daily, free:

Email address:  

You make SSC a better place

As a member of SQLServerCentral, you get free access to loads of fresh content: thousands of articles and SQL scripts, a library of free eBooks, a weekly database news roundup, a great Q & A platform… And it’s our huge, buzzing community of SQL Server Professionals that makes it such a success.

Join us!

Steve Jones
Editor, SQLServerCentral.com

Already a member? Jump in:

Email address:   Password:   Remember me: Forgotten your password?
Steve Jones