adjacency list to nested dictionary

[Horcle]

I have the following SQLAlchemy class representing an adjacency list:

class Node(db.Model):

    __tablename__ = 'meds'

    id = Column(Integer, primary_key=True)

    type = Column(String(64))

    name = Column(String(64))

    parent_id = Column(Integer, ForeignKey('node.id'))

    children = relationship("Node")

I need to create a dictionary to represent a tree of arbitrary depth that would look like:

{
"children": [
    {
      "children": [
        {
          "id": 4,
          "name": "Child1",
          "parent_id": 3,
          "type": "Parent 2"
          "children": [
            {
              "id": 6,
              "name": "Child3",
              "parent_id": 3,
              "type": "Parent 3",
              "children": [...]
            },
            {
              "id": 7,
              "name": "Child4",
              "parent_id": 3,
              "type": "Leaf"
           }
          ]
        },
        {
          "id": 5,
          "name": "Child2",
          "parent_id": 3,
          "type": "Leaf"
        }
      ],
      "id": 3,
      "name": "CardioTest",
      "parent_id": null,
      "type": "Parent"
    }
  ]
}

Can this dictionary be built non-recursively? I am not sure how to manually do this otherwise. 

Thanks in advance!

Greg--

[Jeff Widman]

What database are you using? 

Are you trying to solve data insert or retrieval? 

Do you want to do your traversal in your app or use SQLAlchemy to generate a SQL query that does all the work within the DB and then returns the result? 

ᐧ

--
You received this message because you are subscribed to the Google Groups "sqlalchemy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sqlalchemy+...@googlegroups.com.
To post to this group, send email to sqlal...@googlegroups.com.
Visit this group at https://groups.google.com/group/sqlalchemy.
For more options, visit https://groups.google.com/d/optout.

--

Jeff Widman

jeffwidman.com | 740-WIDMAN-J (943-6265) 

<><

[Horcle]

We're using MySQL and need retrieval of all data from the table in the format given (nested JSON). Simplest solution would be good (whether in app or SQLAlchemy). I tried using the JsonSerializer as noted here http://stackoverflow.com/questions/30367450/how-to-create-a-json-object-from-tree-data-structure-in-database, but could not get it to work. 

Thanks!

Greg--

[Jeff Widman]

You've got to separate issues here--one of retrieving the data, and the second of serializing it to JSON. They're related, but perhaps easier to solve if you mentally think of them as distinct problems.

Since you're storing the data as an adjacency list, then you'll need to either use a recursive function or a while loop to traverse the database up/down levels of the tree. There's no avoiding that unfortunately. (Technically if you know the maximum depth of the tree you could use a for loop, but I would never do that because it isn't future-proof.)

AFAIK MySQL doesn't support Recursive CTEs--there are some hacks posted on StackOverflow, but it'll almost certainly be eaiser to do this within your app (although slow because for each level of the tree you're issuing a new query, processing it within your app, and then re-issuing a new query for the next level up or down the tree).

For serializing the data as nested JSON, I hear good things about marshmallow's support for nested json. You could certainly write your own function, it's just Marshmallow provides some niceties like allowing you to specify the maximum nesting depth: https://github.com/marshmallow-code/marshmallow/issues/9

If I were doing it, my first prototype would probably write two functions--one that maps the adjacency list in SQL to an equivalent list of lists in Python, and then a second that unwraps the python lists and serializes them into nested marshmallow json. From there it'll be easier to decide if it's worthwhile to eliminate the python lists of lists by doing the serializing inline with traversing the adjacency list.

ᐧ

[Horcle]

Thanks for the advice and for confirming my suspicions. I did find a solution here using CTEs, but yes,  I know MySQL definitely does not support them. I'll definitely take a look at Marshmallow.

Greg--