Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

 All Forums
 SQL Server 2000 Forums
 SQL Server Development (2000)
 Recursive problem seems impossible in SQL

Author  Topic 

AskSQLTeam
Ask SQLTeam Question

0 Posts

Posted - 2002-03-14 : 09:20:04
Nick Gilbert writes "Hi,

I've got an unusual and difficult problem that I have no idea how to solve.

Basically, I have a database of Conference Venues. Venues have many rooms (average: 5) which can be set up in 4 different ways (Classroom, Boardroom, Theatre and U-Shape). A particular room will have 4 different capacities listed depending on how it is set up. My client wishes the users to be able to specify room requirements and the web site will find venues that have suitable matching rooms. They can specify multiple rooms using 5 drop downs and a free-text capacity field:

eg:
Classroom 100 people
Classroom 100 people
Classroom 200 people
Boardroom 20 people

My problem: It seems to be impossible to code a suitable query in SQL that can find a particular venue with a set of rooms that matches these criteria. The only way that we even vaguely worked was very inefficient and was far too slow to use on the website (there are 6000 venues with 30,000 rooms between them).

I can't think of a way of, for each venue, seeing whether it's rooms fulfill the various requirements.

I'm not sure whether I've described my problem well enough, but if anyone is interested in helping, I can answer any questions or send you some sample data.

Rooms capacities are stored in this table and are one to one mapped back to a Rooms table, which in turn has a one to many mapping back to a Venues table.

CREATE TABLE [dbo].[Meetingroom_capacity] (
[foreignKey] [int] NOT NULL ,
[capacityBoardroom] [int] NULL ,
[capacityClass] [int] NULL ,
[capacityTheatre] [int] NULL ,
[capacityUshape] [int] NULL
)
I'm using SQL 2000 on a dual 1.4GHz Dell server.

Thanks,

Nick Gilbert"

AndrewMurphy
Master Smack Fu Yak Hacker

2916 Posts

Posted - 2002-03-14 : 12:49:42
in order to prompt the "if anyone is interested in helping, I can answer any questions or send you some sample data", the 2nd part of this should be done.....


sample data, and sample results are often the fastest way to get the readers here interested in an esoteric problem like this.


Go to Top of Page

Jay99

468 Posts

Posted - 2002-03-14 : 13:39:41
I am not 100% clear on what data you want to extract? They way I read it, there is nothing 'Recursive' here. Maybe some clearer details would help.

Anywho . . . A shot in the dark
I am going to assume your foreignKey (very catchy name) field references a 'roomid' in your 'rooms' table and there is also a 'roomname' in there . . .


declare @roomtype varchar(something),
@capacity int

-- your first example under the 'eg:'
-- you would replace these with the input parms from your proc
select @roomtype = 'classroom', @capacity = 100

select
r.roomname
from
rooms r
inner join Meetingroom_capacity c
r.roomid = c.foreignkey
where
(@roomtype = 'Classroom' and c.CapacityClass = @capacity) or
(@roomtype = 'Boardroom' and c.CapacityBoard = @capacity) or
(@roomtype = 'Theatre' and c.CapacityTheatre = @capacity) or
(@roomtype = 'U-Shape' and c.CapacityUShape = @capacity)



Jay
Go to Top of Page

nmg196
Yak Posting Veteran

70 Posts

Posted - 2002-03-15 : 07:20:26
OK, I don't think I've explained myself clearly:

The users need to be able to specify multiple rooms. Ie they may know that they need two "Classrooms" of 100 people and a Boardroom of 30 people. Here's the form:



The data is stored like this:



If the user was only allowed to specify one room of one type, then the problem would be very simple. The problem is matching a list of rooms to a list of rooms in the database without actually reusing rooms. I mean there's no way to describe that scenario in SQL. You can't say "give me all venues where the venue has 3 different rooms matching these criteria".

In response to the guy above, yes - some of the field names are silly - and so is the format of the database in general, but I can't change it, so I just need to work with it how it is.. It's not *too* bad!

And yes, maybe "recursive" isn't the right word, but you do somehow need to remember which rooms you've allocated already while trying to fulfill the criteria if you see what I mean? Ie in my example screen shot above, the server needs to find a venue that has 3 seperate rooms in the Meeting_rooms table - all of which fulfill the capacity criteria specified on the form.

