Postgres Query Based on Previous and Next Rows

Question

I'm trying to solve the bus routing problem in postgresql which requires visibility of previous and next rows. Here is my solution.

Step 1) Have one edges table which represents all the edges (the source and target represent vertices (bus stops):

postgres=# select id, source, target, cost from busedges;
 id | source | target | cost
----+--------+--------+------
  1 |      1 |      2 |    1
  2 |      2 |      3 |    1
  3 |      3 |      4 |    1
  4 |      4 |      5 |    1
  5 |      1 |      7 |    1
  6 |      7 |      8 |    1
  7 |      1 |      6 |    1
  8 |      6 |      8 |    1
  9 |      9 |     10 |    1
 10 |     10 |     11 |    1
 11 |     11 |     12 |    1
 12 |     12 |     13 |    1
 13 |      9 |     15 |    1
 14 |     15 |     16 |    1
 15 |      9 |     14 |    1
 16 |     14 |     16 |    1

Step 2) Have a table which represents bus details like from time, to time, edge etc.

NOTE: I have used integer format for "from" and "to" column for faster results as I can do an integer query, but I can replace it with any better format if available.

postgres=# select id, "busedgeId", "busId", "from", "to" from busedgetimes;
 id | busedgeId | busId | from  |  to
----+-----------+-------+-------+-------
 18 |         1 |     1 | 33000 | 33300
 19 |         2 |     1 | 33300 | 33600
 20 |         3 |     2 | 33900 | 34200
 21 |         4 |     2 | 34200 | 34800
 22 |         1 |     3 | 36000 | 36300
 23 |         2 |     3 | 36600 | 37200
 24 |         3 |     4 | 38400 | 38700
 25 |         4 |     4 | 38700 | 39540

Step 3) Use dijkstra algorithm to find the nearest path.

Step 4) Get the upcoming buses from the busedgetimes table in the earliest first order for the nearest path detected by dijkstra algorithm.

Problem: I am finding it difficult to make the query for the Step 4.

For example: If I get the path as edges 2, 3, 4, to travel from source vertex 2 to target vertex 5 in the above records. To get the first bus for the first edge, it's not so hard as I can simply query with from < 'expected departure' order by from desc but for the second edge, the from condition requires to time of first result row. Also, query requires edge ids filter.

How can I achieve this in a single query?

Acord

you can use window function lag as mention in this post for computing current result on the based of previous result. – Mathia

Thank you so much, yes, I think this helps me in solving the problem. I am gonna try this and update here. – Acord

Thanks again, this helped me solve the problem with some additional conditions and subquery. dbfiddle.uk/… – Acord

Answer 1

I am not sure if I understood your problem correctly. But getting values from other rows this can be done by window functions (https://www.postgresql.org/docs/current/static/tutorial-window.html):

demo: db<>fiddle

SELECT
    id,
    lag("to") OVER (ORDER BY id) as prev_to,
    "from",
    "to",
    lead("from") OVER (ORDER BY id) as next_from
FROM bustimes;

The lag function moves the value of the previous row into the current one. The lead function does the same with the next row. So you are able to calculate a difference between last arrival and current departure or something like that.

Result:

id   prev_to   from    to      next_from
18             33000   33300   33300
19   33300     33300   33600   33900
20   33600     33900   34200   34200
21   34200     34200   34800   36000
22   34800     36000   36300        

---

Please notice that "from" and "to" are reserved words in PostgreSQL. It would be better to chose other names.

Sommerville

Thank you so much, yes, I think this helps me in solving the problem. I am gonna try this and update here. Also, thanks for the suggestions on not using reserved words. – Acord

Thanks again, this helped me solve the problem with some additional conditions and subquery. dbfiddle.uk/… – Acord