Solved

# Connected flights query problem....

Posted on 2004-11-17
530 Views
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?
0
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
0

LVL 100

Expert Comment

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

mlmcc
0

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.
0

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.
0

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.
0

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
SourceAirport
DestinationAirport

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

e.g.
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

0

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:

Route_Steps

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.
0

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
loop

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.
0

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.
0

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?
0

Author Comment

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

## Featured Post

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.
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…