I think any algorithm would go along the following lines:
Order the criteria by size (ascending) and try and fulfill the smallest room first. Then try and find a venue that also has the second room of sufficient capacity and then the third... Then only return the venues that were able to fulfill all three (in this example) room criteria.

Here's some sample data in zipped CSV format in case anyone is interested in helping:

[url]http://www.nickgilbert.com/temp/VenueDB.zip[/url]


CREATE TABLE [dbo].[Meeting_Rooms] (
[primaryKey] [int] NOT NULL ,
[foreignKey] [int] NULL ,
[facilities] [ntext] NULL ,
[floor] [nvarchar] (20) NULL ,
[lightingText] [nvarchar] (20) NULL ,
[lightingType] [nvarchar] (200) NULL ,
[meetroomName] [nvarchar] (30) NULL ,
[order] [int] NULL ,
[suite] [nvarchar] (30) NULL
)


CREATE TABLE [dbo].[Meetingroom_capacity] (
[foreignKey] [int] NOT NULL ,
[capacityBoardroom] [int] NULL ,
[capacityClass] [int] NULL ,
[capacityTheatre] [int] NULL ,
[capacityUshape] [int] NULL
)


Thanks!

Nick...
Go to Top of Page

AndrewMurphy
Master Smack Fu Yak Hacker

2916 Posts

Posted - 2002-03-15 : 07:32:14
why not step back a bit and treat it as 5 seperate problems....

ie select * from roomsavailable where roomid not in (listofroomsalreadyreserved) and roomsize suits requirement.

