Help with Tree Traversal in Power Query

[isg]

Hi everyone,

First of all, full disclosure: I am not at all a Power Query expert. I had a great success getting a solution by posting in this forum last time so I'm posting again in hopes that you all Power Query experts would be able to help me with another problem.

I essentially have a data set that is supposed to look like a tree. Below is an example:

The corresponding data to the above chart is as below (sorry, formatting is difficult in this forum).

PrimaryKey	Data1	Data2	Data3		ForeignKey	FK Data1	FK Data2	FK Data3
0001	Data1_1	Data2_1	Data3_1
0002	Data1_2	Data2_2	Data3_2
0003	Data1_3	Data2_3	Data3_3
0004	Data1_4	Data2_4	Data3_4		0001	Data1_1	Data2_1	Data3_1
0005	Data1_5	Data2_5	Data3_5		0001	Data1_1	Data2_1	Data3_1
0006	Data1_6	Data2_6	Data3_6		0004	Data1_4	Data2_4	Data3_4
0007	Data1_7	Data2_7	Data3_7		0005	Data1_5	Data2_5	Data3_5
0008	Data1_8	Data2_8	Data3_8		0002	Data1_2	Data2_2	Data3_2
0009	Data1_9	Data2_9	Data3_9		0002	Data1_2	Data2_2	Data3_2
0010	Data1_10	Data2_10	Data3_10		0002	Data1_2	Data2_2	Data3_2
0011	Data1_11	Data2_11	Data3_11		0002	Data1_2	Data2_2	Data3_2
0012	Data1_12	Data2_12	Data3_12		0009	Data1_9	Data2_9	Data3_9
0013	Data1_13	Data2_13	Data3_13		0009	Data1_9	Data2_9	Data3_9
0014	Data1_14	Data2_14	Data3_14		0011	Data1_11	Data2_11	Data3_11
0015	Data1_15	Data2_15	Data3_15		0003	Data1_3	Data2_3	Data3_3
0016	Data1_16	Data2_16	Data3_16		0003	Data1_3	Data2_3	Data3_3
0017	Data1_17	Data2_17	Data3_17		0003	Data1_3	Data2_3	Data3_3
0018	Data1_18	Data2_18	Data3_18		0003	Data1_3	Data2_3	Data3_3
0019	Data1_19	Data2_19	Data3_19		0003	Data1_3	Data2_3	Data3_3

I want to be able to input the PrimaryKey value, and get all the data "under" the value inputted based on the tree chart. Below is an example input and expected output.

Data Input:

Search PrimaryKey

0001

0009

0015

Data Output:

PrimaryKey	Data1	Data2	Data3		ForeignKey	FK Data1	FK Data2	FK Data3
0001	Data1_1	Data2_1	Data3_1
0004	Data1_4	Data2_4	Data3_4		0001	Data1_1	Data2_1	Data3_1
0005	Data1_5	Data2_5	Data3_5		0001	Data1_1	Data2_1	Data3_1
0006	Data1_6	Data2_6	Data3_6		0004	Data1_4	Data2_4	Data3_4
0007	Data1_7	Data2_7	Data3_7		0005	Data1_5	Data2_5	Data3_5
0009	Data1_9	Data2_9	Data3_9		0002	Data1_2	Data2_2	Data3_2
0012	Data1_12	Data2_12	Data3_12		0009	Data1_9	Data2_9	Data3_9
0013	Data1_13	Data2_13	Data3_13		0009	Data1_9	Data2_9	Data3_9
0015	Data1_15	Data2_15	Data3_15		0003	Data1_3	Data2_3	Data3_3

So, if the input is 0001, 0002, 0003, it would output everything.

Currently, I am doing a manual iteration where:

1. I merge input with the PrimaryKey
2. Merge input with the ForeignKey then append to #1
3. Then I merge the appended table to the ForeignKey again and append that to #2.
4. Remove duplicates.
5. Then I merge input again, etc..

This is not an ideal algorithm as I would not have to manually stop the merging + append + deduplication. I want to the script to basically do that automatically for me when it sees that there are no other "nodes" to reiterate through.

