Retrieving hierarchical groups ... with infinite recursion

Question

I have a table like this one that contains links:

key_a key_b -------------- abbc ghagca fg 

not quite neat and endless recursion ...

key_a = parent key_b = child

Require a request that will recompose and assign a number for each hierarchical group (parent + direct children + indirect children):

 key_a key_b nb_group -------------------------- ab 1 ag 1 bc 1 **ca** 1 fg 2 gh 2 **link responsible of infinite loop** 

Since we have

A-B-C-A

-> You just need to show the link as shown.

Any idea?

Thanks in advance

Answer 1

The problem is that you are not dealing with strict hierarchies; you are dealing with directed graphs where some graphs have loops. Note that your nbgroup # 1 does not have a canonical root - it could be a, b or c due to the circular reference from ca.

The main way to deal with this is to think in terms of graph methods, not recursion. In fact, an iterative approach (not using CTE) is the only solution I can come up with in SQL. The basic approach is explained here .

Here is an SQL script with a solution that applies to both loops and the case with a common sheet. Note that it uses iteration (with failover to prevent runaway processes) and table variables to work; I do not think it will cost. Also note the changed sample data (ag changed to ah, explained below).

If you delve into SQL, you will notice that I have changed some key points from the solution indicated in the link. This solution concerned non-oriented edges, while your edges are directed (if you used non-oriented edges, the entire set of samples is the only component due to the ag compound).

This is the reason why I changed ag to ah in my sample data. Your problem specification is simple as long as the common nodes are separated; what specification i encoded. In this case, ah and gh can easily be tied to their own components, because we are worried about parental reachability (even given cycles).

However, when you have common branches, it is not clear what you want to show. Consider the relation ag: in this case, gh can exist in any component (agh or fgh). You put him in the second, but maybe he was the first, right? This ambiguity is why I did not try to solve it in this decision.

Edit: To be clear, in my solution above, if common marriages are found, it treats the whole set as one component. Not what you described above, but it will need to be changed after clarifying the problem. Hope this brings you closer.

Answer 2

You must use a recursive query. In the first part, we select all records that are top-level nodes (do not have parents), and using ROW_NUMBER() , assign them group identification numbers. Then, in the recursive part, we add children to them one by one and use the numbers of the identifiers of the parent groups.

 with CTE as ( select t1.parent,t1.child, ROW_NUMBER() over (order by t1.parent) rn from t t1 where not exists (select 1 from t where child=t1.parent) union all select t.parent,t.child, CTE.rn from t join CTE on t.parent=CTE.Child ) select * from CTE order by RN,parent 

SQLFiddle demo

Answer 3

The painful problem of moving a graph using recursive CTEs. This is the problem of finding related subgraphs in a graph. The challenge with recursive CTEs is to prevent unjustified recursion, that is, endless loops in SQL Server, which usually means storing them in a row.

The idea is to get a list of all pairs of nodes that are connected (and node is connected to itself). Then take a minimum from the list of connected nodes and use it as id for the connected subgraph.

Another idea is to go around the graph in both directions from node. This ensures that all possible sites are visited. The following is a query that does the following:

 with fullt as ( select keyA, keyB from t union select keyB, keyA from t ), CTE as ( select t.keyA, t.keyB, t.keyB as last, 1 as level, ','+cast(keyA as varchar(max))+','+cast(keyB as varchar(max))+',' as path from fullt t union all select cte.keyA, cte.keyB, (case when t.keyA = cte.last then t.keyB else t.keyA end) as last, 1 + level, cte.path+t.keyB+',' from fullt t join CTE on t.keyA = CTE.last or t.keyB = cte.keyA where cte.path not like '%,'+t.keyB+',%' ) -- select * from cte where 'g' in (keyA, keyB) select t.keyA, t.keyB, dense_rank() over (order by min(cte.Last)) as grp, min(cte.Last) from t join CTE on (t.keyA = CTE.keyA and t.keyB = cte.keyB) or (t.keyA = CTE.keyB and t.keyB = cte.keyA) where cte.path like '%,'+t.keyA+',%' or cte.path like '%,'+t.keyB+',%' group by t.id, t.keyA, t.keyB order by t.id; 

SQLFiddle here .

Answer 4

you can check with COMMON TABLE EXPRESSIONS

here is the link