(excuse the pseudo-sql....but you should get what i'm describing)

each time you execute the query, the listofroomsalreadyreserved grows in size to add the last room reserved...on first execution, there would be nothing in the list (or maybe for consistancy/simplicity a roomid which can never exist but which will ensure the list always has 1 entry ('cause having none is a pain to dealt with))


so what you will end up with is

start loop
findroomsuitable (excluding rooms already marked as suitable)
add new room to reserved/to-be-excluded list
end loop

you suggest that "If the user was only allowed to specify one room of one type, then the problem would be very simple"...why make it complicated and try to do it in one go....5 x simple solution, may be a lot simpler(+faster) than 1 x complex solution.

Go to Top of Page

nmg196
Yak Posting Veteran

70 Posts

Posted - 2002-03-15 : 07:47:24
I started going that way, but soon got stuck. Your "findroomsuitable" function from your last block of pseudocode is non trivial; You're not just trying to find a suitable room, you're trying to find the smallest suitable room per venue, as eventually you need a list of Venues that match your criteria, rather than a long list of suitable rooms.

Ie, it's intended that the user uses this form to find a list of venues that can fulfill all of the rooms requirements at once. Basically, I'm going to need a query or stored procedure that returns a list of venue IDs of venues.

Now the only way I can think of doing that is to either copy the big matrix of room capacities into a main memory 2D array and flag which rooms have been used, while doing some very complex nested looping or somehow using temp tables, stored procedures and cursors to do the same thing in SQL Server. Unfortunately my knowledge of cursors and stored procedures isn't too great and I think this is quite a difficult problem.

Thanks,
Nick...

Go to Top of Page

Jay99

468 Posts

Posted - 2002-03-15 : 08:19:37
I think this proc will do it for you . . . pass in as many rooms as you like, just make sure the lists line up. You will probably want to inject some good error handling and some logic to make sure the room isn't already reserved.


-- usp_multiroom 'Boardroom,Boardroom,Classroom', '30,100,150'
create procedure usp_multiroom
@roomlist varchar(1000), --comma seperated list of desired rooms
@delegateslist varchar(1000) --comma seperated list of desired delegates
-- (should match 1for1 with @roomlist)
as

create table #reservations ( --temp table to hold processed lists
resid integer identity(1,1),
room varchar(50),
del smallint,
mtgroom int
)


declare @separator_position_room int,
@separator_position_del int,
@array_value_room varchar(50),
@array_value_del varchar(50),
@resid int,
@maxresid int


--*****************************************************************************
--Step 1: parse the parm lists
-- note: if you are on 2k, you should make this generic and put it in a
-- UDF . . .
--*****************************************************************************

select @roomlist = @roomlist + ','
select @delegateslist = @delegateslist + ','

while patindex('%,%', @roomlist) <> 0
begin
select @separator_position_room = patindex('%,%', @roomlist)
select @separator_position_del = patindex('%,%', @delegateslist)
if @separator_position_del = 0
print 'Do some error handling'


select @array_value_room = left(@roomlist, @separator_position_room-1)
select @array_value_del = left(@delegateslist, @separator_position_del-1)

insert #reservations (room, del)
values(@array_value_room, convert(smallint, @array_value_del))

select @roomlist = stuff(@roomlist, 1, @separator_position_room, '')
select @delegateslist = stuff(@delegateslist, 1, @separator_position_del, '')

end

--*****************************************************************************
--Step 1: match up the desired reservations with a meeting room
--*****************************************************************************

select
@resid = 1,
@maxresid = max(resid)
from
#reservations

while @resid <= @maxresid
begin

update #reservations
set mtgroom = (
select
min(mr.primarykey)
from
Meeting_rooms mr
inner join Meetingroom_capacity mc
on mr.primarykey = mc.foreignkey
inner join #reservations r
on ((r.room = 'Classroom' and mc.CapacityClass = r.del) or
(r.room = 'Boardroom' and mc.CapacityBoardroom = r.del) or
(r.room = 'Theatre' and mc.CapacityTheatre = r.del) or
(r.room = 'U-Shape' and mc.CapacityUShape = r.del))
where
resid = @resid and
not exists (
select 1
from
#reservations
where
mtgroom = mr.primarykey) )
where
resid = @resid

set @resid = @resid + 1
end

select *
from #reservations

drop table #reservations

go



Jay

edit: I was still typing while the last two post came in, so I missed the importance of the venues . . . however, you should be able to modify the last update statement and the temp table to grab the venue id. Also, you may want to modify the update statement to get the smallest room available rather than an exact match on number of delegates . . . Anyway, I hope the proc helps.

Edited by - Jay99 on 03/15/2002 08:22:27
Go to Top of Page

nmg196
Yak Posting Veteran

70 Posts

Posted - 2002-03-15 : 09:03:40
Thanks very much for your help Jay, but your solution doesn't tackle the somewhat complex problem of matching all rooms at once, which is the main issue I have. It's a shame our messages crossed paths :)

I'm still thinking, but I don't think I'm going to get anywhere because neither my brain nor my knowledge of SQL2000 are really up to the job!

One idea I had, is to create a view, which is ordered by VenueID and then each of the room types that the user selected. (eg, VenueID, Boardroom, Classroom) but making sure that the smallest room is the first type in the list. Then perhaps you could pick the first matching room per venue, and then try and match the rest, ignoring the one you just allocated... somehow!! That's the difficult bit.

My brain hurts!

Thanks,
Nick...

Go to Top of Page

Jay99

468 Posts

Posted - 2002-03-15 : 09:09:03
quote:

...but your solution doesn't tackle the somewhat complex problem of matching all rooms at once, which is the main issue I have....
Thanks,
Nick...



OK, I am completely lost then. You are passing in two comma-sep lists into this proc and it gives a matching room for each roomtype/capacity combo . . . all at once. It won't pick the same room for two roomtype/capacity pairs ... You can mark up the proc to actually do the reservation, I didn't have your reservation schema.

<throwing-in-towel>Best of luck to you . . .</throwing-in-towel>

Jay
Go to Top of Page

Jay99

468 Posts

Posted - 2002-03-15 : 09:36:14
quote:

quote:

...but your solution doesn't tackle the somewhat complex problem of matching all rooms at once, which is the main issue I have....
Thanks,
Nick...



OK, I am completely lost then. You are passing in two comma-sep lists into this proc and it gives a matching room for each roomtype/capacity combo . . . all at once. It won't pick the same room for two roomtype/capacity pairs ... You can mark up the proc to actually do the reservation, I didn't have your reservation schema.

<throwing-in-towel>Best of luck to you . . .</throwing-in-towel>

Jay



Alright, I am taking the towel back . . . I see the problem, gimme a minute . . .

Jay
Go to Top of Page

Jay99

468 Posts

Posted - 2002-03-15 : 09:39:02
can you gimme the ddl for the venues table and add some sample data to your zip?

Jay
Go to Top of Page

AndrewMurphy
Master Smack Fu Yak Hacker

2916 Posts

Posted - 2002-03-15 : 09:47:08
i wasn't suggesting that your find1room code was trivial...as per your comment...

"Your "findroomsuitable" function from your last block of pseudocode is non trivial;"


you did state "If the user was only allowed to specify one room of one type, then the problem would be very simple" and I took this to mean if you were only looking for 1 room, the solution was straightforward. I was then suggesting that you repeat this simple solution, provided that you managed the alreadyusedrooms....and also kept track of the requirement that selected rooms be in the same venue. (I can now see that you would run into problems if a venue which could satisfy "room need#1", then failed to satisfy "room need#2".....then that venue needs to be excluded altogether and start back at the beginning on the next venue)


I wonder if this problem isn't a recursive one but more a travelling-saleman type problem....evaluate all combinations and find most suitable one?



what if you work backwards?....find all venues which satisfy the 'I need x number of rooms" criteria, for each of these ensure the rooms are suitable for the criteria given, then check that the selection of rooms is unique.


rather than try to build up a list of suitable rooms, why not trim down a list of "all rooms" by excluding unsuitable venues, etc?



I'm acting as devil's advocate here or even suggesting a bit of lateral-thinking.

Go to Top of Page

nmg196
Yak Posting Veteran

70 Posts

Posted - 2002-03-15 : 10:06:39
Here's an example that's as clear as I can get it:

Here's a list of capacities/rooms/venues:


SELECT Meeting_Rooms.foreignKey AS VenueID,
Meeting_Rooms.primaryKey as RoomID,
capacityBoardroom, capacityClass
FROM Meeting_Rooms
INNER JOIN Meetingroom_capacity ON Meeting_Rooms.primaryKey = Meetingroom_capacity.foreignKey
WHERE (NOT (capacityBoardroom = 0)) AND (NOT (capacityClass = 0))
ORDER BY Meeting_Rooms.foreignKey, capacityBoardroom, capacityClass



VenueID RoomID capacityBoardroom capacityClass
----------- ----------- ----------------- -------------
22 2204 16 18
22 2207 20 20
22 2201 20 25
22 2202 20 25
22 2203 20 35
23 2301 52 60
24 2403 36 36
24 2402 80 130
24 2401 120 150
27 2701 40 60
28 2807 30 45
28 2806 50 50
28 2805 60 60
29 2904 24 12
29 2905 24 12
29 2906 24 12
29 2903 30 40
29 2901 70 120
29 2902 70 120
30 3005 14 10
30 3007 14 14
30 3006 20 50
30 3003 30 50
30 3004 30 50
30 3002 50 100


(the WHERE clause is just to make this list shorter as there are loads of small boardrooms where all the other capacities are set to 0)

So, the user specifies:
Boardroom 20
Classroom 100
Classroom 120

...of the above (very cut!) dataset, the only venues that can match all three rooms are 24,29 and 30.

Does this make sense, or am I further confusing everyone? :)

