How to perform undirected graph processing from SQL data

Question

I ran into the following problem in dynamically creating topics for our ActiveMQ system:

I have a number of processes (M_1, ..., M_n), where n is not large, typically 5-10. Some of the processes will listen to the output of others, through a message queue; these edges are specified in an XML file, e.g.

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

etc. The edges are sparse, so there won't be many of them. I will parse this XML and store this information in an SQL DB, one table for nodes and another for edges.

Now, I need to dynamically create strings of the form

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 

where the tags are sequentially generated. What is the best way to go about querying SQL to obtain these relationships? Are there any tools or other tutorials you can point me to? I've never done graps with SQL.

Using SQL is imperative, because we use it for other stuff, too.

Thanks!

Answer 1

Ok, here's my stab at the problem.

Here's a sketch of the nodes and edges tables:

[nodes]
node : varchar(xx)

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

Assuming your db has support for CTEs, then a query structured like this will bring together the relationships and concatenate results:

/* 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

I'm doing this off the bat, so surely a few syntax errors in there. I hope the comments explain the intent.