Connected flights query problem....

Posted on 2004-11-17
Last Modified: 2008-03-17
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?
Question by:azizs
    LVL 1

    Expert Comment

    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
    LVL 100

    Expert Comment

    Will this be in an application or are you trying to do this strictly from SQL?


    Author Comment

    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.
    LVL 1

    Expert Comment

    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.

    Author Comment

    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.
    LVL 50

    Accepted Solution

    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

    LVL 4

    Expert Comment

    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.

    Author Comment

    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.
    LVL 4

    Assisted Solution

    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.
    LVL 50

    Expert Comment

    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?  

    Author Comment

    got it done thanks everyone. you guys have been great help...

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    How your wiki can always stay up-to-date

    Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
    - Increase transparency
    - Onboard new hires faster
    - Access from mobile/offline

    Introduction: Often, when running a query with joins, the results show up "duplicates", and often, those duplicates can be "eliminated" in the results using DISTINCT, for example. Using DISTINCT is simple: just add it after the SELECT keyword, an…
    Creating and Managing Databases with phpMyAdmin in cPanel.
    Video by: Steve
    Using examples as well as descriptions, step through each of the common simple join types, explaining differences in syntax, differences in expected outputs and showing how the queries run along with the actual outputs based upon a simple set of dem…
    Polish reports in Access so they look terrific. Take yourself to another level. Equations, Back Color, Alternate Back Color. Write easy VBA Code. Tighten space to use less pages. Launch report from a menu, considering criteria only when it is filled…

    737 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    15 Experts available now in Live!

    Get 1:1 Help Now