You shouldn't actually *need* the venues table to solve this problem as all that's required are the venue IDs. But here is the DDL - let me know if you really need some sample data - and I'll dump out a couple of thousand rows:


CREATE TABLE [dbo].[Venue] (
[primaryKey] [int] NOT NULL,
[addressLine1] [nvarchar] (75) NULL,
[addressLine2] [nvarchar] (75) NULL,
[associationNames] [ntext] NULL,
[bedroomFacilities] [ntext] NULL,
[conferenceEquipment] [ntext] NULL,
[country] [nvarchar] (30) NULL,
[county] [nvarchar] (28) NULL,
[displayType] [nvarchar] (4) NULL,
[email] [ntext] NULL,
[equipDescription] [ntext] NULL,
[fax] [nvarchar] (70) NULL,
[groupIDs] [nvarchar] (3) NULL,
[placesofInterest] [ntext] NULL,
[postcode] [nvarchar] (8) NULL,
[region] [nvarchar] (28) NULL,
[tel] [nvarchar] (74) NULL,
[town] [nvarchar] (30) NULL,
[URL] [ntext] NULL,
[venueFacilities] [nvarchar] (75) NULL,
[venueName] [nvarchar] (75) NOT NULL,
[venueStyle] [ntext] NULL
)


Thanks for helping by the way guys - because I really am stuck here and I do appreciate your comments/ideas! :)

