Dexie.js: Storing hierarchical data structures with infinite nesting of objects of same type

[imolorhe]

Hello. I know this is more of a general question on dealing with hierarchical data structures and databases, but I am using Dexie and wanted to know if there are recommended approaches to handling these kinds of scenarios.

So in my use case, I have a collection data type, which is an objection containing:

• name
• description
• a list of queries
• a list of collections

{
  name: '',
  description: '',
  queries: [ ... ],
  collections: [ { name, description, queries, collections }, ... ]
}

The list of collections in the original object each have the same data structure, so having several nested collections.

I have thought about saving the list of collections as a list of collection IDs and also adding a parentCollectionID to each collection, while storing all the collections on the same level in the database, such that I would transform the data after getting it, replacing the IDs with the corresponding collection object (I'm thinking this might be an expensive operation, depending on the number of collections in the database).

I should also point out that the collection objects can be moved from one collection to another collection, in which case I would update all three collections (remove collection ID from original parent collection, add collection ID to new parent collection, and update parentCollectionID in moved collection).

Is there a better approach to handling this scenario, or is there any functionality provided by Dexie to make these kinds of operations more efficient (in developer experience or code performance) to handle?

Thanks! And thanks for building this library. ✌️

[dfahlander]

Hi!

There are various ways to solve this problem, but I prefer the one pattern that it is implemented i postgres hierarchies (ltree):

Let me give an example of how you could implement it using dexie. In this sample the primary key is auto-incremented but does not need to be that. The important thing is the parentPath property.

const db = new Dexie('treedb');
db.version(1).stores({
  tasks: '++id, parentPath'
});

/** Add a top-level task */
async function addRootTask(name) {
   return await db.tasks.add({name, parentPath: ""});
}

/** Add a sub task */
async function addChildTask(name, parentId) {
  const parent = await db.tasks.get(parentId);
  const parentPath = parent.parentPath + parentId + "/";
  return await db.tasks.add({name, parentPath});
}

/** Get a task and include all of its direct children */
async function getTaskWithChildren(taskid) {
   const task = await db.tasks.get(taskId);
   task.children = await db.tasks
     .where({parentPath: `${task.parentPath}${taskId}/`})
     .toArray();
   return task;
}

/** Get a task and include all of its descendants */
async function getTaskWithAllDescendants(taskId) {
   const task = await db.tasks.get(taskId);
   task.descendants = await db.tasks
     .where('parentPath').startsWith (`${task.parentPath}${taskId}/`)
     .toArray();
   return task;
}

/** Move the task from one parent to another
*/
async function moveTask(taskId, newParentId) {
  return await db.transaction('rw', db.tasks, async ()=>{
    const task = await db.tasks.get(taskId);
    const newParent = await db.tasks.get(newParentId);
    if (!newParent) throw new Error("Could not find parent task");
    return await db.tasks.where({id: taskId}) // include the task itself and...
      .or('parentPath').startsWith (`${task.parentPath}${taskId}/`) // ...descendants
      // replace the path prefix on the task + all descendants in one atomic operation
      .modify(t =>
        t.parentPath = t.parentPath.replace(
          task.parentPath,
          newParent.parentPath)
        )
      );
  });
}

When deleting a task, do a similar query as the moveTask(), making sure to delete all descendants with the task...

The key is to utilize the startsWith() method, which is very performant on btree indexes. That way we do not need to traverse the tree recursively to find all descendants.

[imolorhe]

Okay, thanks for the response! I've thought about using the materialized path as well. It seems it has an advantage of being able to index the parent path and directly query a descendant using parent path. Thanks again, this has been useful.