Balisage Paper: Automatically Denormalizing Document Relationships

Incomplete views

The fundamental problem with references is that accessing a complete view of a document with references requires traversing it and constructing its missing content dynamically using joins. For each document we must find its references, get the referenced documents from the database, and insert them into the expanded view.

In the context of result sets, this effect is multiplied, and the overhead for generating complete views on a set of documents is no longer simply a factor of the number of documents selected by a query, but of that number plus the number of referenced documents in the result set. Performance-sensitive applications will need to ensure that a small result set of documents with many references does not result in an explosion of reads. In some cases, that will not be necessary, or it can be mitigated. For example, in a page of query results, the application can choose not to expand references when rendering results and only expand an individual document once it has been selected. But it is often the case that the application needs to address aspects of the expanded view in queries, which brings us to the next problem.

When using key-based relationships, search applications may be forced to support queries with constraints that join data across documents. For example, using the attorneys and clients model above, we may need to generate a query that selects “attorneys living on the west coast representing a client on the east coast.” This query includes a pair of related constraints, each in a different set of documents associated by ID/IDREF relationships. When the query is executed, it will need to read both sets of documents with constraints applied and join them together based on the criteria that they are related via ID and IDREF. Even a selective query with few results may, in the worst case, produce an explosion of document reads due to the fact that the selectivity of the query hinges only on the intersection of constraints, not any per-document constraint.

          

  let $states-west := (‘CA’, ‘OR’, ‘WA’)
  let $states-east := (‘ME’, ‘NH’, ‘RI’, ... , ‘FL’)
  let $attorneys-west := //attorney[state = $states-west]
  let $clients-east := //client[state = $states-east]
  return $attorneys-west[attorney-client/@idref = $clients-east/@id]
        

If either $attorneys-west or $clients-east selects a large number of documents, the overhead to perform this query will be high. It might be improved by selecting the east coast clients first, using their ids to add an additional constraint to the attorneys, increasing selectivity:

  ...
  let $clients-east := //client[state = $states-east]
  return //attorney[attorney-client = $clients-east/@id][state = $states-west]
        

However, it is possible that $clients-east still leads to overhead or that serializing the queries prevents the query engine from executing them in parallel. Ultimately, the best optimizations may be data and implementation-dependent, resulting in queries that are difficult to write and maintain, especially as the content of the database changes.

Another common application requirement is displaying search facets, wherein aggregated data about a query’s full set of results are displayed alongside a subset of sorted results displayed as snippets. Conventionally, search snippets are hyperlinked to a more complete view of the item represented in the paged set, and facets are hyperlinked to a query that returns a new result set constrained by the property and value indicated by the facet.

Figure 6: Search results

Most XQuery databases provide configurable indexes for efficiently querying specified path or element values that can be used to facilitate fast faceted search calculations. It is not currently possible, however, to create an index for a document using values from a referenced document, so there are no shortcuts around manual joins using indexes. Like the first example, calculating facets for documents outside the result set requires joining across both sets documents using XQuery:

  let $client-results := //client[(: implementation-specific full text constraint :)]
  let $client-attorney-refs := $client-results/client-attorney/@idref
  return subsequence(
      for $attorney in //attorney[@id = $client-attorney-refs]
      let $count := count($client-results[client-attorney/@idref = $attorney/@id])
      order by $count descending
      return <attorney-facet value=”{ $attorney/full-name }” count=”{ $count }” />,
      1, 5)
        

Best practices for handling these types of use cases in different database implementations have different conventions with respect to indexing and query optimization that can be unintuitive,^[6][7] and building a solution to support joins generically within an application can be tricky and still lead to variable or disappointing performance. Armed with the implementation-recommended indexing and query patterns, it is possible to minimize the impact of joins, but depending on the database implementation and application, it may still be necessary to put hard limits on the size of result sets or drop some of the harder to calculate information from the aggregate queries to prevent high latency queries.

Runaway code

One issue that may be less obvious at the outset, but can be insidious and capable of having a strong impact, is the fragmenting effect on code that can occur from introducing a new paradigm into an application and maintenance problems that result from adding complexity and managing it as the application scales. At a high level, combining self-contained document models with relational-like data models ties together contrasting concepts for reading and writing information within an application. As outlined above, solutions built to handle querying across related documents will introduce coding patterns that diverge from those of fully coherent documents.

Software developers typically follow design principles and utilize coding patterns as they work, in many cases religiously. Despite the fact that many principles overlap or conflict, and various trends come and go over time, they all seem to work toward the same goal: preventing code complexity from ballooning out of control. Whether or not any particular set of maintenance strategies is more effective than another is a topic of debate (and unfortunately very little research), but experience has taught the industry as a whole that some strategy is necessary to continuously reduce complexity through the implementation of abstractions, modularization, limiting dependencies, and code reuse.