Nick....

Edited by - nmg196 on 03/15/2002 10:07:44
Go to Top of Page

AndrewMurphy
Master Smack Fu Yak Hacker

2916 Posts

Posted - 2002-03-15 : 11:23:22
reverting to SET theory, what if you built seperate queries for each requirement....and then work on getting the intersection of the result sets?


set A...satisfies boardroom capacity 20
set B...satisfies classroom capacity 100
set C...satisfies classroom capcaity 120



what you want then to get is items in A,B and C who have a common venue?


(don't know how to post graphics here....so excuse the crude drawings.)
AAAAA BBBBBBB
A BAA B
A B A B
A BCCCCCA B
A C BXXA C B
A C BAA C B
ACAAA BBBBBCB
C C
CCCCC


so basically you are interested in the items XX above....would have to put in some code to remove the rooms suitable for 2 uses (or more importantly, decide which use is more valid - ie if a room is suitable for a conferance and a boardroom, which would the client be more interested in?....provided other rooms can be found in the same hotel to satisfy the other requirements)

Go to Top of Page

joldham
Wiseass Yak Posting Master

300 Posts

Posted - 2002-03-15 : 11:53:06
If you could upload a zip with the tables and a few rows, that would be great. Just started looking at the post and I have an idea, but as you probably know it is rather intensive. I am pretty sure I can get it to work, but it may be tomorrow as I am at work right now.

I would give a synopsis, but I would have to write a book and I want to make sure I am not missing something. This is definitely something that I would want to test before giving any code.

Jeremy

Go to Top of Page

Jay99

468 Posts

Posted - 2002-03-15 : 11:54:55
quote:

[Alright, I am taking the towel back . . . I see the problem, gimme a minute . . .

Jay



I have a working solution, but I am doing a few more tweaks . . . (man this is killing my day :) )

Jay

Edit: I have got the thing finding a venue that matches all given criteria, but the trick is finding the BEST venue . . .


Edited by - Jay99 on 03/15/2002 11:56:21

Edit(again): There is going to be a big precision/performance tradeoff . . .


Edited by - Jay99 on 03/15/2002 11:58:13
Go to Top of Page

ToddV
Posting Yak Master

218 Posts

Posted - 2002-03-15 : 11:56:33
I have a solution too, but it is pretty bad. I will wait to see yours.

Go to Top of Page

joldham
Wiseass Yak Posting Master

300 Posts

Posted - 2002-03-15 : 12:00:18
If Jay comes up with the solution, I won't spend the hour or so I think I will need and I am sure you won't want to waste your time loading exporting some tables.

Jay, does your solution use cursors or did you figure out a setbased solution?

Jeremy

Go to Top of Page

Jay99

468 Posts

Posted - 2002-03-15 : 12:00:27
Here is where I am. But there are problems.

1. It is possible, because of the looping order, that it won't match a venue when there actually is one available.
2. It won't optimize room size, because of the simple >= match.

More work on this later.



-- usp_multiroom 'Boardroom,Boardroom,Classroom,U-Shape', '30,100,150,75'
alter procedure usp_multiroom
@roomlist varchar(1000), --comma seperated list of desired rooms
@delegateslist varchar(1000) --comma seperated list of desired delegates
-- (should match 1for1 with @roomlist)
as

create table #reservations ( --temp table to hold processed lists
resid integer identity(1,1),
room varchar(50),
del smallint,
mtgroom int
)

create table #venues ( --temp table to hold possible venues
venid integer identity(1,1),
venueid integer
)

declare @separator_position_room int,
@separator_position_del int,
@array_value_room varchar(50),
@array_value_del varchar(50),
@resid int,
@maxresid int,
@venid int,
@maxvenid int,
@venueid int

--*****************************************************************************
--Step 1: parse the parm lists
-- note: if you are on 2k, you should make this generic and put it in a
-- UDF . . .
--*****************************************************************************

select @roomlist = @roomlist + ','
select @delegateslist = @delegateslist + ','

while patindex('%,%', @roomlist) <> 0
begin
select @separator_position_room = patindex('%,%', @roomlist)
select @separator_position_del = patindex('%,%', @delegateslist)
if @separator_position_del = 0
print 'Do some error handling'


