Connected flights query problem....

I have a flight table with flight number, departure time, arrival time, date, leavesFrom and arrivesAt. I need to determine given a place of departure and destination whether it is possible to get to the destination by taking 0 or more connection flight. And a way to determine (an empty table perhaps) if no just flight exits. Need the flight / connection flights that would take the least amount of time, if psobbile.

 num |    day     |    aid     |      leavesfrom      |      arrivesat       |    departuretime    |     arrivaltime
   2 | 2005-01-09 | id1        | Dubai                | swiss                | 2005-01-09 04:05:06 | 2005-01-09 05:05:06
   3 | 2005-01-10 | id1        | swiss                | Tanzania             | 2005-01-10 04:05:06 | 2005-01-10 05:05:06
   4 | 2005-01-11 | id1        | Tanzania             | Karachi              | 2005-01-11 04:05:06 | 2005-01-11 05:05:06
   1 | 2005-01-08 | id1        | Toronto              | Dubai                | 2005-01-08 04:05:06 | 2005-01-08 05:05:06
   7 | 2005-01-12 | id1        | Dubai                | Toronto              | 2005-01-12 04:05:06 | 2005-01-12 05:05:06
  17 | 2005-01-13 | id1        | Jamaica              | Miami                | 2005-01-13 04:05:06 | 2005-01-13 05:05:06

for example there is  a flight from Toronto to Karachi that requires 3 connection flights

If that is not possible to extract from current table, what solution can you provide and how can i go about doing it?
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

You need to limit the number of connections you're allowed, or you will have an infinitely complex problem.

Once you have decided on a limit, build up subqueries on connecting flights, joining on arrivesat=departs and where the time and date of departure are after the arrival time
Will this be in an application or are you trying to do this strictly from SQL?

azizsAuthor Commented:
Well I could limit the number of connection to say 12. That is something i thought abt but building up subquereis won't be an efficient solution, since the flight table would be potentially huge. Well basically I have a  application program which asks this query from the database. So i planned on having some function which actually runs the query and send the result back.
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

I don't think you're going to get an efficient solution. Because there is no logical way to know which route to take, you need to check all the options at each stage. I believe the term is NP complex. See also the travelling salesman problem.
azizsAuthor Commented:
Well i wouldn't say the problem is in NP. well this question is more like given a node s and a node t in a graph determine whether you can reach s from t. now although the brtue force algorithm would be exponential in time you could get a poly time algo. which would basically be a breath first search. And this problem more resembles the problem i mentioned above then the salesman problem. In the salesman problem we are forced to visit every city (this is what i guess results in exponential time) but that is not the case inthis problem.
least amount of time is a problem
and this approach is bordering on the brute force approach

temp tables like

Level int


 Insert into a temp table
  all the Direct connections from the starting airport

  exit if destination is in list....

 Insert into a second temp table  
  all the Direct connections from the Destination airport

2) Main Loop

  Now For the Current levels DestinationAirports
   insert as the next level all destination available from them
       for which the destinationAirport does not already exist
         at a previous level  
  Check to see if any The Desired Destination has been reached
  of If the Destination Airport exists in the second Temp Table
    so a flight exist to the destination...

  Take the Current levels in the second temp table and
   insert as the next level all destinations available from them
       for which the destinationAirport does not already exist
         at a previous level  

  Check to see if any The Desired Destination has been reached
  of If the Destination Airport exists in the First Temp Table
    so a flight exist to the destination...

 loop ...

that technique will provide a flight plan from A to B, with minimum
connections ... but of course it may not be the most direct or
shorttest travel time...

London to Perth

flight 1 London - Paris
flight 2 Paris - Newcastle
flight 3 NewCastle - Perth

as opposed to
london - Birmingham
Birmingham - Leeds
Leeds - Glasgow
Glasgow - Perth


Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
You have to bound the options carefully or you'll end up with a myriad of possible routes.

I think you'd have to create a table like:


Step    Flight_Num    ....    departuretime    flighttime   waittime

Then one of the first restrictions you have to impose is to discard possible flights if you already have them in the table.

Just of the top of my head, it might be a good idea to scan the options from both ends.  Create a table with the cities you can go from the depature city in 1 flight, in 2 flights, etc.   And then from destination city again, from how many cities you can arrive in 1 flight, in 2 flights, etc.  The it's a matter of matching Departure 1 flight with Destination 1 Flight, if no luck, then increase 1 flight from either end, then 1 flight from the other, etc.  That should reduce the options considerably.
azizsAuthor Commented:
hmm Lowfatspread i didn't fully understand what you said but i think i have an idea of what you query is doing just do double check this is what i think is going on

Step1 create a table with the following attributes, leaveFrom Char , arrvesAt Char, Connection int
and insert all the flights that leave from "Place we leave from"  and its destination and put in connection as 0 for all of them
then check if the table consists of destination matching the "Place we want to reach". if so we break and return the result

else step2  

that insert all the flights that leave from the current destinations(arrivesAt attribute), currently in the temp table created, and insert their resulting destinations plus insert connections as 1 for all of them. check if i have the destination i was looking for in the arrivesAt section. If yes i just break from the loop returning the result

else i continue looping incremementing connection each time

Plus wondering if someone has better solution then this or can improve it? or if someone could come up with a function that does that limiting to 6 connection flights and returing the number of connections that would be great.
Lowfatspread's idea is not exactly that, the thing I suggested is actually the same idea.

If you do what you say you'll potentially end with a bigger number of routes only to finally discard most of them.  In your example (Toronto - Karachi) that would give you:

Toronto - Dubai - 0
Dubai - Toronto - 1  (ok, strike this)
Dubai - Swiss - 1
Swiss - Tanzania - 2
Tanzania - Karachi - 3       (4 iterations)

Ok, this didn't work as I expected because your data isn't real, but imagine flights from Toronto to all over the World, say New York, then New York has tons of connections, etc., etc.

Instead you would iterate from the departure point and the destination point:

Toronto - Dubai - 0                         Tanzania - Karachi - 1       (2 iterations)

Dubai <> Tanzania then iterate once more from the departure:

Toronto - Dubai - 0                         Tanzania - Karachi - 1       (3 iterations)
Dubai - Swiss - 1

Swiss <> Tanzania then iterate once more from the destination:

Toronto - Dubai - 0                         Tanzania - Karachi - 1       (4 iterations)
Dubai - Swiss - 1                            Swiss - Tanzania - 2        

Swiss = Swiss - you got a match!

In this case it's the same, but if you make sample data with at least 2 flights departing from each city you'll see the difference.
hmm yes , my basic idea was just to find the destination available from each airport
with the assumption that if a flight exists a to b then a return flight b to a is possible...
i wasn't at this initial stage assuming that individual flights would be stored in the temp tables
just the distinct set of possible destinations...
  that could of course mean that the eventual route would come out as flights only on fridays between airports ...

how real is this requirement?  
azizsAuthor Commented:
got it done thanks everyone. you guys have been great help...
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.