"Travelling Salesman" SQL statement?
Hi guys, Pls pardon me if this sounds not directly related to Informix newsgroup. Reason being, someone suggested a solution but is based on "the other" database SQL extention, namely CONNECT and START WITH. How would I do this in an Informix db environment? Let's say I have a table like this, start end ------ ------ A B A C B C B E C E and I would like to know, what are all the ways I can go from A to E, how would I do my SQL statement? I would like my output to be, Route 1 - A to B, B to C, C to E Route 2 - A to C, C to E. Thanks, tata. p.s. below's the fun stuff that I got from http://www.experts-exchange.com/ on this particular question. -------------------- What you're asking for is not simple, for 2 reasons: 1. you want to "walk the tree" for as many legs as it takes to get to the destination 2. you only want to display trees (itineraries) whose last node is your final destination It is far simpler and more efficient to do this within a procedure. However, if you insist on doing this within a single query, you'll want to use your database's equivalent of the "Connect by" clause. Below is an example in Oracle. If this is the type of thing you want, let me know and I'll try to explain it. /* My table of flights. It has lots of different flights between cities A through F. You want to get to get from A to D. */ SQL> select * from yoren_tmp; DEPT_STATION ARRV_STATION ------------ ------------ A D A B C D B C A E D F A C C E /* The query below shows all the possible ways to get from A to D */ SQL> get tmp 1 select itinerary_id, dept_station,arrv_station 2 from 3 (select rownum-level itinerary_id, 4 dept_station,arrv_station 5 from yoren_tmp 6 where dept_station != '&&to' 7 start with dept_station = '&&from' 8 connect by prior arrv_station = dept_station 9 ) a 10 where exists 11 (select * from 12 (select rownum-level itinerary_id, 13 dept_station,arrv_station 14 from yoren_tmp 15 where dept_station != '&&to' 16 start with dept_station = '&&from' 17 connect by prior arrv_station = dept_station 18 ) b 19 where a.itinerary_id = b.itinerary_id and 20* b.arrv_station = '&&to') SQL>/ SQL> / Enter value for to: D old 6: where dept_station != '&&to' new 6: where dept_station != 'D' Enter value for from: A old 7: start with dept_station = '&&from' new 7: start with dept_station = 'A' old 15: where dept_station != '&&to' new 15: where dept_station != 'D' old 16: start with dept_station = '&&from' new 16: start with dept_station = 'A' old 20: b.arrv_station = '&&to') new 20: b.arrv_station = 'D') ITINERARY_ID DEPT_STATION ARRV_STATION ------------ ------------ ------------ 0 A D 1 A B B C C D 6 A C C D 6 rows selected.
As far as I can tell, Informix SQL doesn't have a direct equivalent to START
WITH or CONNECT BY PRIOR. Your specific problem can be solved directly in a
single SQL, with the caveat that we have to set a maximum number of hops.
Here's my test for up to four hops (cribbed from Informix Guide to SQL
Version 7.2 Tutorial page 5-29):
create table route( start char(1), end char(1));
insert into route values ("A", "B");
insert into route values ("A", "C");
insert into route values ("A", "D");
insert into route values ("A", "E");
insert into route values ("A", "G");
insert into route values ("G", "H");
insert into route values ("H", "I");
insert into route values ("H", "E");
insert into route values ("I", "E");
insert into route values ("G", "B");
insert into route values ("D", "F");
insert into route values ("B", "C");
insert into route values ("B", "E");
insert into route values ("C", "E");
select one.start, one.end, two.end, three.end, last.end
from route one,
outer (route two,
outer (route three, outer route last))
where one.start = "A"
and last.end = "E"
and one.end = two.start
and two.end = three.start
and three.end = last.start
order by last.end, three.end, two.end, one.end
Output:
A E
A B E
A C E
A D F
A G B E
A B C E
A G H E
A G B C E
A G H I E
Since Informix SQL doesn't have a way to reference a prior row, I don't
think that a no-upper-limit solution is achievable. As your Oracle
respondent points out, in 4GL, SPL, or other procedural language, this is a
variation of the parts-explosion problem and readily (but not trivially)
resolved. If you want to see it in 4GL, say "Please" and I'll write-and-post
it.
Lee Haw, Ong wrote in message <77g25b$14o$1@mawar.singnet.com.sg>...
>Hi guys,
>
>Pls pardon me if this sounds not directly related to Informix newsgroup.
>Reason being, someone suggested a solution but is based on "the other"
>database SQL extention, namely CONNECT and START WITH. How would I do this
>in an Informix db environment?
>
>Let's say I have a table like this,
>
>start end
>------ ------
>A B
>A C
>B C
>B E
>C E
>
>and I would like to know, what are all the ways I can go from A to E, how
>would I do my SQL statement?
>
>I would like my output to be,
>
>Route 1 - A to B, B to C, C to E
>Route 2 - A to C, C to E.
>
>Thanks, tata.
>
>
>p.s. below's the fun stuff that I got from http://www.experts-exchange.com/
>on this particular question.
>
>--------------------
>
>What you're asking for is not simple, for 2 reasons:
>
>1. you want to "walk the tree" for as many legs as it takes to get to the
>destination
>2. you only want to display trees (itineraries) whose last node is your
>final destination
>
>It is far simpler and more efficient to do this within a procedure.
However,
>if you insist on doing this within a single query, you'll want to use your
>database's equivalent of the "Connect by" clause. Below is an example in
>Oracle. If this is the type of thing you want, let me know and I'll try to
>explain it.
>
>/* My table of flights. It has lots of different flights between cities A
>through F. You want to get
> to get from A to D. */
>SQL> select * from yoren_tmp;
>
>DEPT_STATION ARRV_STATION
>------------ ------------
>A D
>A B
>C D
>B C
>A E
>D F
>A C
>C E
>
>
>/* The query below shows all the possible ways to get from A to D */
>SQL> get tmp
> 1 select itinerary_id, dept_station,arrv_station
> 2 from
> 3 (select rownum-level itinerary_id,
> 4 dept_station,arrv_station
> 5 from yoren_tmp
> 6 where dept_station != '&&to'
> 7 start with dept_station = '&&from'
> 8 connect by prior arrv_station = dept_station
> 9 ) a
> 10 where exists
> 11 (select * from
> 12 (select rownum-level itinerary_id,
> 13 dept_station,arrv_station
> 14 from yoren_tmp
> 15 where dept_station != '&&to'
> 16 start with dept_station = '&&from'
> 17 connect by prior arrv_station = dept_station
> 18 ) b
> 19 where a.itinerary_id = b.itinerary_id and
> 20* b.arrv_station = '&&to')
>SQL>/
>SQL> /
>Enter value for to: D
>old 6: where dept_station != '&&to'
>new 6: where dept_station != 'D'
>Enter value for from: A
>old 7: start with dept_station = '&&from'
>new 7: start with dept_station = 'A'
>old 15: where dept_station != '&&to'
>new 15: where dept_station != 'D'
>old 16: start with dept_station = '&&from'
>new 16: start with dept_station = 'A'
>old 20: b.arrv_station = '&&to')
>new 20: b.arrv_station = 'D')
>
>ITINERARY_ID DEPT_STATION ARRV_STATION
>------------ ------------ ------------
> 0 A D
> 1 A B
> B C
> C D
> 6 A C
> C D
>
>6 rows selected.
>
>
>