Как выполнить ненаправленную обработку графа из данных SQL - PullRequest
Новая
       8

Как выполнить ненаправленную обработку графа из данных SQL

0 голосов
/ 11 мая 2010

Я столкнулся со следующей проблемой при динамическом создании тем для нашей системы ActiveMQ:

У меня есть несколько процессов (M_1, ..., M_n), где n невелико, обычно 5-10. Некоторые процессы будут прослушивать вывод других через очередь сообщений; эти ребра указываются в файле XML, например, 

<link from="M1" to="M3"</link>
<link from="M2" to="M4"</link>
<link from="M3" to="M4"</link>

и т.д.. Края редкие, поэтому их не будет много. Я проанализирую этот XML и сохраню эту информацию в БД SQL, одна таблица для узлов и другая для ребер.

Теперь мне нужно динамически создать строки вида 

M1.exe --output_topic=T1
M2.exe --output_topic=T2
M3.exe --input_topic=T1 --output_topic=T3
M4.exe --input_topic=T2 --input_topic=T3

где теги генерируются последовательно. Каков наилучший способ запроса SQL для получения этих отношений? Есть ли какие-либо инструменты или другие учебники, на которые вы можете указать мне? Я никогда не занимался с SQL.

Использование SQL обязательно, потому что мы используем его и для других вещей.

Спасибо!

1 Ответ

1 голос
/ 11 мая 2010

Хорошо, вот мой удар по проблеме.

Вот эскиз таблиц узлов и ребер: 

[nodes]
node : varchar(xx)

[edges]
outputNode : varchar(xx)
inputNode : varchar(xx)

Если ваш БД поддерживает CTE, тогда такой структурированный запрос объединит взаимосвязи и объединит результаты: 

/* pair output nodes with a topic, assigned sequentially */
WITH OutputTopics(node, topicNumber) AS (
   SELECT outputNode, ROW_NUMBER() (ORDER BY outputNode) AS topicNumber 
   FROM 
     (SELECT DISTINCT outputNode FROM edges) AS outputNodes
), 
/* pair input nodes to the topic of associated output nodes */
InputTopicNumbers(inputNode, topicNumber) AS (
   SELECT edges.inputNode, ot.topicNumber FROM edges INNER JOIN
       OutputTopics AS ot ON ot.node=edges.outputNode
),
/* Recursive CTE to concat all topics together */
InputTopics(inputNode, topics, topicNumber) AS (
      /* The seed for the recursion - all input nodes */
      SELECT inputNode, CAST ('' AS nvarchar(max)), 0 /* max topic handled for node */
      FROM InputTopicNumbers
      GROUP BY inputNode
   UNION ALL /* Add topics that are greater than those processed */
      /* recursively concat topic numbers in ascending order */
      SELECT i.inputNode, CONCAT(c.topics, ' --input-topic=T',i.topicNumber), i.topicNumber
      FROM InputTopics AS c 
      INNER JOIN InputTopicNumbers i ON i.inputNode=c.inputNode
      WHERE i.topicNumber > c.topicNumber
),
/* Bring it all together - append each node with '.exe',
   list the output topic, if present
   Use the recursive CTE to concat all inputTopics */
NodeCommands(node, exe, input, output) AS (
    SELECT nodes.node,
       CONCAT(nodes.node,'.exe'), 
       CONCAT(' --output_topic=T',ot.topicNumber), /* NULL if no output node */
       it.topics
    FROM nodes
    LEFT OUTER JOIN OutputTopics AS ot ON ot.node=nodes.node
    LEFT OUTER JOIN InputTopics AS it ON it.inputNode=nodes.node
)
/* finally our top-level query concatenates the parts to 
   arrive at a single command line */
SELECT CONCAT(
   exe, 
   ISNULL(input, ''),
   ISNULL(output, '')) 
FROM NodeCommands ORDER BY node

Я делаю это с нуля, так что, конечно, там есть несколько синтаксических ошибок. Я надеюсь, что комментарии объясняют намерение.

...