With data lakes and schema-free NoSQL document stores, extracting a descriptive schema from JSON data collections is an acute challenge. In this paper, we target the discovery of tagged unions, a JSON Schema design pattern where the value of one property of an object (the tag) conditionally implies subschemas for sibling properties. We formalize these implications as conditional functional dependencies and capture them using the JSON Schema operators if-then-else. We further motivate our heuristics to avoid overfitting. Experiments with our prototype implementation are promising, and show that this form of tagged unions can successfully be detected in real-world GeoJSON and TopoJSON datasets. In discussing future work, we outline how our approach can be extended further.
JSON is a popular data exchange format. Extracting a
schema from collections of JSON documents is a
realworld challenge which is actively being researched [
Ideally, the extracted schema describes the data tightly, yet without overfitting. In this article, we target the detection of a specific schema design pattern in the JSON Schema language, the pattern of tagged unions, also known as discriminated unions, labeled unions, or variant types.
This is a recommended design pattern [9], and has been found to be quite common in real-world schemas [10].
Example 1. Figure 1 shows GeoJSON data. The array starting in line 2 holds four objects, of type Point and LineString. Point coordinates are encoded as an array of numbers, while lines are encoded as an array of points, and hence, an array of number arrays.
The GeoJSON specification (IETF RFC 7946, clickable link embedded in the PDF) describes six types of geometries, including polygons and multi-polygons. Consistently, the property type serves as a tag to distinguish the subschema of sibling property coordinates, thereby instantiating a tagged union.
GeoJSON comes without an oficial JSON Schema
specification [ 11]. In Figure 2, we therefore show a
handcrafted excerpt using the if-then-else construct to
enforce the tagged union, with the following
semantics: If the object in question has a property labeled
1 { " type ": " GeometryCollection ",
2 " geometries ": [
3 { " type ": " Point ",
4 " coordinates ": [30 ,10] },
5 { " type ": " Point ",
6 " coordinates ": [
Example 2. Various schemas listed on SchemaStore.org, a community-curated collection of JSON Schema declarations, encode tagged unions using if-then-else.
Among them are the Minecraft schemas which use tagged unions to encode so-called data packs for configuring Minecraft worlds. Other examples are Github Issue Forms, or the cloudify schema (clickable links in the PDF).
In schema extraction, the detection of tagged unions has so far received limited attention: Several approaches are able to detect union types, i.e., properties whose type is a union of types, but they do not detect the dependency w.r.t. a specific property value (the “tag” in the tagged union). Figure 3a shows an example: This schema for GeoJSON data does not restrict the values for property type (it allows all strings) and allows alternative © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License subschemas for property coordinates. As it is overly ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) general, the schema allows to encode lines as mere ar" type ": { " const ": " Point " } },
" items ": { " type ": " number " } } } }, " properties ": { " required ": [ " type " ] },
" type ": { " const ": " LineString " } }, 3 7 8 9 11 12 13 14 15 16 17 18 19 20 21 5 " then ": { 6 " properties ": { " coordinates ": {
" type ": " array ", 10 " else ": { "if ": { " then ": { " properties ": { " coordinates ": { " type ": " array ", " items ": { " type ": " array ",
by state-of-the-art third-party tools. • Our experiments on real-world GeoJSON datasets (and its sibling format TopoJSON) show that meaningful tagged unions can indeed be identified. We illustrate the impact of a configurable threshold on the number of tagged unions detected, and consequently, the size of the extracted schema.
We further outline promising directions of future work.
Structure of this paper. In Section 2, we introduce Section 4, we present our approach, specifically the architecture and heuristics employed, and an outlook on future extensions. In Section 5, our experiments are presented rays of numbers (rather than arrays of number-arrays), and discussed. In Section 6, we draw our conclusions and " items ": { " type ": " number " } } } } } } in violation of the GeoJSON specification.
Existing approaches to JSON Schema extraction fail to detect tagged unions. Notably, in describing their approach to schema extraction based on typing JSON values, Baazizi et al. [2] outline how their approach can be extended to include tagged unions. However, they do not discuss strategies against overfitting to the input data during the discovery of tagged unions.
on a relational encoding of JSON objects from which we then derive conditional dependencies. A central part of our contribution are our heuristics, which filter out dependencies that have insuficient support in the input data, so that they are not reflected in the derived schema. Specifically, ours is the first proposal towards the discovery of tagged unions that — to our knowledge — includes an experimental evaluation over real-world data. Contributions. This paper makes the following contributions: • We target the detection of tagged unions in JSON schema extraction, specifically, tagged unions that are based on dependencies between a property value and the implied subschema of its sibling properties. • Our approach relies on the discovery of unary constant conditional functional dependencies in a relational encoding of the JSON objects. Traditionally, conditional functional dependencies are employed in the context of data cleaning, and we apply them to a new domain. • Our approach is composable with existing algorithms for JSON schema extraction, as we impose the tagged unions on top of the schemas derived discuss opportunities for future work.
2.1. JSON Data Model and JSON Schema
The grammar below (adopted from [13]) captures the syntax of JSON values, namely basic values, objects, or arrays.
Basic values
include the null value, Booleans, numbers , and strings . Objects
represent sets of members, each member being a name-value pair, arrays represent sequences of values. ::= | |
::= null | true | false | | ::= { 1 : 1, . . . , : } ::= [ 1, . . . , ] ≥ 0
∈ Num, ∈ Str ≥ 0, ̸= ⇒ ̸= JSON Schema. JSON Schema is a language for defining the structure of JSON documents. The syntax and semantics of JSON Schema have been formalized in [14], and we informally present some of the main keywords:
Assertions include required, enum, const, pattern and type, and indicate a test that is performed on the corresponding instance.
Applicators include the Boolean operators not, anyOf, allOf, oneOf, as well as, if-then-else. They further include the object operators patternProperties, additionalProperties, and properties, and the array operator items, and the reference operator $ref.
They apply a diferent operator to the same instance or to a component of the current instance.
Annotations (title, description, and $comment) do not afect validation but indicate an annotation associated to the instance. 1 " anyOf ": [ 2 { " type ": " object ", 3 " properties ": { 4 "type": { "type": "string" }, 5 " coordinates ": { 6 " type ": " array ", 7 " items ": { " type ": " number " } } } 8 }, 9 { " type ": " object ", 10 " properties ": { 11 "type": { "type": "string" }, 12 " coordinates ": { 13 " type ": " array ", 14 " items ": { " type ": " array ", 15 " items ": { " type ": " number " } 16 } } } } ] 1 " anyOf ": [ 2 { " type ": " object ", 3 " properties ": { 4 "type": { "const": "Point" }, 5 " coordinates ": { 6 " type ": " array ", 7 " items ": { " type ": " number " } } } 8 }, 9 { " type ": " object ", 10 " properties ": { 11 "type": { "const": "LineString" }, 12 " coordinates ": { 13 " type ": " array ", 14 " items ": { " type ": " array ", 15 " items ": { " type ": " number " } 16 } } } } ] (a) Union type.
(b) Tagged union.
Union types A property with several possible types “Point” with coordinates encoded as an array of numbers
(or subschemas) can be described as a union type [
Tagged unions The if-then-else operator allows for declaring tagged unions, and was introduced (rather 2.2. Dependencies recently) with JSON Schema Draft 7.
In Example 1, we informally introduced the semantics. For the relational model, the concept of functional depenAs for terminology, we distinguish one property as the dencies is well explored, and various generalizations are tag (in our example, the property labeled type), and known, such as conditional functional dependencies [16] identify one or more properties with implied subschemas which only apply to a subset of the tuples. In the follow(in our example, for coordinates). ing, we extend these notions to JSON data, assuming a
The tag-property may go by any name. While the relational encoding of all objects that are reachable by schemas for GitHub Issue Forms and cloudify from Ex- the same path from the document root. This idea of a ample 2 incidentally also rely on a tag labeled “type”, in relational encoding of semi-structured data for the definithe example of Minecraft (see data snippets in Figure 5), tion or detection of dependencies is a common approach, the tag-property is labeled “condition”. e.g., for XML [17], JSON [18], or RDF data [19].
An alternative encoding for tagged unions is to use a
union operator, as shown in Figure 3b. Two diferent com- Relational encoding Given a JSON value, we consider
binations of values for property type and subschemas all labeled paths from the root to a JSON object. Paths
for property coordinates are given in accordance with may be encoded in JSONPath [
We next introduce the schema for our relational en- Dependencies We next introduce dependencies over coding. We reserve attribute . id for an (internal) object this relational encoding. Traditional functional depenidentifier. The object identifier must be unique, but we dencies (FDs) capture constraints that hold on all tuples do not impose any constraints on its semantics. In the of a relation. Moreover, conditional functional dependenfollowing, we will simply use the line of code in the file cies (CFDs) [16] are functional dependencies that hold containing the JSON Schema declaration (after pretty on only a subset of the tuples. While in their full genprinting), where the scope of the object is first entered. erality, CFDs are a generalization of classical functional
We identify the labels of all properties reachable by a dependencies, we will focus on a very restricted subclass given path : that is related to association rules [21], and that can be defined quite compactly. = { | object { 1 : 1, . . . , : } is reachable by path }
Definition 4. If is a set of attributes, then a unary constant conditional functional dependency over (ucCFD) is an expression of the form
For each property label in where occurs as a basic value, we define a relational attribute .value [ = ] → [ = ] that captures the basic value . These properties are considered to be candidates for tags. where , are attributes in and , are constants
Further, for each property label in , we define from the domains of and respectively. A relation an attribute .type, capturing the subschema directly over satisfies [ = ] → [ = ] if for each derived from its value . pair of tuples , ∈ , ( ) = ( ) = implies
For each object reachable by path , we then insert ( ) = ( ) = . one tuple into this relation, choosing some unique object Example 5. The dependency below holds in Table 1 and identifier for each object. The attribute values are pop- reads as follows: ulated with the semantics described above; null values mark missing entries. [type.value = "Point"] → [coordinates.type = t1] Example 3. Table 1 shows the encoding for the JSON The left-hand-side, in brackets, declares a condition objects from Figure 1 in the array starting from line 3, that must be satisfied for the dependency to hold: We conreachable by the JSONPath /geometries[*]. By t1 sider all attributes where the value of attribute type.value and t2, we abbreviate the subschemas directly derived is the string “Point”. For all tuples where this condition is from the JSON values, requiring an array of numbers (t1) satisfied, the value of attribute coordinates.type must and an array of arrays of numbers (t2), namely be the subschema abbreviated as t1.
In our domain of application, namely JSON values, (t1) these dependencies express powerful constraints between property values and subschemas: In the example dependency above, it is implied that if the value of property type is the string constant “Point”, then the value of the sibling property coordinates must conform to the (t2) subschema t1.
In the remainder of this article, we exclusively focus on the discovery of such value-type constraints, where the attribute on the left-hand-side of a ucCFD is of the form “ .value” (the value of property , which we consider to be a candidate for a tag in a tagged union), and the attribute on the right-hand-side is of the form “ .type” (the subschema of the sibling property ).
Traditionally, tagged unions are declared by switching on the value of a single tag property. This is also the recommended practice in JSON Schema [9], and in agreement with what we observe in real-world data [10].
We are therefore confident that our restriction to unary dependencies is justified.
(quantitative comparison). Several of the examined
approaches also support the extraction of union types: [
XML was developed as a semi-structured data format their most generic type.
with implicit structural information and an optional ex- But neither Klettke et al. [
traction from JSON data [
Recent surveys of diferent schema extraction approaches were provided by [4] (qualitative comparison) and [5] Dependencies. For an overview of data dependencies, we refer to a comprehensive survey [36], and focus on functional, inclusion, and conditional functional dependencies in the following.
Functional dependencies and inclusion dependencies. Functional dependencies [37, 38, 39, 18] and inclusion dependencies on semi-structured data [40, 18] define semantic constraints on data to guarantee certain approach. In previous work on inferring inclusion dedata characteristics, to normalize data [41], and to ensure pendencies from JSON data [6], we suggested an eficient data quality. These constraints can also be applied in method that uses lattice characteristics to optimize the data cleaning. In [42], an overview over diferent meth- algorithm. To consider outliers, a threshold is introduced. ods and the semantic constraints, rules, or patterns to With it, it is possible to derive related inclusion dependetect errors in the data cleaning process is given. Schel- dencies which are violated by a small number of outliers. ter et al. [43] use declarative rules in unit tests to check A further relaxation of functional dependency discovthe data quality (defined with several metrics). Some ex- ery has been suggested in [49] for data lakes. Here, outamples are: completeness of datasets, range conditions, liers are not ignored, but properties that have diferent certain cardinalities and constraints on statistics. Both yet similar labels are combined. This method can be used approaches do not infer the semantic constraints from for data exploration and profiling of datasets with lower data but show how declarative rules can be leveraged data quality. during data preprocessing.
The discovery of valid uniqueness constraints, func- Conditional functional dependencies. Conditional tional dependencies and inclusion dependencies is a well- functional dependencies [16] were first introduced for studied field in relational databases [ 44, 45, 46, 47, 48] relational data, in the context of data cleaning. We apply and even more relevant in JSON data (or, more generally, conditional functional dependencies in a new context, NoSQL data) because often these semantic constraints the relational encoding of JSON objects. are not predefined in the NoSQL databases. They are im- In [50, 51], three algorithms for CFD mining are proplicitly available in the data but for data cleaning tasks, posed and evaluated: CTANE and FastCFD build upon this information is required in form of rules and con- existing algorithms for FD discovery, TANE and FastFD, straints. Hence, development of algorithms to derive respectively and are intended for general CFD discovexplicit semantic constraints from NoSQL data is of par- ery. The third algorithm is custom-designed for constant ticular importance. CFDs, as also targeted by us.
Methods for deriving semantic constraints from data In [
Arenas and Libkin define functional and inclusion de- 4. Approach pendencies for XML [17], as a basis for schema normalization. More recently, Mior [18] targets the mining of Our end-to-end approach is sketched in Figure 4. In our functional and inclusion dependencies from JSON data. upcoming walk-through of the architecture, we first focus Both formalisms do not allow to capture the conditional on the basic approach, as well as our heuristics against functional dependencies required in our context. overfitting and schema bloat. We then outline future
However, Mior compares the performance of depen- work extensions to robustly generalize our approach to dency discovery in a relational encoding of the JSON a larger family of tagged unions. data (termed “static unrolling”) with a dynamic unrolling technique, showing that the latter has superior runtime 4.1. Architecture performance. Mior focuses on the discovery of functional dependencies and inclusion dependencies. While his ap- Composability. We design our approach to be composproach does not consider the special case of conditional able with existing schema extraction algorithms: Given a functional dependencies, which is relevant in our context, collection of JSON values, we extract a JSON Schema deit is capable of deriving approximate dependencies, thus scription , using any third-party tool. Along the process being more robust w.r.t. vagueness in the input data. sketched along the bottom, we further derive the declara
Kruse et al. developed in [40] the scalable discovery of tion of tagged unions, denoted , a sequence of (possibly inclusion dependencies from data. Scalability of the ap- nested) JSON Schema if-then-else statements. proach is achieved by two reasons: the approach is only By the conjunction of the subschemas as concentrating on discovery of unary inclusion depen- {"allOf": [S, ]}, the composite schema requires the JSON values to satisfy both subschemas, imposing tagged unions on schema . This approach allows us to focus on the particular challenge of identifying tagged unions, while conveniently leveraging state-of-the-art schema extraction tools for describing the other aspects of the dencies (consisting of one attribute on the left-hand and on the right-hand side) and is developing a distributed approach. Combining both, a very eficient algorithm can be developed for analyzing large datasets. The heterogeneity of datasets has not been considered in this JSON Schema
1
JSON
Schema
Extraction, e.g. [
Schema
2
A
B
C
3
JSON Schema {allOf:[ , ]} [X=v1]→[Y=t1] [X=v2]→[Y=t2] [X=v3]→[Z=t3] schema. We leave it to future work to recursively merge implied subschema. Recall that with the dot-notation, we the composite schema, thereby improving the readability distinguish the value of JSON property (i.e., . value) as well as the locality of the interacting constraints. from the subschema of sibling property (i.e., .type) in our relational encoding of JSON objects.
Relational encoding. In a first step towards the dis- Example 7. From the relational encoding in Table 1, we covery of tagged unions, we parse all JSON values into a derive the following dependencies, again using the abbresingle parse tree (adding a virtual root node), and deter- viations t1 and t2 for the subschemas introduced earlier: mine the set of all labeled paths from the root to a JSON [type.value = "Point"] → [coordinates.type = t1] object. For each such path, we then derive the relational [type.value = "LineString"] → [coordinates.type = t2] encoding of all properties in the reachable objects. We have already introduced this data structure in Section 2, and resume the discussion of our running example.
Recall that in the context of our application, they are interpreted as follows. Given a JSON object reachable by the path /geometries[*], if the value of property Example 6. Consider the GeoJSON value in Figure 1. type is “Point”, the value of the sibling property coordiTable 1 shows the relational encoding of the four objects nates must conform to the subschema t1 (an array of reachable by the path /geometries[*]. The role of numbers). If the value of property type is “LineString”, the unique object identifier is to preserve cardinalities then the value of sibling property coordinates must in repeating attribute values, allowing us to later filter conform to the subschema t2 (an array of points). dependencies based on their support in the input.
In the discovery of these dependencies, we leverage
The running example has been designed to be simple, state-of-the-art algorithms [
Dependency discovery. Based on the relational en- In the following, we outline the general idea. Inferring coding, we discover conditional functional dependencies. conditional functional dependencies from PLIs can be We restrict ourselves to unary constant conditional de- achieved by finding inclusions between them: given PLIs pendencies in our relational encoding, of the form A.value = {{1, 2, 3}, {4, 5, 6}} of attribute . value and B.type = {{1, 2, 3, 4}, {5}, {6}} of attribute . type, we [. value = ] → [. type = ] receive the inclusion {1, 2, 3} ⊂ {1, 2, 3, 4}, allowing us to infer that the values of JSON property A corresponding where the left-hand-side denotes the value of the can- to rows 1, 2 and 3 determine the subschemas of the sibling didate tag, and the right-hand-side a property with an property B. implied subschema. Above, and are distinct prop- More sophisticated algorithms developed for the diserty labels, is a basic-value constant, and denotes the covery of conditional functional dependencies (CFDs), such as CFDMiner, CTANE and FastCFD [50], could be Minimum Threshold min. Especially in large datadeployed just as well. As our current restrictions, most sets, it is to be expected that dependencies are inferred notably the one to unary dependencies, obfuscate many that have no real semantics, despite us ignoring attributes of the challenges in FD and CFD discovery, we opted for with unique values. Our implementation has a configour simpler approach. urable minimum threshold: Dependencies with insuficient support in the input are then ignored during the Pruning candidate dependencies. To avoid over- generation of if-then-else statements. iftting in the derived schemas, we heuristically prune By allowing to configure this threshold, either as an candidate dependencies, as described in the upcoming absolute or relative value, the number of discovered deSection 4.2. pendencies can be influenced. Our experiments evaluate this efect.
Finalization. In a final step, the conditional functional dependencies are transformed into nested if-then-else 4.3. Future Generalizations of the statements in JSON Schema . This step is merely tech- Approach nical, as is the construction of the composite schema. 4.2. Heuristics In our approach, an inherent challenge is dealing with high numbers of discovered dependencies, which may lead to overfitting the derived schema w.r.t. the input data.
We next distinguish default heuristics and heuristics that are configurable by an expert user.
The following heuristics are always applied, as they prevent schema bloat due to overfitting.
In GeoJSON data, which served as our motivation for the discovery of tagged unions, the geometry objects are highly regular. When inspecting further instances of tagged unions in real-world data, we encounter variations that require us to generalize our approach. For illustration, we again resort to an example. 1 [ { " condition ": " minecraft : time_check ", 2 " period ": 24000 , 3 " value ": { "min ": 0.0 } } ]
(a) The value of property min (line 3) is numeric. 1 [ { " condition ": " minecraft : weather_check ", 2 " raining ": false , Single-valued attributes. In discovering dependen- 34 { "" ctohnudnidteiroinng":":" fmailnseecra}f,t : time_check ", cies, we ignore all attributes from the relational encoding 56 "" vpaelruieod":":{24000 , with a single-valued domain. In Table 1, this concerns 7 "min ": { the attribute type.type. 89 " t"arngaemte "":: {"% StartSunburn ", 10 " type ": " minecraft : fixed " }, Unique attributes. Unique property values are rec- 1112 "" tsycpoere":":""miDnaeyctirmaeft":, score " } } } ] ognized as conditional functional dependencies, and ultimately, cause overfitting and schema bloat. In dependency discovery, we therefore ignore all attributes where the domain consists of unique values (such as the object identifier .id, which does not appear in the input data, and need not be considered in dependency discovery).
Union rule. We apply the union rule to the discovered Example 8. We consider JSON data used in the Minecraft dependencies, so that one tag may imply the subschemas game, as shown in Figure 5. The property condition for several sibling properties. This improves schema functions as a tag, and distinguishes notions such as “time succinctness. checks” and “weather checks”, among others. Depending on the tag value, diferent sibling properties exist: Given 4.2.2. Configurable Heuristics that the tag value is a “weather check”, sibling properties labeled raining and thundering exist. Given that the The following heuristics is reasonable in many cases. As tag value is a “time check”, sibling properties labeled it is not universally applicable, we make it configurable. period and value exist.
To extend our approach to such more general forms of tagged unions, we need to be able to detect conditional dependencies between the value of a candidate tag, and the existence of a sibling property (which we term as a fully automated reproduction package, are availvalue-label constraints, to distinguish from the value- able online [12]. Additionally, in the PDF version of this type constraints that we already handle). Here, a specific article, clickable links in Table 2 allow our readers to dichallenge is to handle optional sibling properties, which rectly inspect the input datasets, as well as the extracted are not always present.
Example 9. Resuming the previous example of a Minecraft “time check”, the subschema for property value is an object with a property min. The subschema of property min, however, may vary. In the top example, it is a numeric value. In the bottom example, it is a nested object.
Our approach outlined so far cannot detect this condi- our results. tional functional dependency, because the subschemas of the sibling property difer.
To detect value-type dependencies where the types on ognized subschema. In our current prototype implemen- ficiently large document size and (2) that at least two tation, we introduce attributes min.type1, . . . , min.type (e.g., for a fixed limit
= 6), where we describe the subschema with a varying degree of detail. For instance, from a shallow min.type1= {"type":
"object} to a very fine-grained description that fully captures all nested objects. In pruning candidate dependencies, we only keep the most detailed subschema for which a CFD still holds. This allows us to detect a common subschema in many practical cases.
We next describe our experiments using real-world geospatial datasets encoded in JSON. For notational simplicity, we will write “CFDs” when we refer to the subfamily of unary constant conditional functional dependencies, as introduced in Section 2. 5.1. Setup
Our prototype is implemented in Python, using the library anytree for managing parse trees. For schema validation, we use the Python library jsonschema (clickable links in the PDF).
For the “third-party” schema extraction tool, we
employ a tool that we have built in earlier work [
successfully built a variant of our architecture based on
the schema extraction tool by Frozza et al. [
Our research artifacts (code, data, extracted schemas), as well
open data servers, as well as by performing a search over all open-source licensed repositories on GitHub using Google BigQuery. Our selection criteria were (1) a sufdiferent types of geometries co-occur, so that we may be able to infer tagged unions.
• Map Germany is a TopoJSON dataset, describing a map of Germany and surrounding areas, including cities, urban areas, and rivers. This dataset uses geometry types Point, LineString,
• Map EU is a TopoJSON dataset. Its structure is comparable to Map Germany but describes countries in the EU in detail and contains the borders of some adjacent countries. • WorldGen Berlin is a GeoJSON dataset from Open
• US House Members lists members of the US House of representatives, including their place of birth, hometown and congressional district, encoded in • Wildlife Sites contains wildlife sites in West Yorkshire, described either as a GeoJSON Polygon or
The datasets encode GeoJSON or the related TopoJSON format (distinguished as formats “T” and “G” in the table).
We list the size of each dataset in lines of code after prettyprinting (column | |
).
In lieu of a ground truth describing the number of conditional functional dependencies in the data that is not GeoJSON-encoded, we report in the table the number of detectable CFDs in the GeoJSON-parts only (
).
We manually determine this value for each dataset, inspecting all distinct types of GeoJSON objects (e.g., Point, LineString, Polygon) on each diferent path. We ignore all paths where the value of the GeoJSON type does not vary. While these can be detected as CFDs from the data, they are not meaningful for recognizing tagged unions, and should be modeled, for instance, simply as constant values instead. 6 6 2 2 50% 35% 15% 50% 35% 15% 50% 35% 15% 50% 35% 15% 50% 35% 15% |T| (LoC) 126 158 190 95 95 127 150 182 278 54 54 54 38 38 92
Ratio
(TopoJSON or GeoJSON) and report its size (| |) in lines of code (LoC), the size of the conventionally extracted schema (in LoC) and the number of theoretically detectable Geo-/TopoJSON CFDs ( ). For diferent threshold settings min, we produce a subschema encoding the tagged unions. “Ratio ” reports the share of w.r.t. the size of the composite schema.
Further, the number of CFDs initially discovered (w/o heuristics), after applying threshold min (see Section 4.2.2), and after applying the remaining default heuristics (see Section 4.2.1) are reported. The last column reports the result of checking whether dataset
is valid w.r.t. the extracted composite schema (a checkmark symbol “✓” denotes a successful check). The checkmarks are clickable links, embedded in the PDF, to the composite schema.
Format |D| (LoC) |S| (LoC)
DetGeo min
CFDs w/o Heuristics
CFDs w/ min
CFDs w/ min
and Heuristics 5.2. Experimental Design Workflow. For each data collection, we extract com- schemas successfully validate against Draft-07, and furposite schemas choosing three settings for the minimum threshold min: an aggressive setting of 50%, requiring a conditional functional dependency to occur in at least ther, that all JSON datasets validate against the composite schemas.
Decreasing the threshold min leads to more condihalf of the tuples in the relational encoding of all objects tional functional dependencies being discovered. The reachable by a given path, and more lenient settings with share of the subschema encoding tagged unions com35% and 15%, respectively.
For each threshold setting, we generate schemas (from the third-party tool) and (encoding the tagged unions), as well as the composite schema. pared to the entire composite schema ranges between 10% and up to approx. 38%. While the 38% share might appear to be large, the composite schema has less than 250 lines in total, compared to 800K lines of JSON input.
Each composite schema is validated against the spec- Thus, this dataset is highly regular in its structure, and ification of JSON Schema
Draft-07, confirming that the the extracted schema comparatively compact. composite schema conforms. The input datasets are furFor the bottom three datasets, we detect conditional ther validated against the extracted composite schema, functional dependencies in the hundreds, even more than checking for any logical errors in schema extraction. 5.3. Results printing), the number of conditional functional depen- target DetGeo). Note that there are only six distinct geone thousand in the case of the WorldGen Berlin data.
However, applying the threshold and the other heuristics drastically reduces the dependencies towards the number of tagged unions that we expect to find (c.f. the ometries in GeoJSON which may, however, occur on diferent paths, leading to more than six if-then-else statements in the GeoJSON part.
listed in Example 2), as well as synthetic data, and data After applying heuristics and a threshold of 15%, we not encoding any tagged unions, are required. only miss two detectable CFDs in Map EU and three in We do not focus on the performance of our unoptiWorldGen Berlin. Missed CFDs can be attributed to the mized prototype implementation, as the algorithm is threshold being too coarse.
Manually inspecting the final dependencies, we find
only executed once for each dataset. Of course,
scalability to larger inputs is an issue to be addressed in
one unexpected dependency for Wildlife Sites with a
future work, as CFD discovery in general is an expensive
threshold of 15%. This is the only false positive depen- problem: Already in addressing the discovery of
funcdency across all datasets. It results in a tagged union
tional dependencies in their full generality, algorithms
being declared for a specific date, which is not
semanhave exponential runtime complexity [
. performance depends heavily on the input, with some Thus, we have a single case of overfitting for the datasets algorithms scaling better with size of the dataset (i.e., the analyzed. Overall, we observe very high precision in recnumber of tuples) thus being suitable for large datasets, ognizing the GeoJSON/TopoJSON dependencies resident while others perform better with higher arity. For conin the data.
stant CFDs, Li et al. [
We do not focus on runtime evaluation, as our im- improvements by applying custom rules for pruning the plementation is prototypical and unoptimized. Yet to search space. provide a general perspective, we share our observation With strong restrictions to the problem space, such as that runtimes vary greatly between datasets, ranging our restriction to unary constant CFDs in our case, we can from roughly one second to approximately one minute. expect reasonable runtime performance on real-world This is a waiting time which we deem acceptable for a inputs (which are often reasonably well-behaved). non-interactive, irregular task.
In our experiments, we observed a considerable impact Since our approach is main-memory based, memory of our heuristics and threshold on runtime, reducing the is a physical limitation to the inputs that we can proprocessing time for all datasets by up to two orders of cess. For the datasets considered here, 16GB of RAM are magnitude. This is promising for further optimizations. suficient to run our experiments. 5.4. Discussion The comparison between the number of dependencies found with diferent heuristics shows the efectiveness lar, this concerns the configuration knob represented by minimum threshold. with 50% obviously too rigid, but 15% delivering meaningful results. In future work, we plan to investigate how to auto-adjust the threshold, based on statistical distributions obtained by profiling the input.
An obvious threat to the generalizability of our results — however promising they are — is that the GeoJSON datasets are highly regular in their structure. In the GeoJSON-part, they contain only a small number of detectable dependencies, between two and eleven. Therefore, we refrain from computing the metrics precision and recall, as they are easily distorted when working with small numbers. However, the manual inspection of the derived dependencies, and the comparison against the target DetGeo, shows that our approach is indeed successful for the input datasets chosen.
To counter the threat of generalizability, further experiments over diferent real-world datasets (e.g., the datasets
In this article, we proposed a method to infer conditional functional dependencies from JSON data. We use the unions in JSON schema extraction.
This allows us to capture value-based constraints. In with users, regarding the users’ preferences in schemas over nested data. Their interviews reveal that valuebased conditions have a greater influence on the diferentiation of schema variants than structural constraints, and are therefore preferred.
In future work, our approach can be extended for the extraction of further variants of dependencies, for instance, traditional conditional functional dependencies that capture implications between atomic property values, or dependencies where the value of the tag property implies the existence of a specific sibling property, as discussed in greater detail in Section 4.3. This allows to recognize a larger family of tagged unions.
Our prototype implementation is currently main-memory based, which limits the size of inputs that we can handle. Making our implementation scale to larger inputs is one of the immediate next steps. Here, we may build upon first results by Mior [ 18], who shows that discoverof these heuristics in pruning dependencies. In particu- identified dependencies as the basis for declaring tagged
Our approach to setting this threshold is rather coarse, fact, in [35] Gallinucci et al. report on expert interviews