Advanced query possible UNION ? help
-
Hello,
I am attempting to use a find the number of points between two points.
I have 3 tables that store information about which point connects to another point.
Tables:
tblCountry has two columns
toCountry | fromCountry
--------------|--------------
1001 | 1011
1001 | 1012
1001 | 1028
1002 | 1003
1002 | 1016
ect... returns approximately 300 rows
tblCounty has 4 columns
toCountry | fromCounty | toCounty | fromCountry
--------------|---------------|--------------|--------------
1001 | 2001 | 2004 | 1001
1001 | 2001 | 2005 | 1001
1001 | 2001 | 2008 | 1001
1001 | 2001 | 2009 | 1001
1001 | 2001 | 2011 | 1001
1001 | 2001 | 2367 | 1030
1002 | 2017 | 2020 | 1002
1002 | 2018 | 2020 | 1002
1002 | 2018 | 2022 | 1002
1002 | 2018 | 2409 | 1033
ect... returns approximately 2,000 rows
tblCity has 6 columns
toCountry | fromCounty | toCity | fromCity | toCounty | fromCountry
--------------|---------------|--------------|---------------|--------------|---------------
1001 | 2001 | 3001 | 3003 | 2001 | 1001
1001 | 2001 | 3001 | 3005 | 2001 | 1001
1001 | 2001 | 3001 | 3007 | 2001 | 1001
1001 | 2001 | 3002 | 3005 | 2001 | 1001
1001 | 2016 | 3118 | 3117 | 2017 | 1002
1002 | 2017 | 3119 | 3120 | 2017 | 1002
1002 | 2017 | 3119 | 3121 | 2017 | 1002
1002 | 2017 | 3122 | 3120 | 2017 | 1002
ect... returns approximately 14,000 rows
what I am trying to do is plot a course between two cities and get the number of cities between "fromCity(A)" and "toCity(B)"
I thought that a Union query would do the job for me, but I am having a rough time with the logic involved.
what I am looking to do is check to see if city A is in the same country as city B, if yes, check to see if city A is in the same county as city B, if yes check to see if city A connects to city B, if yes return 1 row.
like wise, if none of the above are true, get the country that city A is in, find the country city B is in, check to see if they border each other, if not, find a route that connects Country A with Country B then plot the shortest route between (countryA(CountyA(CityA))) and (countryB(CountB(CityB))) and return the number of rows.
when I start this query, the starting city, county and country are Known as well as the end city, county and country.
the only result I am trying to find is the number of points between city A and city B.
Any thoughts on how to do this?
Any help would be greatly appreciated.
Swindla
-
Have a look at my implementation of Dijkstra's algorithm posted here
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=77262
N 56°04'39.16"
E 12°55'05.25" -
Peter,
Thank you for your reply.
After making the above post, I somehow stumbled accross the Wikipidia definition of the Dijkstra's Algorithm and the link to your post at http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=77262.
It looks like what I need.
I was very tired when I found it and have not tried to implement it.
I am curious as to how processor intisive it will be.
Have you done any benchmarking by chance?
The reason I ask is;
I would like to use this in a web application and display the number of nodes from a current location to up to 30 different locations. ie.. "you are here" (current location), (locationA) "is 4 nodes away", (locationB)"is 8 nodes away", (locationC) "is 20 nodes away" etc... for up to 30 different "To Locations".
With the possibility of having 150+ users hitting this page at the same time all with different "Start locations" and 30 "To Locations", it would seem that this might not be possible, due to CPU limitations, memory limitations and or disc limitations.
Any thoughts on this ?
Swindla
-
You should use dbo.fnFriendsStep function found here
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=73079
It works quit fast and performs well.
//Peter Larsson
N 56°04'39.16"
E 12°55'05.25" -
Peter,
After a quick test of the function listed in the link above http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=73079 , it would appear that this returns a count of ALL rows in the table.
using your illistration:
/*
A - B
/ / \
C - G D
\ /
E - F
*/
What I am looking for is to get a count of the number of nodes from "A" to "F" (which in this case would be 3) or from "A" to "E" ( the shortest route would be from "A" to "C" to "E", and should return 2).
I am going to play with it a bit and see what I come up with.
Thank you very much for your input.
Swindla
-
CREATE FUNCTION dbo.fnFriendsBetween
(
@From VARCHAR(2),
@To VARCHAR(2)
)
RETURNS INT
AS
BEGIN
IF @From IS NULL OR @To IS NULL
RETURN -1
DECLARE @Friends TABLE (Generation INT, p VARCHAR(2))
DECLARE @Generation INT
SELECT @Generation = 0
INSERT @Friends
(
Generation,
p
 
SELECT 0,
@From
WHILE @@ROWCOUNT > 0 AND NOT EXISTS (SELECT * FROM @Friends WHERE p = @To)
BEGIN
SELECT @Generation = @Generation + 1
INSERT @Friends
(
Generation,
p
 
SELECT @Generation,
pTo
FROM Contacts
WHERE pFrom IN (SELECT p FROM @Friends WHERE Generation = @Generation - 1)
AND pTo NOT IN (SELECT p FROM @Friends)
UNION ALL
SELECT @Generation,
pFrom
FROM Contacts
WHERE pTo IN (SELECT p FROM @Friends WHERE Generation = @Generation - 1)
AND pFrom NOT IN (SELECT p FROM @Friends)
END
RETURN @Generation
END
N 56°04'39.16"
E 12°55'05.25" -
Peter,
This looks wonderful. After some toying around with it, I came up with this query:
select min(dbo.fnFriendsBetween('a', 'f'))
from contacts
which returns
(no Column name)
3
I must admit, that I keep getting lost when trying to follow the flow of the function you have created.
It is wonderful that this works, and I cannot thank you enough, however... I would like to understand what this function is doing.
If it is not too much trouble, could I get an explanation of this? or possibly comment the code?
Thank you once again,
Swindla
p.s. the
threw me off for a sec. -
The reason I ask, is that I will be attempting to use all three tables in order to greatly optimize this query, hopefully removing as many as 13,000 rows to query by checking to find the Starting Country, and the end Country, .. the Countries in route, then doing the same thing for the Counties and finally checking only the cities within those results. Instead of checking all Cites every time.
I really would like to understand how to do this, instead of having someone do it for me.
I hope I am not being too much trouble.
Thank you very much for your assistance.
Swindla
-
After testing this on the tables I am using, it looks like I will have to rethink this whole thing.
simply running a single check between one county and another (the smallest table , with approximately 300 rows) it takes 4 seconds. I am assuming that this is because it it figuring out all of the impossible routes.
I figured I would have a look at the larger table ( which returns 14000 + rows ) and see what kind of time it would take to complete.......
I stopped the query after 30 minutes, in fear of filling the drives with one table...
It looks like I will need to figure out some way to weight the nodes in an attempt to prevent calculations of less likely routes.
4 seconds would be pushing it for a complete calculation fromCity >> toCity. I fear that this may not be possible with what I have to work with.
Swindla
Viewing 10 posts - 1 through 10 (of 10 total)
You must be logged in to reply to this topic. Login to reply