In document stores, schema is a soft concept and the documents in a collection can have di erent schemata; this gives designers and implementers augmented exibility but requires an extra e ort to understand the rules that drove the use of alternative schemata when heterogeneous documents are to be analyzed or integrated. In this paper we outline a technique, called schema pro ling, to explain the schema variants within a collection in document stores by capturing the hidden rules explaining the use of these variants; we express these rules in the form of a decision tree, called schema pro le, whose main feature is the coexistence of value-based and schema-based conditions. Consistently with the requirements we elicited from real users, we aim at creating explicative, precise, and concise schema pro les; to quantitatively assess these qualities we introduce a novel measure of entropy.
Recent years have witnessed an erosion of the relational DBMS predominance to the bene t of DBMSs based on alternative representation models (e.g., documentoriented and graph-based) which adopt a schemaless representation for data. Schemaless databases are preferred to relational ones for storing heterogeneous data with variable schemata and structural forms; typical schema variants within a collection consist in missing or additional attributes, in di erent names or types for an attribute, and in di erent structures for instances. The absence of a unique schema grants exibility to operational applications but adds complexity to analytical applications, in which a single analysis often involves large sets of data with di erent schemata. Dealing with this complexity requires a notable e ort to understand the rules that drove the use of alternative schemata, plus an integration activity to identify a common schema to be adopted for analysis |which is quite hard when no documentation is available.
In this paper we outline a technique to explain the schema variants within a collection in document stores by capturing the hidden rules explaining the use of these variants. We call this activity schema pro ling. Schema pro ling can be used for instance when trying to decode the behavior of an undocumented application that manages a document-base, or to support analytical applications ? This work was partly supported by the EU-funded project TOREADOR (contract n. H2020-688797).
CardioOn CardioOn=true CardioOn=false
Ac&vityType Ac&vityType=“Run” “Bike” v4 s1
Ac&vityType=“Walk”
User ∃
∃ d4 BPM v3 s3 {} " "DAuc&rav&itoynT"yp :e 1"3 :0 " B ike", User.Age ∃ ∃ User.Age≤60 User.Age>60 v1 s2 s3 v2 v5 s4 v6 s5 {} """ "CBDAaPucrM&rdavi"&iot o:Oy 8dnTn0"y1"p : :e 1 t"0ru :, e"R, un{} " ,""" " CBDAaPucrM&rdavi"&iot o:Oy nT n"y"p : :de 2 t"20ru :, e"R, un{}" , " Ac&vityTypde"3 : "Run" {} {" " } U A " "scAUe&gsrvee"i"rtd :Iy :D 5T 4"y2p : e2"3, : "W{} a {" " }l U Ak " " "scAN,e&ga rve"mi"t :ye : T " 6y :1p "d eJ6a" c :k ""W, alk", v7 s1
d7
{ "Ac&vityType" : "Walk",
"Dura&on" : 60
}
that query a document store following either a schema-on-write or
schema-onread approach [
A schema pro le should describe the rules for assigning a document to a schema based on the document features; hence, modeling a schema pro le as a classi er is a natural choice, which also allows the existing literature on classication to be reused. More speci cally, since users need a comprehensible and compact representation of schema pro les, among the di erent types of classi ers we focus on decision trees.
Straightly reusing traditional decision trees for schema pro ling would mean classifying documents based on the values of their attributes only. However, this would often lead to trees where a single rule explains di erent schemata, which would yield an imprecise information. To address this issues, in our approach documents are also classi ed using schema-based conditions related to the presence or absence of attributes. Consider for example Figure 1, showing a portion of a schema pro le built in the domain of physical tness to describe a collection of documents generated by training machines. Each internal node in the tree is associated with a document attribute a and can express either a value-based condition (white box; each outgoing arc is related to one or more values of a, e.g., User.Age < 60) or a schema-based condition (grey box; the two outgoing arcs represent the presence or absence of a in the document, e.g., 9BPM). Each path in the tree models a rule; it leads to a leaf (represented as a circle) that corresponds to a schema found for the documents that meet all the conditions expressed along that path (document examples are shown in dashed boxes). So, for instance, schema s1 is used in all the documents for which either ActivityType = \Bike", or ActivityType = \Walk" and eld User is not present.
Another drawback of traditional decision trees is that they often give several rules for the same class. While this may be correct for some speci c collections (e.g., schema s1 in Figure 1 appears in two leaves, i.e., it is explained by two di erent rules), in general we wish to keep the number of rules to a minimum aimed at giving users a more concise picture of schema usage. This is achieved in our approach by introducing a novel measure called schema entropy that, together with the classical entropy measure, enables a better assessment of the quality of a schema pro le. 2
The central concept of a document store is the notion of a document. Following the most widely adopted format, a document is a JSON object. An object is formed by a set of name/value pairs called elements. A value can be either a primitive value (i.e, a number, a string, or a Boolean), an array of values, an object, or null. A collection D is a set of documents. Arrays have no constraint on their size and on the type of their values, i.e., an array can simultaneously contain numbers, strings, other arrays, as well as objects with di erent structures. Figure 2.a shows a document that represents a training session containing an array of objects with di erent schemata (element Comments).
The JSON schema initiative provides the speci cations to de ne the schema of a document; however, as shown in Figure 2.b, the resulting schemata provide a complex representation of arrays and are quite verbose. Indeed, the schema of an array is de ned as the ordered list of the schemata of its values, so two arrays share the same schema only if they contain the same number of values and these values share the same schemata in the same order. This schema-matching criterion would add unnecessary burden to our approach |also considering that the type variability of array elements is less relevant than that of the other attributes. So we adopt a more concise representation for the schema of a document, called reduced schema, which does not enter into the content of arrays, but simply denotes the presence of an array structure.
schema (brie y, r-schema) of d, denoted rs(d), is a set of attributes, each corresponding to one element in d. Attribute a 2 rs(d) is identi ed by a pathname, path(a), and by a type, type(a) 2 fprimitive; object; arrayg. While path(a) is a string in dot notation reproducing the path of the element corresponding to a in d, type(a) is the type of that element (type primitive generalizes numbers, strings, Booleans, and nulls).
Note that, although r-schemata are de ned as sets of attributes, their pathnames code the document structure (short of the internal structure of arrays). Example 1. Figure 2 shows a sample document, its JSON schema (as per the speci cations of the JSON schema initiative), and its r-schema. Note how, in the r-schema, the complexity and heterogeneity of array Comments is hidden in attribute Details.Comments with generic type array.
To put together the relevant information coded by di erent r-schemata, for the documents within a collection D we de ne a global r-schema that includes all the distinct attributes that appear in the r-schemata of the documents in D:
with S(D) the set of distinct r-schemata of the documents in D (where two attributes in the r-schemata of two documents are considered equal if they have the same pathname and the same type). The r-schema of D is de ned as rs(D) = Sd2D rs(d). Given s 2 S(D), we denote with jDjs the number of documents in D with r-schema s.
Based on the concepts introduced above, we can now de ne schema pro les. De nition 3 (Schema Pro le). A schema pro le for collection D is a directed tree T where each internal node corresponds to some attribute a 2 rs(D) and expresses a condition that can be either value-based or schema-based: (i) a node expressing a schema-based condition has exactly two outgoing arcs, labelled as 9 and 6 9 respectively; (ii) a node expressing a value-based condition has two or more outgoing arcs, each labelled with a condition over the domain of a. Value-based conditions can only be expressed on attributes of type primitive. Given node v, we denote with Dv D the set of documents that meet all the conditions expressed by the nodes in the path from the root to v, with S(Dv) S(D) the set of distinct r-schemata of the documents in Dv, and with jDvjs the number of documents with r-schema s 2 S(Dv) belonging to Dv.
Intuitively, each path in a schema pro le models a rule that includes a set of conditions for selecting one or more r-schemata. We also remark that De nition 3 can accommodate both binary and n-ary trees.
Example 2. Figure 1 shows an n-ary schema pro le with two schema-based conditions (User and BPM) and three value-based conditions (ActivityType, CardioOn, and User.Age). In this case, it is D = fd1; : : : ; d7g and S(D) = fs1; : : : ; s5g. The schema pro le has leaves v1; : : : ; v7, with Dv1 = fd1; d2g. Note that document d3 belongs to both v2 and v3, since attribute CardioOn is missing.
The rst stage of our work has been devoted to elicit user requirements for schema pro ling with reference in two application domains: that of a company selling tness equipment, whose documents contain the registration of workout sessions, and that of a software development company, whose documents contain the log of the errors generated by the deployed applications. The requirements we elicited can be summarized as follows: (i) a schema pro le should be explicative, i.e., it should give priority to value-based conditions (which explain the di erence between two r-schemata in terms of the values taken by an attribute) over schema-based ones (which merely acknowledge this di erence); (ii) a schema prole should be precise, i.e., it should accurately characterize each single r-schema by avoiding mixing documents with di erent r-schemata in the same leaf of the tree; (iii) a schema pro le should be concise, i.e., it should provide a small set of rules (a single rule for each r-schema).
Now we can informally state our nal goal as that of nding a schema pro le
that achieves a trade-o between precision, conciseness, and explicativeness. The
problem can be modeled as a classi cation one where the documents, properly
extended with schema information, are the objects to be classi ed according to
the schema labels. Since schema pro les are decision trees, to solve this problem
we have extended the well-known C4.5 algorithm [
We consider a schema pro le to be explicative if it prefers value-based conditions over schema-based ones, because the latter acknowledge that there is a di erence between two r-schemata but do not really explain its reason. Indeed, a value-based condition always relates two di erent attributes (for instance, with reference to Figure 1, attributes User.Age and UserID); this is because a condition on the values of an attribute a does not partition the documents based on the presence/absence of a. Conversely, a schema-based condition on a always partitions the documents based on the presence/absence of a so, in a sense, it merely explains itself.
So, to evaluate explicativeness we use the number of schema-based conditions in the schema pro le T : the lower this number, the more explicative T . 3.2
A distinguishing feature of the classi cation approaches based on decision trees is
the function they adopt to quantify the \purity" of the leaves where observations
are classi ed, where a leaf is said to be pure if all its observations share the same
class. The most common function used to this end is entropy [
T0 s1, s2, s3, s4
B
B=“b1” B=“b2” s1, s2, s3 TBA
B B=“b1” B=“b2” s4 s4 De nition 4 (Entropy). Let S(D) be the set of distinct r-schemata of the documents in collection D, and T be a schema pro le for D with leaves v1; : : : ; vm. The entropy of T is entropy(T ) = m X jDvj j entropy(vj ) j=1 jDj where jDvj j is the probability of leaf vj , entropy(vj ) = jDj P
jDvj js log jDvj js s2S(Dv) jDvj j jDvj j is the entropy of leaf vj , and jDvj js is the probability of r-schema s within leaf jDvj j vj . Leaf vj is said to be pure if entropy(vj ) = 0.
Entropy is strictly related to precision: within a schema pro le with null entropy, all the documents included in each leaf share the same r-schema, thus the schema pro le has maximum precision.
Example 3. Let D be a collection with 100 documents, 4 r-schemata s1; : : : ; s4, and two attributes, A and B. The values of the attributes for the di erent rschemata are listed in Figure 3 (symbol \{" means \any value"), together with ve possible schema pro les. A degenerate schema pro le T0 made of a single root node v0 has entropy entropy(T0) = entropy(v0) = 1:85 (because Dv0 D). Schema pro les TA and TB have entropy(TA) = 0:46 and entropy(TB) = 1:38, respectively. Both schema pro les TAB and TBA have null entropy because no leaf includes multiple r-schemata. 3.3
Entropy is focused on node purity, hence its minimization often leads to split observations of the same class among several leaves. While this is a secondary problem in generic classi cation problems, where the precision of the resulting model is more important than its readability, it becomes critical in schema proling since it con icts with the conciseness requirement. Indeed, in our context, each r-schema might end up for being explained by a wide set of rules, thus precluding users from getting a concise picture of schema usage. For instance, with reference to Example 3, though both schema pro les TAB and TBA have null entropy, the latter is clearly the one that best represents the collection, with each r-schema being reached by a single path in the tree.
To evaluate the conciseness of schema pro les, we propose a measure called schema entropy. Our requirement is to reduce the number of rules provided by maximizing the cohesion of the documents that share the same r-schema |a maximally concise schema pro le is one where there is a single rule for each r-schema. So we invert the original de nition of entropy to relate it to the purity of the r-schemata instead of the purity of the leaves: in terms of entropy, a leaf is pure if it contains only documents with the same r-schema; in terms of schema entropy, an r-schema is pure if all its documents are in the same leaf. The schema entropy of a degenerate schema pro le where all the documents are included into a single node (the root) is 0; when documents are split into di erent leaves, the schema entropy can never decrease.
sEntropy(T ) =
sEntropy(s) X
jDjs s2S(D) jDj s 2 S(D). where sEntropy(s) = Pjm=1 j DjDvjjsjs log jDvj js is the schema entropy of r-schema jDjs Example 4. With reference to Example 3, it is sEntropy(T0) = sEntropy(TB) = sEntropy(TBA) = 0 and sEntropy(TA) = sEntropy(TAB) = 0:16. Therefore, if both entropy and schema entropy are considered, TBA is the best schema pro le. 4
Early work on schema discovery focused on describing semi-structured data
retrieved from web pages based on the Object Exchange Model (e.g., [
In this paper we have outlined an approach to schema pro ling for document stores. The idea is to capture the rules that explain the use of di erent schemata within a collection through a decision tree whose nodes express either value-based or schema-based conditions. Though our approach has some points in common with the above mentioned ones, its goal is completely di erent. The ultimate goal of the previous work is to provide a way to describe the intensional aspects of the documents, while ours is to explain the schema variants. Besides, no other approach considers the extensional point of view to describe schema variants. Finally, while all previous approaches produce in output some form of skeleton schema, we create a schema pro le that classi es schema variants.
We made some experimental tests using both synthetic and real-world collections, with numbers of documents ranging from about 10000 to more than 5 millions, and it turned out that our approach achieves a good trade-o among precision, conciseness, and expressiveness. Speci cally, to assess its accuracy we compared the schema pro les it delivers with a baseline (for synthetic collections the baseline is the set of rules used to generate the collection itself, while for real-world collections it has been provided by the users). For comparisons we adopt the weighted tree edit-distance (i.e., the length of the cheapest sequence of node-edit operations that transforms one tree into the other, weighted on the tree depth), which ranges between 0 and 1.17 for synthetic collections and between 0 and 1.33 for real-world collections. Finally, in terms of e ciency, we found that the total time to build a schema pro le ranges from a few seconds to about 3 minutes, depending on the number of documents and on their number of attributes (on a 64-bits Intel Core i7 quad-core 3.4GHz).