select @array_value_room = left(@roomlist, @separator_position_room-1)
select @array_value_del = left(@delegateslist, @separator_position_del-1)

insert #reservations (room, del)
values(@array_value_room, convert(smallint, @array_value_del))

select @roomlist = stuff(@roomlist, 1, @separator_position_room, '')
select @delegateslist = stuff(@delegateslist, 1, @separator_position_del, '')

end

--*****************************************************************************
--Step 2: get a list of possible venue id that will full-fill all the room requests
-- a possible venue is one where at least one reseration requirement is met
--*****************************************************************************

select
mr.foreignkey as veneuid
into #venuestemp
from
Meeting_rooms mr
inner join Meetingroom_capacity mc
on mr.primarykey = mc.foreignkey
inner join #reservations r
on ((r.room = 'Classroom' and mc.CapacityClass >= r.del) or
(r.room = 'Boardroom' and mc.CapacityBoardroom >= r.del) or
(r.room = 'Theatre' and mc.CapacityTheatre >= r.del) or
(r.room = 'U-Shape' and mc.CapacityUShape >= r.del))
group by mr.foreignkey
order by count(*) desc

--This little dance is done to get the venues with the most rooms at the top to make
--the search faster
insert #venues
select * from #venuestemp

--*****************************************************************************
--Step 3: match up the desired reservations with a meeting room
--*****************************************************************************

--set up the control variables
select
@resid = 1,
@maxresid = max(resid)
from
#reservations

select
@venid = 1,
@maxvenid = max(venid)
from
#venues

--Loop through all the possible venues looking for one that has all the rooms we need
while @venid <= @maxvenid
begin
--Loop through all the reservation requirements and match to a room in this venue
while @resid <= @maxresid
begin
--Put the qualifying room into the #reservations table
update #reservations
set mtgroom = (
select
min(mr.primarykey)
from
Meeting_rooms mr
inner join Meetingroom_capacity mc
on mr.primarykey = mc.foreignkey
inner join #reservations r
on ((r.room = 'Classroom' and mc.CapacityClass >= r.del) or
(r.room = 'Boardroom' and mc.CapacityBoardroom >= r.del) or
(r.room = 'Theatre' and mc.CapacityTheatre >= r.del) or
(r.room = 'U-Shape' and mc.CapacityUShape >= r.del))
inner join #venues v
on v.venueid = mr.foreignkey
where
resid = @resid and
venid = @venid and
not exists (
select 1
from
#reservations
where
mtgroom = mr.primarykey) )
where
resid = @resid

set @resid = @resid + 1
end

--Lets see if we matched all requirements for this venue
if exists (select 1
from
#reservations
where
mtgroom is null)
begin
-- nope, start over with a new venue
update #reservations
set mtgroom = null

select @resid = 1, @venid = @venid +1
end
else
begin
-- hey, we found a match . . . giddy-up
select @venueid = venueid
from #venues
where @venid = venid

break
end
end

select @venueid

drop table #reservations
drop table #venues
go



Jay
Go to Top of Page

Jay99

468 Posts

Posted - 2002-03-15 : 12:01:56
quote:

If Jay comes up with the solution, I won't spend the hour or so I think I will need and I am sure you won't want to waste your time loading exporting some tables.

Jay, does your solution use cursors or did you figure out a setbased solution?

Jeremy





Cursors . . . CURSE YOU!! But it isn't set based . . .


Jay
Go to Top of Page

nmg196
Yak Posting Veteran

70 Posts

Posted - 2002-03-15 : 12:03:42
joldham, yes I did post the schema and the URL of the required sample data in one of my previous posts. You shouldn't need my Venues table as all I need back are Venue IDs. In theory you could actually put the capacities in the Meeting_rooms table and avoid the 2nd table altogether, but it's not my database so I can't modify the schema :(

[url]http://www.nickgilbert.com/temp/VenueDB.zip[/url]

I think you can only get a full explanation of the problem by reading *all* of the above posts as I didn't explain it very well the first few times :)

I think we've got an almost working solution here, but it's too slow to use! Aaagh!

Nick...

Go to Top of Page
    Next Page

- Advertisement -