Natural Joins for Schema-free Data.

In this paper, we propose an efficient approach for computing natural joins over schema-free JSON documents. We argue that traditional hash- and sort-based approaches are inapplicable as shared attributes between documents can vary, given the lack of a fixed schema. We propose using a frequent pattern tree (FP-tree) to store a compact representation of the JSON documents and present two algorithms for traversing the constituent nodes to identify results. Through extensive experiments on real-world and synthetic datasets, we show that they have superior performance over the join approaches used in traditional database systems in terms of execution time and memory consumption.