Самый эффективный способ индексировать и запрашивать пути в графе

Question

У меня есть таблица, представляющая график: Края (от, до) .

Я бы хотел запросить эту таблицу с помощью «запросов пути», получая только источник и назначение пути.

Например, предположим, что моя таблица состоит из следующих строк:

+------+----+
| from | to |
+------+----+
| a    | b  |
| b    | c  |
| c    | d  |
| f    | g  |
| b    | f  |
| c    | a  |
+------+----+ 

Предположим, я выполняю следующий (псевдо) запрос:

SELECT ?v1, ?v2 WHERE ?v1 to ?t1, ?t1 to ?t2, ?t2 to ?v2;

Это означает, что я хочу, чтобы все пары источника и назначения существовали на всех путях, состоящих из 4 узлов. Выполнение этого запроса должно вернуть следующие результаты:

+-----+-----+
| ?v1 | ?v2 |
+-----+-----+
| a   | a   |
| a   | g   |
| a   | d   |
+-----+-----+

Конечно, могут понадобиться и пути, состоящие из разного количества узлов, число 4 не кодируется жестко: -)

Мои вопросы:

1. Какой лучший способ построить такой запрос SQL (обратите внимание, что я использую SQLite, поэтому рекурсивные запросы использовать нельзя).
2. В настоящее время у меня есть один индекс для столбца из и один для столбца до . Это оптимально? Должен ли я создать индекс для пары " from, to ?" Вместо этого?

Предположения

1. Нет собственных краев (E.G "a - a").

2. Нет двух одинаковых строк.

Заранее спасибо!

Answer 1

ad 1.) если вы заранее не знаете, что ваши пути всегда будут иметь заданную длину (или небольшой набор заданных длин), вы не можете выразить свой запрос в чистом sql.тем не менее, вы можете постепенно поддерживать транзитивное закрытие вашего графика, в частности, если

• изменения в вашем графике нечасты
• и / или являются в основном вставками ребер (вместо удаления)
• или в основном происходят как массовые изменения, иногда допускающие некоторую предварительную обработку.

метод описан в статье dong et al., Doi: //10.1.1.103.3314 ;не пугайтесь теории и математики, они также предоставляют готовый к использованию SQL-код, и их основные идеи просты.

ad 2.)

, если поддерживать транзитивное замыканиеТаблица - это опция для вас, она может дать один индекс на пару столбцов, представляющих начальную и конечную вершины путей.

если это не так, вы можете использовать структуру своего графика: для среднего поклонника-выходов, которые высоки (малы) по сравнению с разветвлениями, вам лучше использовать индекс в столбце 'to' ('from').

, если вы не можете сделать предположение о разветвленииСоотношения / веер, вероятно, вам лучше всего иметь индекс для каждого столбца.

надеюсь, это поможет,

С наилучшими пожеланиями, Carsten