Ходить по дереву в обратном направлении в SQL

Question

У меня есть таблица с очень простой схемой:

CREATE TABLE q(
 orig INTEGER NOT NULL,
 dest INTEGER NOT NULL,
 cost  FLOAT,
 PRIMARY KEY (orig, dest)
);

Мне нужно пройтись по столу назад, чтобы минимизировать затраты. Позвольте мне объяснить.

Мне нужен тур из 15 пунктов, пункт может быть orig или dest. Мой алгоритм - возврат от последнего dest к исходному orig. Вот как я это изложил:

Учитывая последний dest, найдите orig, который будет ссылаться на указанный dest с минимальным cost. Соответствующий orig становится новым dest; повторить это 15 раз.

Давайте предположим, что я знаю, что последним dest является число 10. Оператор SQL, который позволяет мне найти orig, ведущий к dest в cost-, сводит к минимуму:

SELECT orig FROM q WHERE cost = (SELECT MIN(cost) FROM q WHERE dest = 10);

Теперь я бы использовал orig, возвращенный вышеупомянутой функцией, чтобы найти предыдущую точку (предположим, она вернула, скажем, точку 5):

SELECT orig FROM q WHERE cost = (SELECT MIN(cost) FROM q WHERE dest = 5);

Я могу продолжать до тех пор, пока не наберу 15 очков.

Как сделать эффективный запрос, чтобы сделать это в SQL? В моей таблице 50 миллионов строк.

Answer 1

Краткий ответ: вы не можете.

Более длинный ответ: предполагая, что я правильно понял ваш вопрос, вы могли бы написать оператор SQL, который был бы настолько эффективным, насколько это возможно, но вряд ли он вернетрезультат в разумные сроки - скажем, возраст вселенной до сих пор.

Если ваша таблица из 50 миллионов строк не содержит дубликатов и отображает прямые пути из всех местоположений во все другие местоположения, то числоМеста включены примерно квадратный корень из 50 миллионов - т.е.несколько более 7070 местоположений.

Количество возможных путей, которые могут быть выбраны, будет, таким образом, 7070 x 7069 x 7068 ... x 7056, или, другими словами, несколько больше, чем 7000 ^ 15 (приблизительно 4,75).x 10 ^ 57).

В конечном счете, это вариант проблемы коммивояжера - подходы на основе грубых сил, основанные на SQL, совершенно не подходят для ее решения с таким большим набором данных.

Answer 2

Вот запрос, который предполагает, что вы используете SQL Server 2005+. Он использует общие табличные выражения (CTE). Этот пример на самом деле возвращает все пути с совокупной стоимостью, которые имеют выбранные orig и dest. Он также показывает количество точек на пути. Его можно изменить, чтобы получить лучший выбор (например, минимальная стоимость, минимальное количество шагов и т.

Я не знаю, как производительность будет. Но индексы были бы полезны.

WITH Paths AS  -- Get list of all paths
    ( SELECT ROW_NUMBER() OVER (ORDER BY orig) AS PathNumber, orig,
        dest, cost, 1 AS points
    FROM q

    UNION ALL

    SELECT Paths.PathNumber, Paths.orig,
        q.dest, q.cost, paths.points + 1 AS points
    FROM Paths
    JOIN q ON Paths.dest = q.orig
    WHERE Paths.points < 15
    )
    , PathsRows AS  -- Get total points in each path
    ( SELECT COUNT(*) OVER (PARTITION BY PathNumber) AS TotalPoints, PathNumber
        , orig, dest, cost, points
    FROM Paths
    )
    , PathsSum AS  -- summarize for each path
    ( SELECT PathNumber,
        MIN(CASE WHEN points = TotalPoints THEN orig END) AS orig,
        MAX(CASE WHEN points = TotalPoints THEN dest END) AS dest,
        SUM(cost) AS cost, MAX(points) AS points
    FROM PathsRows
    GROUP BY PathNumber
    )

SELECT PathNumber, orig, dest, cost, points
FROM PathsSum
WHERE dest = 4
    and orig = 1
ORDER BY PathNumber, points