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.
| 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 peopleClassroom 100 peopleClassroom 200 peopleBoardroom 20 peopleMy 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. |
 |
|
|
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 darkI 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 procselect @roomtype = 'classroom', @capacity = 100select r.roomnamefrom rooms r inner join Meetingroom_capacity c r.roomid = c.foreignkeywhere (@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 |
 |
|
|
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... |
 |
|
|
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 isstart loop findroomsuitable (excluding rooms already marked as suitable) add new room to reserved/to-be-excluded listend loopyou 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. |
 |
|
|
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... |
 |
|
|
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)ascreate 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) <> 0begin 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 #reservationswhile @resid <= @maxresidbegin 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 endselect *from #reservationsdrop table #reservationsgoJayedit: 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 |
 |
|
|
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... |
 |
|
|
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 |
 |
|
|
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 |
 |
|
|
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 |
 |
|
|
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. |
 |
|
|
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, capacityClassFROM Meeting_Rooms INNER JOIN Meetingroom_capacity ON Meeting_Rooms.primaryKey = Meetingroom_capacity.foreignKeyWHERE (NOT (capacityBoardroom = 0)) AND (NOT (capacityClass = 0))ORDER BY Meeting_Rooms.foreignKey, capacityBoardroom, capacityClass VenueID RoomID capacityBoardroom capacityClass ----------- ----------- ----------------- ------------- 22 2204 16 1822 2207 20 2022 2201 20 2522 2202 20 2522 2203 20 3523 2301 52 6024 2403 36 3624 2402 80 13024 2401 120 15027 2701 40 6028 2807 30 4528 2806 50 5028 2805 60 6029 2904 24 1229 2905 24 1229 2906 24 1229 2903 30 4029 2901 70 12029 2902 70 12030 3005 14 1030 3007 14 1430 3006 20 5030 3003 30 5030 3004 30 5030 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 20Classroom 100Classroom 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 |
 |
|
|
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 20set B...satisfies classroom capacity 100set C...satisfies classroom capcaity 120what 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 BA BCCCCCA B A C BXXA C B A C BAA C B ACAAA BBBBBCB C C CCCCCso 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) |
 |
|
|
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 |
 |
|
|
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 :) )JayEdit: 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:21Edit(again): There is going to be a big precision/performance tradeoff . . .Edited by - Jay99 on 03/15/2002 11:58:13 |
 |
|
|
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. |
 |
|
|
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 |
 |
|
|
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)ascreate 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) <> 0begin 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 veneuidinto #venuestempfrom 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.foreignkeyorder by count(*) desc--This little dance is done to get the venues with the most rooms at the top to make--the search fasterinsert #venuesselect * from #venuestemp--*****************************************************************************--Step 3: match up the desired reservations with a meeting room--*****************************************************************************--set up the control variablesselect @resid = 1, @maxresid = max(resid)from #reservationsselect @venid = 1, @maxvenid = max(venid)from #venues--Loop through all the possible venues looking for one that has all the rooms we needwhile @venid <= @maxvenidbegin --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 endendselect @venueiddrop table #reservationsdrop table #venuesgoJay |
 |
|
|
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 |
 |
|
|
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... |
 |
|
|
Next Page
|
|
|
|
|