如何从SQL数据执行无向图处理

Question

在为我们的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 DB中，一个表用于节点，另一个表用于边。

现在，我需要动态创建以下形式的字符串

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做过graps。

使用SQL是势在必行的，因为我们也将它用于其他方面。

谢谢!

Answer 1

好了，这是我在这个问题上的尝试。

下面是节点和边表的草图：

[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

我一开始就这么做了，所以肯定有一些语法错误。我希望评论能解释我的意图。