6

I have what seemed like an easy query to write, that really has me stumped - can anyone help me please?

So this is really easy on paper, but I can't translate it into SQL. Lets say you have some graph data:

x | y

1 | 5.5

2 | 8

3 | 2

4 | 3

5 | 1

And you essentially want to draw a line sloping down on top of the data, touching at least 2 of the top-most points, like this... graph

To find when new data steps above this line-- So I am thinking this comes down to the basic formula for a graph y=A + Bx So, if we know A and B, for a given value of x, we can predict y (and more importantly whether new values of y are above or below the value we predict for y based on this line).

Can anyone help please?

If it helps anyone, very quick create & data statement...

create table graph1 (x int, y decimal(4,2));

insert into graph1 values (1,5.5),(2,8),(3,2),(4,3),(5,1);

I can do a least squares regression to generate an equation for the linear regression (a line through the middle of the data) - but how would I generate one for the top of the channel the data sits in??

  • 1
    Verify the accuracy of your illustration... it seems like if (2,8) and (4,3) are true then you have a rise/run of -2.5/1 so the line would intersect (5,0.5) so (5,1) is actually above the line, not below. Right? – Michael - sqlbot Mar 29 '15 at 13:21
  • Clearly its not meant to be to scale - it was for illistrative purposes only - what's important is the SQL code that will work with any example. – user3566845 Mar 29 '15 at 13:23
  • Do you know that there could be more than one solutions (lines) to the problem? Do you want the query to find them all? – ypercubeᵀᴹ Mar 29 '15 at 13:26
  • 2
    You problem is called Pareto (efficient) front or convex hull. I had answered a similar question in SO, some years ago: How to write a query selecting reasonable trade-offs? (but that answer is without the "efficient", just the Pareto front.) – ypercubeᵀᴹ Mar 29 '15 at 14:07
  • 1
    Not a direct answer, but maybe a solution to your problem: If you calculate the trend line (regression) for your data, and then calculate the MAX distance of points above this line, you can check for each new point if its distance from the trend-line is bigger than the MAX-Distance - so you could find any points which are a bigger deviation than any current... – Falco Mar 30 '15 at 8:57
12

The whole set of lines that satisfy the problem are known as a Pareto efficient front (or frontier or set) or the convex hull problem.
(See also my answer in the similar question at StackOverflow: How to write a query selecting reasonable trade-offs?).

So, one way to solve would be to identify first the points of the front, with a query like below. I assume there is a unique constraint on (x):

CREATE TABLE pareto AS
SELECT a.x
     , a.y
FROM graph1 AS a
WHERE NOT EXISTS
  ( SELECT 1
    FROM graph1 AS b
    WHERE b.x > a.x
      AND b.y >= a.y
  ) ;

SELECT *
FROM pareto ;

This would result in:

+------+------+
| x    | y    |
+------+------+
| 2.00 | 8.00 |
| 4.00 | 3.00 |
| 5.00 | 1.00 |
+------+------+

The lines that pass through these points are our candidates. We have to eliminate however the points (like (4,3)) where another line passes above it. This would be much easier with a recursive CTE but MySQL has not implemented CTEs at all.

The query would not be hard to write - but you do need to experiment with adding some indexes on the temp table (you might even make it a normal InnoDB table), especially if the number of points is high:

SELECT p.x
     , p.y
FROM pareto AS p
WHERE NOT EXISTS   
      ( SELECT 1 
        FROM pareto AS st 
          CROSS JOIN pareto AS en
        WHERE st.x < p.x 
          AND p.x < en.x 
          AND (p.x * (en.y-st.y) + p.y * (en.x-st.x) < 0)
      ) ;

Result:

+------+------+
| x    | y    |
+------+------+
| 2.00 | 8.00 |
| 5.00 | 1.00 |
+------+------+

If the number of points expected at this point is high (like 1000+) a SQL query for MySQL would probably be inefficient as it would require a 3-way cross join (of the temp table). Another option would be to have a query that uses mysql variables and runs through the (temp) table in order of the x coordinate, eliminating the covered points - either in one or multiple batches.


Another option would be to write the whole query in one go. Good for testing with small data - but I wouldn't even try it if there were millions of rows:

SELECT a.x
     , a.y
FROM graph1 AS a
WHERE NOT EXISTS
      ( SELECT 1
        FROM graph1 AS b
        WHERE b.x > a.x
          AND b.y >= a.y
      ) 
  AND NOT EXISTS   
      ( SELECT 1 
        FROM graph1 AS st 
          CROSS JOIN graph1 AS en
        WHERE st.x < a.x 
          AND a.x < en.x 
          AND (a.x * (en.y-st.y) + a.y * (en.x-st.x) < 0)
      ) ;

Result:

+------+------+
| x    | y    |
+------+------+
| 2.00 | 8.00 |
| 5.00 | 1.00 |
+------+------+

Note for all the queries. I would prefer if both x and y where the same type (so make x decimal(4,2) as y).

An index on (x,y) would be used by both queries.

  • Amazing!! I was also looking at using the least squares regression (as quick to execute) -- and this could be used to cut down the amount of data feeding into your query. Thank you so much! (I would vote up but I only a noobie here so not allowed yet) – user3566845 Mar 29 '15 at 14:59
  • (I realise this wasn't part of my original question) I'm now looking at getting the lower most co-ordinates. I tried reversing the query, but its the last line thats foxing me, I've got... – user3566845 Mar 29 '15 at 15:13
  • SELECT a.x, a.y FROM graph1 a WHERE NOT EXISTS ( SELECT 1 FROM graph1 b WHERE b.x < a.x AND b.y <= a.y ) AND NOT EXISTS ( SELECT 1 FROM graph1 st CROSS JOIN graph1 en WHERE st.x > a.x AND a.x > en.x AND (a.x * (st.y-en.y) + a.y * (st.x-en.x) > 0) ) ; – user3566845 Mar 29 '15 at 15:13
  • Your query seems right. it return 3 points (1, 5.5) (3,2) and (5,1). I would have written it as SELECT a.x, a.y FROM graph1 a WHERE NOT EXISTS ( SELECT 1 FROM graph1 b WHERE b.x < a.x AND b.y <= a.y ) AND NOT EXISTS ( SELECT 1 FROM graph1 st CROSS JOIN graph1 en WHERE st.x < a.x AND a.x < en.x AND (a.x * (en.y-st.y) + a.y * (en.x-st.x) > 0) ) ; but the result is the same – ypercubeᵀᴹ Mar 29 '15 at 15:25
  • I was trying to get rid of that (5,1) -- but if I'm understanding Pareto correctly thats also a valid candidate - thanks again! – user3566845 Mar 29 '15 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.