Applications take on expanded requirements over time, and it is critical for maintainers to carefully examine their designs and refactor as code is updated to implement new features. The different coding patterns introduced in examples above to support the diverging document concepts can negatively affect nearly every aspect of code maintenance. Even in applications that are not performance critical, avoiding the introduction of these types of queries and runtime dependencies can result in code that is simpler to reason about, organize, and maintain as it scales.

Relationship create

Creating a denormalized many-to-many relationship follows similar steps as the normalized two-way IDREF solution, and in both cases, both documents must be updated. In the normalized create, only an element denoting a reference to the other is added; in the denormalized create, the contents of the referenced document are used wholesale in place of the reference. One new requirement is that a denormalized create must read-on-update to exchange content. Typically, lock contention will not differ when reading from a document that is also updated in the same transaction, so the added overhead of denormalizing this operation can be minimal.^[8]

Figure 8: Create denormalized relationship

This example creates a relationship on documents with no existing relationships. However, when relating or updating documents that already have denormalized relationships, the copied entities stored in <ref:copy> should not also include their copied references. From the perspective of the containing entity, the relationships within a copied entity are either circular, or they will reference documents that do not have references back, leaving no way to update them consistently when the canonical document is updated. Therefore, an entity copy transformation should be used to remove existing denormalized relationships from any dereferenced copy.

Figure 9: Entity copy transformation

Related document update

Now that references are replaced with denormalized copies of the canonical entity’s data, updating a document requires updating every document on the other side of the relationship as well. Similar to the normalized model, where reading a complete document required expanding every reference to a canonical document, now to maintain consistency, any document update requires propagating the new information to its denormalized copy in referenced documents.

Figure 10: Updating a related document

This step is the essence of the denormalization process because it is responsible for maintaining consistency across related documents. It deliberately defies one of the original stated design goals of the relational model and normal form - to free relations from insert, update, and delete dependencies. The primary reason behind that goal was the expectation that managing dependencies would quickly become complex or impractical (or a problem writing to storage hardware would occur), leading to “update anomalies galore” [Codd1990], and inconsistencies across related data would accumulate throughout the database.

The automatic denormalization process proposed here can be implemented in a single component capable of handling any update operation. As a practical matter, maintenance of the component to support changes to the data model is simple, and in many cases (depending on the database) the component can be written to handle generic references, such that code changes would only be required if the denormalization schema itself changes. BaseX, eXist-db, and MarkLogic all provide methods to apply cascading updates atomically, within a single transaction, eliminating a class of possible undesirable side effects from managing redundant data, one of the motivating factors behind normalization.

Because the number of relationships per document will typically not grow relative to the size of the database, avoiding joins across large portions of the database can also be a worthwhile performance trade-off for cascading document updates. However, the comparison is not apples-to-apples, since writing to a database is a more resource intensive operation than reading from it. Also, the details of lock handling across database implementations differ (and some are configurable), so performance testing for any specific implementation and configuration is appropriate if the likely trade-off is not clear from an application’s requirements or usage information.

Delete

Denormalized delete follows the same pattern as update, but without the need for the entity copy transformation step. When a document is deleted, iterate over its references and remove the copy in any referenced document. Deleting a relationship follows the inverse pattern of create.

Read

Now that work has been done on the create/update/delete side to ensure consistent denormalized relationships, documents have been restored to a prototypical document structure.

<attorney id="123">
  <name>Johnny Cochran</name>
  <ref:copies>
    <client id="abc">
      <name>O.J. Simpson</name>
    </client>
  </ref:copies>
</attorney>

<attorney id="456">
  <name>Robert Shapiro</name>
  <ref:copies>
    <client id="abc">
      <name>O.J. Simpson</name>
    </client>
  </ref:copies>
</attorney>

<client id="abc">
  <name>O.J. Simpson</name>
  <ref:copies>
    <attorney id="123">
      <name>Johnny Cochran</name>
    </attorney>
    <attorney id="456">
      <name>Robert Shapiro</name>
    </attorney>
  </ref:copies>
</client>
        

Rendering documents with relationships no longer necessitates a runtime expansion process to produce a complete view, and it is possible to query related documents without joining. The additional consistency across queries and rendering components should provide more opportunities for code reuse and less complexity to maintain overall.

The pathological query from above - “return any attorney working on the west coast representing a client on the east coast” - is now simplified and is structured more optimally for query evaluation. Additionally, indexing state elements will now be effective at preventing the database from reading documents from disk before a result set is determined.

  //attorney[state = $states-west][ref:copies/client/state = $states-east)]

