Forum Discussion
Recursive query to derive indirect relationships
- 7 years ago
Nolock: I worked out the solution to prevent endless loops. In short: the 'froms' that are already done, are remember in a list and not offered to be done in a next recursion. At the end of the query self-referencing transitions are removed.
let Source = Excel.CurrentWorkbook(), tmpInput = Source{[Name="tmpInput"]}[Content], ChangedType = Table.TransformColumnTypes(tmpInput,{{"From", Int64.Type}, {"To", Int64.Type}, {"RelationType", type text}}), // get list of all descendants fnTransitiveRelationList = (sourceTbl as table, curToBeDoneList as list, alreadyDoneList as list) as list => let curNumber = List.First(curToBeDoneList), rowsStartingWithCurNumber = Table.SelectRows(sourceTbl, each [From] = curNumber), alreadyDoneList = List.Combine({alreadyDoneList, {curNumber}}), result = if Table.IsEmpty(rowsStartingWithCurNumber) and List.IsEmpty(curToBeDoneList) then {} else let toList = Table.Column(rowsStartingWithCurNumber, "To"), nextToBeDoneList = List.Distinct( List.Combine( { List.RemoveFirstN(curToBeDoneList, 1), toList } ) ), nextToBeDoneListNoAlreadyDone = List.Difference(nextToBeDoneList,alreadyDoneList), recursiveResultList = @fnTransitiveRelationList(sourceTbl, nextToBeDoneListNoAlreadyDone, alreadyDoneList), curRecursiveResultList = List.Distinct( List.Combine( { toList, recursiveResultList } ) ) in curRecursiveResultList in result, // create a table from all descendants with a from column and relation type = indirect fnTransitiveRelationTable = (sourceTbl as table, from as number) as table => let recursiveList = fnTransitiveRelationList(sourceTbl, {from},{}), recordList = List.Transform(recursiveList, each [From = from, To = _, RelationType = "Indirect"]), result = Table.FromRecords(recordList) in result, // add a column TableOfDescendants TableOfDescendents = Table.AddColumn(ChangedType, "TableOfDescendents", each fnTransitiveRelationTable(ChangedType, [From])), // combine input table with new descendants TableOfAllDescentantsTables = Table.Combine({ChangedType, Table.Combine(TableOfDescendents[TableOfDescendents])}), // distinct on columns From and To Result = Table.SelectRows(Table.Distinct(TableOfAllDescentantsTables, {"From", "To"}), each [From] <> [To]) in Result
Nolock: The duplicate paths to get from 67 to 71 aren't the problem, I found already. I am going to investigate now my complete set with data what might be the problem (probably a loop).
Problem is indeed a loop in the from-to's, e.g. 76 > 77 and 77 > 76.
Nolock: I worked out the solution to prevent endless loops. In short: the 'froms' that are already done, are remember in a list and not offered to be done in a next recursion. At the end of the query self-referencing transitions are removed.
let
Source = Excel.CurrentWorkbook(),
tmpInput = Source{[Name="tmpInput"]}[Content],
ChangedType = Table.TransformColumnTypes(tmpInput,{{"From", Int64.Type}, {"To", Int64.Type}, {"RelationType", type text}}),
// get list of all descendants
fnTransitiveRelationList = (sourceTbl as table, curToBeDoneList as list, alreadyDoneList as list) as list =>
let
curNumber = List.First(curToBeDoneList),
rowsStartingWithCurNumber = Table.SelectRows(sourceTbl, each [From] = curNumber),
alreadyDoneList = List.Combine({alreadyDoneList, {curNumber}}),
result =
if Table.IsEmpty(rowsStartingWithCurNumber) and List.IsEmpty(curToBeDoneList) then
{}
else
let
toList = Table.Column(rowsStartingWithCurNumber, "To"),
nextToBeDoneList = List.Distinct(
List.Combine(
{
List.RemoveFirstN(curToBeDoneList, 1),
toList
}
)
),
nextToBeDoneListNoAlreadyDone = List.Difference(nextToBeDoneList,alreadyDoneList),
recursiveResultList = @fnTransitiveRelationList(sourceTbl, nextToBeDoneListNoAlreadyDone, alreadyDoneList),
curRecursiveResultList = List.Distinct(
List.Combine(
{
toList,
recursiveResultList
}
)
)
in
curRecursiveResultList
in
result,
// create a table from all descendants with a from column and relation type = indirect
fnTransitiveRelationTable = (sourceTbl as table, from as number) as table =>
let
recursiveList = fnTransitiveRelationList(sourceTbl, {from},{}),
recordList = List.Transform(recursiveList, each [From = from, To = _, RelationType = "Indirect"]),
result = Table.FromRecords(recordList)
in
result,
// add a column TableOfDescendants
TableOfDescendents = Table.AddColumn(ChangedType, "TableOfDescendents", each fnTransitiveRelationTable(ChangedType, [From])),
// combine input table with new descendants
TableOfAllDescentantsTables = Table.Combine({ChangedType, Table.Combine(TableOfDescendents[TableOfDescendents])}),
// distinct on columns From and To
Result = Table.SelectRows(Table.Distinct(TableOfAllDescentantsTables, {"From", "To"}), each [From] <> [To])
in
Result- JVos6 years agoHelper IV
Nolock : I noticed a performance issue. Please see: https://community.powerbi.com/t5/Power-Query/Performance-issue-at-expanding-or-combining-tablecolumn/m-p/780163#M26095. If you have any idea...
- Nolock6 years agoResident Rockstar
Hi JVos,
ok, I will look at it. Btw. I will publish a blog post about a transitive closure in Power Query next Tuesday. You can find it then here: https://community.powerbi.com/t5/Community-Blog/bg-p/community_blog