My idea is to have a reiteration with a counter, so when the count of rows in the output table = the number of rows after deduplication, it will stop the reiteration. However, I have no idea how to set that "while" recursion in M. Is this something that would be possible in Power Query? Or should I view the data / procedure in a different perspective?

Let me know if I am not making any sense with my questions and I can edit the post to clarify!

[ThxAlot]

A side question, are you engaged in data analysis related job?

Your question is of typical graph traversal algorithm type. I myself once spent a whole weekend to implement the most classic "depth first search" algorithm in PQ (although PQ isn't an ideal tool to handle recursion)

let
    DFSfx = (_nodes as list) =>
    List.TransformMany(
        _nodes,
        each let neighbors = Record.FieldOrDefault(graph, _, null) in if neighbors is null then {{}} else @DFSfx(neighbors),
        (x,y) => {x} & y
    ),

    Source = Table.FromRows(Json.Document(Binary.Decompress(Binary.FromText("i45WMjAwMFTSUVKK1QGzTYBssBCUb4rGN4PwTWB8cwjfFMa3hPCNoHxDIwjfEsY3RuNDzTdWio0FAA==", BinaryEncoding.Base64), Compression.Deflate)), let _t = ((type nullable text) meta [Serialized.Text = true]) in type table [PrimaryKey = _t, ForeignKey = _t]),
    #"Changed Type" = Table.TransformColumnTypes(Source,{{"PrimaryKey", type text}, {"ForeignKey", type text}}),
    #"Grouped by ForeignKey" = Table.Group(#"Changed Type", "ForeignKey", {"Value", each Table.Column(_, "PrimaryKey")}),
    graph = Record.FromTable(Table.RenameColumns(#"Grouped by ForeignKey", {{"ForeignKey","Name"}})),
    Traversal = DFSfx({"0001","0009","0015"})
in
    Traversal

[slorin]

Hi

Another solution

let
Source = YourSource,
Keys = Record.FromList(Source[ForeignKey], Source[PrimaryKey]),
Search = {"0001","0009","0015"},
Test = (Actual) as logical=> 
  if Actual = null then false 
  else if List.Contains(Search, Actual) then true 
  else @Test(Record.FieldOrDefault(Keys, Actual, null)),
Result = Table.SelectRows(Source, each Test([PrimaryKey]))
in
Result

Stéphane

[oussamahaimoud]

Hi @isg,

Hope you're doing well!

I had to solve this problem before.I recommend you to Use List.Generate to iteratively expand the set of matched PKs by checking which rows have a ForeignKey that's already in your matched set. Stop when no new rows are added (i.e., the count stabilizes).

So, paste this as a new blank query (M):

let

    // Your source tables — adjust names as needed

    Source = YourDataTable,

    InputKeys = YourInputTable, // single column: [SearchPrimaryKey]

    // Convert input to a list

    SeedKeys = List.Transform(InputKeys[SearchPrimaryKey], Text.From),

    // Iteratively expand the key set

    ExpandedKeys = List.Last(

        List.Generate(

            () => SeedKeys,

            (current) => 

                List.Count(

                    List.Union({

                        current,

                        List.Transform(

                            Table.SelectRows(

                                Source, 

                                each List.Contains(current, Text.From([ForeignKey]))

                            )[PrimaryKey],

                            Text.From

                        )

                    })

                ) > List.Count(current),

            (current) =>

                List.Union({

                    current,

                    List.Transform(

                        Table.SelectRows(

                            Source, 

                            each List.Contains(current, Text.From([ForeignKey]))

                        )[PrimaryKey],

                        Text.From

                    )

                })

        )

    ),

    // Filter source to only matched rows

    Result = Table.SelectRows(Source, each List.Contains(ExpandedKeys, Text.From([PrimaryKey])))

in

    Result

For large datasets, this can be slow since each iteration re-scans the full table. If performance is a concern, converting the source to a list of records before the loop will help significantly.

Assisted by AI for clarity of wording.

Hope this helps! Don't forget to accept as solution ✅ and like it 👍 in order to keep helping others.

Best regards,

Oussama (Data Consultant - Expert Fabric & Power BI)