Design Problem: Projecting a JSON

Depth First Search in Action

JSON is the de facto standard for data exchange over the web. Most of the time, just a portion of the JSON response is used; the majority is discarded, resulting in bandwidth waste.

Facebook addressed this problem by introducing GraphQL. GraphQL is a complicated solution, and exploring its pros & cons is beyond the scope of this article. Instead, this article focuses on a custom solution and the associated design decisions.

Designing Query

A client should ask for fields in which it is interested. Projection should be part of the request or query. A projection can be of many types:

• Inclusion Projection: selects given fields only.
• Exclusion Projection: selects all fields except the given fields.
• Renaming Projection: renames given fields.

These projections can be chained together or combined into a single request.

Query Specification

There could be many ways to represent projection specification: a formatted string or structure like JSON itself.

{
  "includes": ["field1",  "field2", ...],
  "excludes": ["field1", "field2", ....],
  "rename": {"oldName": "newName", ...}
}

Due to the conflicting nature of include & exclude projections, only one of them can be applied; so a single request can’t have both include and exclude projections (at least for common fields).

Dot Notation

Dot notation is famously used to refer to fields, or more specifically, “paths to fields.” It is expressed as.

'.parent.child.grandchild.greatgrandchild'

JSONPath formalized the dot-notion and added $ on top to indicate the root; we can omit a full-fledged dot-notion to keep things simple.

// JSON path 
'$.parent.child.grandchild'

Implementing Query

Building Intuition

An object is essentially a tree (or maybe a graph. I will stick to the tree perception.).

For projection, we can iterate over all the paths of “Object Tree” and consider only the matched path for output.

“Depth First Search (DFS)” and “Breath First Search (BFS)” are two candidate algorithms to iterate over a tree.

“Depth First Search (DFS)” is a thoughtful choice when we think of building deep-level selection from the object tree.

Structure of code

We can start with an interface or API for applying projection.

• interface Projection can refer to the query.
• class Projector can be a facade to apply projection.

export interface Projection {
  rename?: { [key: string]: string };
  include?: Array<string>;
  exclude?: Array<string>;
}

export class Projector {
   static apply(obj: any, projection: Projection) {
     let result = obj;
     if (projection.includes) {
        result = new IncludeProjection(obj, project.includes).apply()
     } else if (project.excludes) {
        // not implemented
        result = result;
     } 
     if (projection.rename) {
         // not implemented
         result = result;
     }
     return result;
   }
}

The overall client code looks like as follows:

let x = Projector.apply({
  "username": "dm8typrogrammer",
  "twitterHandler": "@dm8typrogrammer",
  .
  .
  .
}, {
    "includes": ["username"]
})

The data can be sourced from any data store. Projection Query can flow via Network.

It is not feasible to illustrate every projection, as it would make this article into a book. To avoid redundancy, I will only focus on one projection, i.e., inclusion projection.

Digging into Include Projection

class IncludeProjector can encapsulate the code for selecting given fields. The skeleton of the code is as follows:

export class IncludeProjector {
  private obj: any;
  private fields: Set<string>;

  constructor(obj: any, fields: Array<string>) {
    this.obj = obj;
    this.fields = new Set(fields);
  }

 apply() {
    // implementation is pending
    return this.obj;
 }
}

Now, let us focus on implementing apply method.

Case I: No Fields in Selection

The simplest scenario is to return an empty object ({}) if there is no field in the selection.

apply() {
    if ( this.fields == null || this.fields.size == 0) {
        return {};
    }
    else {
        return this.applyOnObject(this.obj, "");
    }
  }
  
  applyOnObject(obj: any, parent: string) {
    // implementation is pending
    return this.obj;
  }

applyOnObject method would contain the implementation of the DFS. Before we go further on this, we need to define two helper methods:

• isPathMatched: detects if the given path is matched against one of the selections.
• isObject: detects if the given value is of Object type or not.

private isPathMatched(key: string) {
   return this.fields.has(key);
}

private isObject(value: any) {
  //ref: https://blog.sarojkdb.com/javascript-isObject/
  return typeof value === 'object' && value !== null && ! Array.isArray(value)
}

Case II: When field selection is not empty

When provided a non-empty list of fields, we can follow the algorithm as:

• Baseline: We start with the given object and consider its parent path as an empty string ".
• Stop Condition: If field path (parent + '.' + field name) is matched against the selection, then we consider the field.
• Recursion: If the current field is an object but not the key we’re searching for, we recursively search its child fields for the possibility of the desired key.

private applyOnObject(obj: any, parent: string) {
  let projectedObj: any = {};
  for (let [key, value] of Object.entries(obj)) {
    if (this.isPathMatched(parent + "." + key)) {
      projectedObj[key] = value;
    } else if (this.isObject(value)) {
      const projectedValue = this.applyOnObject(value, parent + "." + key)
      if (Object.keys(projectedValue).length > 0) {
        projectedObj[key] = projectedValue;
      }
    }
  }
  return projectedObj;
}

The complete code is available at
https://github.com/DM8tyProgrammer/article-projection

Moving Further

My efforts are confined to developing the idea in you by demonstrating a small implementation. It can be extended to incorporate other projection types and JSONPath specifications.

I’m curious to hear your thoughts! Everyone has their own unique solution. Let’s discuss it together!

References

1. JSONPath — Dot Notion
   https://goessner.net/articles/JsonPath/