Similarly, the facet-calculating query example from above can also be simplified without the need for joining and can benefit even further by leveraging the indexing capabilities in MarkLogic or eXist. Because those databases provide functions to access index values directly, indexing the path /client/ref:copies/attorney/full-name permits even more efficient calculation of facets.

let $facets := cts:values(
  cts:path-reference("/ref:copies/attorney/full-name", 
  (), "limit=5", $client-query)
for $f in $facets 
let $count := cts:frequency($f)
order by $count descending

return <attorney-facet value="{ $f }" count="{ $count }" />

          

let $facets := util:index-keys(
  $client-results/ref:attorney/full-name, (), 
  function($key, $count) { 
    <attorney-facet value="{ $key }" count="{ $count[2] }" />
    }, 5, "lucene-index")
for $f in $facets
order by $f/@count
return $f

          

Without the need to join data across documents, the need for nebulous (and often unsuccessful) optimizations is avoided, and with related documents conforming to the self-contained structure of other documents, integrating two disparate data models is no longer necessary, avoiding a class of thorny code maintenance problems.

Caveats

Only recommended for two-way joins

For example, a LawFirm entity may have a many-to-many relationship with an Attorney entity, which also has a many-to-many relationship with a Client entity.

Figure 14: 3-way many-to-many relationship

Using only the technique described here, it is not possible to get denormalized data about Clients from LawFirms and vice versa. It is possible to modify the entity copy transformation to retain references for entities such that an entity’s references and its references’ references are part of the cascading update. But this is dangerous behavior that may result in combinatorial explosions of updates and it can quickly become impractical for most use cases.

Extensions and Optimizations

Entities and sub-entities

In real-world models, it is often unrealistic to insist that relationships occur only between document roots. Instead, it is more idiomatic to consider a document as an entity that may contain descendant subentities recursively, such that any entity or sub-entity can be related to any other entity or sub-entity.

Figure 15: Sub-entities

Additionally, it may be helpful when generating a copy of a sub-entity to also include data about that entity’s parent or ancestors. This pattern can be managed through modifications to the entity copy transform (used above only to remove references) and to update behavior. When an entity is copied, process the parent or ancestors recursively, and when an entity is updated, trigger updates on its child or descendant sub-entities. The structure of the denormalized ancestor markup should be determined by the application. In some cases, the application may benefit from maintaining the nested structure of the related document in its copy and annotating the directly-related entity:

    <client id="abc">
      <name>O.J. Simpson</name>
      <address> ... </address>
      <client-instance id="1357" id-client="abc">
        <name> ... </name>
        <address> ... </address>
        <ref:copies>
          <attorney> 
            <name>Johnny Cochran</name>
            ...
            <ref:context>
              <matter>
                <name>People v. O. J. Simpson</name>
                <judge>Lance Ito</judge>
                <dt-arraignment>1994-06-20T09:00:00-07:00</dt-arraignment>
              </matter>
            </ref:context>
          </attorney>      
        </ref:copies>
      </client-instance>
    </client>
          

In another, it may be more convenient to break the hierarchy into siblings and annotate the entities:

    <ref:copies>
      <ref:copy>
        <ref:context>
          <matter>
            <name>People v. O. J. Simpson</name>
            <judge>Lance Ito</judge>
            <dt-arraignment>1994-06-20T09:00:00-07:00</dt-arraignment>
          </matter>
        </ref:context>
        <ref:parent>
           <attorney> 
             <name>Johnny Cochran</name>
             ...
           </attorney>
        </ref:parent>
      </ref:copy>
    </ref:copies>
          

The annotation schema is not prescriptive and should be adapted to fit the needs of the application, so other variations may be appropriate. For example, relationship annotation elements could be children of entities instead of parents, or they may be attributes on the copied element.

Overlapping hierarchies

Sometimes a model may not call explicitly for a many-to-many relationship, but it may have naturally overlapping one-to-many relationships. Overlapping data structures are not supported by the XML model directly, but they can be approximated using many-to-many relationships.

Figure 16: Overlapping documents

In this scenario, one of the trees may be modeled as the “base” document, and overlapping trees may be modeled using many-to-many relationships between the shared entity of the base document and the parent entities of the overlapping documents. Using automatic denormalization, overlapping hierarchies can be stored as separate and completely coherent documents.

  declare function ref:make-copy($source as element(), $target as element()) as element()
  {
    typeswitch($source)
    (: Rules based on copied entity :)
    case element(attorney) | element(client) return 
      From: Attorney or Client + To:Anything rules
    case element(matter) return 
      (: Combination rules :)
      typeswitch($target)
      case element(client) return From:Matter + To:Client rules
      default return From:Matter + To:Not-Client rules
    default return
      typeswitch($target) return
      (: Rules based on containing entity :)
  }