V1 Recurse through links until the end

Users
1

I am attempting to recurse through records with linked parents.

Here is my current attempt, which performs no recursion at all.

{
  :find [?vals]
  :where [
    (parent-chain-for "idnt-AAA" ?vals nil)
  ]
  :rules [
    [
      (parent-chain-for id ?vals ?parent-val)
        [e :xt/id id]          
        [e :val ?val]
        [(get-in ?val [:parents]) [parent-ref ...]]  
        [(get parent-ref :id) parent-id]
        (parent-chain-for parent-id ?parent-val)
        [(conj ?val ?parent-val) ?vals]
    ]
  ]
}

This is an example of the records I’m trying to recurse through, following the parents:

{
  :parents [{:id "acct-BBB"} {:id "acct-CCC"}],
  :xt/id "idnt-AAA"
}

Currently the query only returns the first record, idnt-AAA, and does not recurse through the accts.

In particular, if I [(println ?parent-val)] after the (parent-chain-for-parent-id ?parent-val) line, it’s nil.

I haven’t figured out how to println and have the function continue, so I can’t say what happens throughout the execution. :confused:

I’m trying to return every item, until such time as the parents collection is empty.

Is this the correct approach? What am I missing?

2

Hey @tempire ignoring some of the specifics of your data shapes, this is how to make the recursion work:

(with-open [n (xt/start-node {})]
  (xt/submit-tx n [[::xt/put {:xt/id "idnt-AAA"
                              :parents ["acct-BBB" "acct-CCC"]}]])
  (xt/submit-tx n [[::xt/put {:xt/id "acct-BBB"
                              :parents ["acct-DDD"]}]])
  (xt/submit-tx n [[::xt/put {:xt/id "acct-CCC"
                              :parents []}]])
  (xt/submit-tx n [[::xt/put {:xt/id "acct-DDD"
                              :parents []}]])
  (xt/sync n)
  (xt/q (xt/db n)
        '{:find [?vals]
          :where [(parent-chain-for "idnt-AAA" ?vals)]
          :rules [[(parent-chain-for [?id] ?vals)
                   [?id :parents ?parent]
                   [(vector ?id ?parent) ?accum]
                   (collect-parents ?accum ?parent ?vals)]
                  [(collect-parents [?accum ?parent] ?vals)
                   (not [?parent :parents])
                   [(identity ?accum) ?vals]]
                  [(collect-parents [?accum ?parent] ?vals)
                   [?parent :parents ?parent2]
                   [(conj ?accum ?parent2) ?accum2]
                   (collect-parents ?accum2 ?parent2 ?vals)]]}))
;; => #{[["idnt-AAA" "acct-BBB" "acct-DDD"]] [["idnt-AAA" "acct-CCC"]]}

If you’re able to share a more representative sample of the documents I can give more specific suggestions on how to get it working :slightly_smiling_face:

Cheers,

Jeremy

3

I appreciate the help. This is my actual data structure for each record:

{:val
 ([:tags ()]
  [:uid ([:type "Identifier"] [:id "idnt--AAA"])]
  [:parents (([:type "Identifier"] [:id "acct-BBB"]))]
  [:attrs ([:abitrary "values"])]),
 :type "IDENTITY", 
 :xt/id "a-namespace/idnt--AAA"}

They are cedar authz data structures.

That being said, it might be time to punt and push off the current query until I have time to move to v2. The postgres wire support is a little too tempting, and I’m not sure I’ll ever have the time spend on clojure expertise.

Does v2 SQL have the ability to do recursion?

1 Like
4

Thanks for the example. If you can create a small tree of linked entities like that then I could help get it working with the nested lookups also.

I’m assuming every instance of ([:key1 val1] ... ) (i.e. “a list of map entries”) is really supposed to be a Clojure(/edn) map - is that just how you’re observing your maps when you retrieve them? Or are you intentionally working with these lists like this explicitly?

v2 SQL can’t do full recursion just yet, but you can query N-layers deep easily enough using CTEs - I shared an example in this other thread: XTDB's Sweet Spot - #9 by refset

Hope that helps!