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
Hi JVos,
I've written the recursive part of the task and you have now a list of all descendent for every row.Unfortunately I can't finish it now because of time pressure. I'll continue tomorrow if you don't finish it by yourself till then.
EDIT: The working solution with comments. It creates a list of all descendents for every row and then merges the result with the origin table.
let
Source = Table.FromRows(Json.Document(Binary.Decompress(Binary.FromText("i45WMlTSUTICYpfMotTkEqVYHYiQMaoQSIUJqhBIhSmqEIhrhioE4ppjClkgCcUCAA==", BinaryEncoding.Base64), Compression.Deflate)), let _t = ((type text) meta [Serialized.Text = true]) in type table [From = _t, To = _t, RelationType = _t]),
ChangedType = Table.TransformColumnTypes(Source,{{"From", Int64.Type}, {"To", Int64.Type}, {"RelationType", type text}}),
// get list of all descendants
fnTransitiveRelationList = (sourceTbl as table, curToBeDoneList as list) as list =>
let
curNumber = List.First(curToBeDoneList),
rowsStartingWithCurNumber = Table.SelectRows(sourceTbl, each [From] = 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
}
)
),
recursiveResultList = @fnTransitiveRelationList(sourceTbl, nextToBeDoneList),
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.Distinct(TableOfAllDescentantsTables, {"From", "To"})
in
Result
- JVos7 years agoHelper IV
Hi Nolock: in the basis, I get your solution to work in my Excel file. Two things:
1. Can you shortly explain how you created the Base64 string that is present in your code?
2. With the real data - above I gave a simple example - the query function is running endless. This is maybe because the relations aren't strict transitve. For example:
From To RelationType 67 79 Direct 79 69 Direct 79 71 Direct 71 72 Direct 72 73 Direct 67 94 Direct 94 95 Direct 95 96 Direct Two paths to get from 67 to 71:
67 => 79 => 71
67 => 94 => 95 => 96 => 71
Note that in this real example there are no loops defined. However I need also to cope with such situations.
I am going to try to find a solution building on the code you provided. But if you quickly know how to solve this, I am pleased with your help.
- JVos7 years agoHelper IV
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.
- JVos7 years agoHelper IV
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
- Nolock7 years agoResident Rockstar
You get the Base64 string when you create a table with help of PowerQuery Editor GUI via Home / External Data / Enter Data.
- JVos7 years agoHelper IV
Nolock: Can you help me a little bit more regarding the base64 string, please? The Power Query Editor that starts from Excel doesn't have the 'External Data' group. Excel has on its 'Data' tab the 'Get & Transform Data' group and there the option 'From Table/Range', but that's not giving me a base64 string.