Kenza Kellou-Menouer
email: kenza.kellou.menouer@gmail.com

Zoubida Kedad
email: zoubida.kedad@uvsq.fr

SchemaDecrypt++: Parallel On-line Versioned Schema Inference for Large Semantic Web Data Sources

Keywords: RDF, Property co-occurrence, Source restrictions, Structural pattern discovery

A growing number of linked data sources are published on the Web. They form a single huge data space referred to as the Web of data. These data sources contain both the data and the schema describing them, but the data is not constrained by this schema. Indeed, two instances of the same class may be described by different properties. This flexibility for describing the data eases their evolution, but it comes at the cost of losing the description of the data, which can be useful in many contexts. The different structures of a class represent its versions. These versions provide useful information on property cooccurrence for a class, but their discovery can be very costly, and even impossible because the data sources are remote. Furthermore, they may have some access limitations, either on the query execution time, or on the number of queries, or on the size of the results.

In this paper, we present SchemaDecrypt + +, a novel approach for the parallel discovery of a versioned schema for a remote data source. Our approach discovers the versions on-line, without uploading or browsing the data source. Broadly speaking, SchemaDecrypt + + allows to discover co-occurrences between properties from any set of properties: (i) specified by the user; (ii) describing the instances of a class or (iii) specified in the schema. SchemaDecrypt + + relies on our previous approach for schema discovery, SchemaDecrypt; in the present work we introduce a new strategy of parallelization of class version exploration, based on the discovery of a set of occurrence rules between the properties of the class. This strategy enables to overcome the source querying restrictions, the combinatorial explosion of the candidate versions and it improves the performances. We present some experimental evaluations on DBpedia to demonstrate the effectiveness of our approach.

Introduction

Modern applications dealing with huge collections of data have evidenced the limitations of relational database management systems, leading both researchers and companies to explore non-traditional ways of storing data. This has motivated the development of a continuously growing number of new data models, with the purpose of tackling the requirements of such applications. Among these requirements, a very flexible and schema-less data model, the ability to represent complex data and achieve scalability.

Users and applications are also provided with a huge amount of data on the Web. This Web of data is enabled thanks to the standard languages provided by the W3C for describing data, such as RDF1 (S2 )/OWL 3 . Data is made available through query endpoints, where users and applications can issue their queries expressed in dedicated query languages such as SPARQL 4 .

Languages used to describe data in the semantic Web provide a high flexibility due to the lack of an explicit or strict schema for the data. RDF(S)/OWL data sources can store data with different structures for the same class, and data evolution is eased due to the lack of restrictions imposed on the data structure. However, this lack of structure makes the interrogation of these data sources more difficult.

The different structures of the instances of a class represent the different versions of this class. Class versions could be viewed as a summary of the cooccurrence between the properties, which is useful for many purposes such as formulating queries, providing a description of the data, identifying the relevant sources for a specific usage, decomposing queries over distributed data sources and optimizing their execution plan.

Our goal is to infer a versioned schema for a remote RDF data source, i.e. versions of the classes defined in the schema. In our previous work [START_REF] Kellou-Menouer | On-line versioned schema inference for large semantic web data sources[END_REF], we have proposed SchemaDecrypt an on-line approach which discovers the versions of each class in the schema, along with the number of occurrences for each one. Our approach does not require to upload or browse the data to find the class versions, it is therefore suitable for large evolving data sources. In this paper, we propose SchemaDecrypt + +, an extension of our approach enabling the parallel exploration of the candidate versions of a class. We have conducted some experiments with both SchemaDecrypt and SchemaDecrypt + + on DBpedia which is a real remote data source. The results show that significant performance improvement is achieved by our extended approach.

The remainder of this paper is organized as follows. We motivate our approach for discovering a versioned schema in section 2, then we present the baseline approach and its challenges in section 3. In section 4, we present SchemaDecrypt, our approach for discovering class versions. We propose a parallel exploration of class versions with SchemaDecrypt + + in section 5. We discuss the cost of our approach in section 6. In section 7, we present our evaluation methodology and the results achieved on a real remote data source. We then discuss some related works in section 8 and finally, a conclusion is provided in section 9.

Motivation

A data source described in RDF(S)/OWL is defined as a set of triples D ⊆ (R ∪ B) × Y × (R ∪ B ∪ L), where the sets R, B, Y and L represent resources, blank nodes, properties and literals respectively. Such data sources are subject to constant evolution and the nature of the languages used to describe them do not impose any constraint on the structure of the data: instances of the same class may have different properties. Several descriptions might be found in each source. We assume that the search is performed using a desktop computer with limited computing power and that there is a limited time to answer the user's query. In the context of a remote data source on the Web, the user can not browse the data; his only access is through queries to the Web server that manages the data source. We represent graphically the schema of a data source by a set of classes and links between them. Each class represents a group of instances with the same type in the data source. A link represents a property, either between a class and a literal, or between two classes. A link p from a class c i and with no target class indicates that an instance of the class c i may have the property p for which the value is a literal. A link p from a class c i to another class c j indicates that an instance of the class c i may have the property p for which the value is an instance of the class c j . It represents a property for which the domain is c i and the range is c j , declared in the data source by the two triples (p rdf s:domain c i ) and (p rdf s:range c j ). There is no information in the data source about the co-occurrence between the properties of a class.

We propose to describe the content of a data source by a versioned schema. Figure 2 shows a partial example of versioned schema for the source S1. The class Museum has three versions in this data source. Class versions show which properties occur together in the data source, and ideally the number of instances for which this co-occurrence holds. The description of such a versioned schema could be useful for a user in various data processing and data management tasks, such as:

• Identifying the relevant sources. A data source may contain a class described by properties which are of interest to a user. However, there is no guarantee that these properties occur together in the instances of the class. Class versions provide information about property co-occurrence, which is useful to determine whether the relevant properties for a user are simultaneously present in some instances in a data source.

For example, assume that the user of Figure 1 would like to know the architects and the number of floors of museums by architectural style. To find this information, he has to query the three sources. However, the versions in Figure 2 show that in source S1, the properties -------------→ architecturalStyle and --------→ f loorCount never occur together to describe museum instances. Therefore, this source is not relevant for the user's needs and it is useless to query it.

• Formulating queries. A description of the different structures of a class and the number of occurrences for each one could help the user to formulate the most appropriate query in order to obtain the needed information.

Depending on the versions of the class, it would sometimes be necessary to write a query for each version containing the required information in order to obtain the most complete answer.

For example, assume that the user is looking for information on the location of museums. Versions could show that this information is sometimes described by v 1 = { ----------→ streetN umber, --------→ streetN ame, -----→ zipCode} with 95 occurrences and sometimes by v 2 = { -----→ address} with 5 occurrences. To have the most complete answer, it is better to write a query for each version that describes the same information. However, each query will respond in a different form. If the user wants to have a homogeneous result, he could decide to query the source only with v 1 which represents the vast majority of answers according to the number of occurrences of v 1 and v 2 .

• Decomposing and optimizing a distributed query. When a query is issued over several data sources, query decomposition is a key problem, as well as finding optimal execution plans as addressed in [START_REF] Quilitz | Querying distributed RDF data sources with SPARQL[END_REF]. The set of class versions for each source could help in decomposing the query and sending the sub-queries to the relevant sources, and the number of occurrences of the versions could be useful in order to optimize the execution plans by ordering the sub-queries according to the selectivity of their criteria.

For example, assume that the data is distributed across three data sources D1, D2 and D3. Properties of an instance could be distributed over the different sources. To answer a query, we have to collect the data from D1, D2, D3 and we have to combine them. Let us consider a user interested in the following query:

-"Select * where {?x rdf:type Museum . ?x architect ?y . ?x floorCount ?z} "

SchemaDecrypt++ could be applied to process each source on the properties ------→ architect and --------→ f loorCount for the class Museum. Let the discovered versions be the followings:

-D1: v 1 = { ------→ architect, --------→ f loorCount} with 20 occurrences ; v 2 = { ------→ architect} with 30 occurrences ; -D2: v 1 = {
------→ architect} with 10 occurrences ; v 2 = { --------→ f loorCount} with 15 occurrences; -D3: the properties do not exist in D3, therefore no version is found.

The data, described by the versions containing all the properties of the query, should first be found as for the data described by the version v 1 of D1. Then, the possible combinations between the versions of the different sources should be detected to have a complete answer as for the version v 2 of D1 which can be combined with the version v 2 of D2. To reduce the size of the intermediate results as early as possible, the data described by version v 2 of D2 which counts less occurrences should be extracted first, then the matching data in version v 2 of D1 should be extracted.

• Improving data description. The information about a schema of a data source is provided to describe its content. However, for an RDF(S)/OWL data source, this information is not accurate [START_REF] Kellou-Menouer | Evaluating the gap between an RDF dataset and its schema[END_REF], because the data do not have to follow the initial schema. Indeed, instances of the same class may have different structures, and in this case, a schema with the different versions of the classes is more accurate to describe the data than a schema with a general description for each class.

In the next section, we present the baseline approach for discovering the versions of a class, as well as the challenges we are faced with when tackling this problem.

Baseline Approach and Challenges

To find the versioned schema of a data source we have to find the different versions of each class. In this section, we first discuss the set of input properties according to the user's needs. We then define the class versions and finally, we present the version discovery process as a combinatorial problem which will highlight the main challenges of discovering a versioned schema. Finally, we present the restrictions imposed by the data sources in our setting.

Input Properties

The instances of an RDF(S)/OWL data source do not have to strictly follow the schema of a class. Indeed, they can have different structures, representing the different versions of this class. The problem of finding the versions of a class is related to the problem of finding the co-occurrence relations between properties. Indeed, a version of a class represents the co-occurrence of its set of properties for at least one instance in the class. The difference is that finding the versions of a class is more general and complete than finding the co-occurrence among properties. However, a user could be interested by the co-occurrence between a specified set of properties or between all the properties describing instances of a class even if they are not declared in the schema. Note that our approach allows to discover the possible versions from any set of properties. We could identify the following three possible sets of input properties according to the user's needs:

1. The set of properties specified by the user. The user may be interested only in some properties declared or not in the schema. He would like to know how these properties co-occur to describe the instances of a class. In this case, our approach allows to discover the versions of the classes for these properties only. Other properties of the class will not be considered in the search and will not be included in the discovered versions. This will result in the description, in the form of versions, of the different co-occurrence relations between the specified properties.

2. The set of properties describing the instances of a class. The set of properties describing the instances of a class c could be obtained using the following queries:

• "Select distinct ?p WHERE {?e rdf:type c . ?e ?p ?y}"(Query 1 (a))

• "Select distinct ?p WHERE {?e rdf:type c . ?y ?p ?e}"(Query 1 (b))

Query 1 (a) returns the outgoing properties of an instance of the class c, while Query 1 (b) returns the incoming properties of an instance of the class c. Note that, if the class c has subclasses, the properties of the instances of these subclasses could be considered to discover the versions of these sub-classes. Indeed, an instance of a subclass of c is an instance of c. The instance e could also be described by the property --------→ f loorCount defined for the class Building. Therefore, our approach takes into account the properties of both the super-classes and the sub-classes when it searches for the different versions of a class. We define the set of associated classes as follows. The set of properties describing the instances of a class (case 2) may contain properties which do no belong to the set of properties of a class specified in the schema (case 3), if some rdf s:domain and rdf s:range declarations are missing. If we make the assumption that the source contains missing declarations, then there may be some declarations about type which are also missing, and therefore there are instances of a class which will not be considered in this case. Note that finding missing declarations about the schema is out of the scope of this paper. This problem was addressed by several works such as in [START_REF] Kellou-Menouer | Schema discovery in RDF data sources[END_REF][START_REF] Paulheim | Type inference on noisy RDF data[END_REF][START_REF] Völker | Statistical schema induction[END_REF][START_REF] Christodoulou | Structure inference for linked data sources using clustering[END_REF][START_REF] Wang | Approximate graph schema extraction for semi-structured data[END_REF][START_REF] Gangemi | Automatic typing of dbpedia entities[END_REF].

During the version discovery process, only the properties belonging to the set of considered properties are taken into account. We define the set of consid-ered properties as follows.

Definition 2 (Set of Considered Properties). The set of considered properties P for a class c is defined according to the user's needs by one of the following cases:

• From the user: if p i is specified by a user then p i ∈ P ;

• From the schema: let C be the set of associated classes of c, ∀ c ∈ C: if ∃ (p i rdf s:domain c ) or ∃ (p i rdf s:range c ) in the data source, then p i ∈ P ;

• From the instances: for each instance e of c, if ∃ (e p i x) or ∃ (x p i e) in the data source, then p i ∈ P .

For example, in Figure 3, the set of considered properties for the class Museum according to the schema is:

P = { --→ label, -------------→ architecturalStyle, --------→ f loorCount, ------→ architect, ← --------- touristicSite}.
To find the different versions of a class, candidate versions are generated from the set of considered properties. A candidate version is validated if it describes some instances in the source.

Class Versions

Let P be the set of considered properties. To find the different versions of c from P , we first generate a candidate version from the properties in P , then we query the data source to get the number of instances having the properties of the candidate version. We define a class version, the set of class versions, and a candidate version in the following.

Definition 3 (Class Version).

A version v i of a class c is a set of properties which describes some instances of c. For v i = {p 1 , ..., p n } to be a version of a class c for the set of considered properties P , the class c must contain at least one instance e such that:

• ∀p j ∈ P : if p j ∈ v i then p j is a property describing e;

• and, ∀p k ∈ P : if p k describes e, then p k ∈ v i .

Definition 4 (Set of Class Versions). The set of versions V of a class c represents the set of possible structures of c for a set of considered properties P . It is defined as follows:

• For each instance e of c, ∃v i ∈ V , such that v i describes e

• For each v i ∈ V , there is an instance e of c, such that v i describes e

In order to discover the versions of a class for a large remote data source, we propose to generate a set of queries based on the set of considered properties P . We now define a candidate version as follows.

Definition 5 (Candidate Version). A candidate version v i of a class c is a combination of k properties from the set of the considered properties P , with k ≤ |P |. v i = {p 1 , ..., p k } is a candidate version for the class c if:

• ∀p j ∈ v i : p j ∈ P .
For example, in order to test the candidate version

v 1 = { --------→ f loorCount, ← --------- touristicSite,
--→ label} of the class Museum, we use the following SPARQL query:

• "Select (COUNT(DISTINCT(?e)) as ?Nb) WHERE -{?e rdf:type Museum . ?e floorCount ?m . ?y touristicSite ?e . ?e label ?n}";

(Query 2)
If the number of instances is positive, then there are instances of c described by the properties of v 1 .

We propose to store the class versions and the number of instance of a version using the VoID5 vocabulary. It is an RDF Schema vocabulary for expressing metadata about RDF data sources. For example, the version v 1 for the class Museum of the Figure 2 When the number of properties of a class is large, this approach is faced with a combinatorial challenge; in addition, some constraints may be imposed by the server of the data source.

A Combinatorial Problem

To find the versions of a class, we propose to generate the possible combinations from the considered set of properties of a class in order to form candidate versions. Let P = {p 1 , p 2 , ...p n } be the set of considered properties for a class c. The candidate versions are all the combinations of k elements from P , where k varies from 1 to n, which represents 2 n combinations and therefore candidate versions. The validated versions are those for which there are instances of the class conforming to this version, and the number of instances represents the number of occurrences of the version. In our approach, a code is associated to each version, where each property in P corresponds to one bit; the version code is defined hereafter.

Definition 6 (version code).

A version code is a binary codification of a class version. We represent each property p i in the set P of the considered properties of a class by one bit in the version code as follows:

• bit(p i ) = 1 if p i is present in the version • bit(p i ) = 0 otherwise
The number of occurrences of each version is estimated according to the number of instances of the class conforming to this version using a Count query as in Query 2.

Figure 4 represents the baseline approach for discovering the versions of the class Museum, which consists in testing all the possible versions. This can be compared to the process of finding a key in cryptanalysis [START_REF] Swenson | Modern Cryptanalysis: Techniques for Advanced Code Breaking[END_REF]: the baseline approach which is an exhaustive search of the versions corresponds to a brute force attack. The number of candidate versions generated from the set of properties P of the class Museum, which has 5 properties, is 2 5 = 32. More generally, the exhaustive search of versions for a class with n properties requires to generate and test 2 n candidate versions. This number may soon be astronomical when the number of properties becomes important. As an example, the number of properties for the class Museum in DBpedia is 285, and the average number of properties for a class is 150 [START_REF] Lehmann | DBpedia-a largescale, multilingual knowledge base extracted from wikipedia[END_REF]. To give an order of magnitude of this number: there are 2 150 candidate versions to be tested, the DBpedia online server6 can test a maximum of 15 queries per second [START_REF] Lehmann | DBpedia-a largescale, multilingual knowledge base extracted from wikipedia[END_REF], the best estimated time for the processing of 2 150 queries therefore is 2 150 /15 seconds ≈ 2 146 seconds, knowing that 1 year = 31 536 000 seconds ≈ 2 25 seconds, 2 146 seconds ≈ 2 121 years ≈ 10 36 years. This is obviously impossible to test.

In addition to the combinatorial problem, two additional difficulties arise in our context:

• All the versions of a class have to be discovered, however we do not know a priori how many versions are valid, and thus when to stop the search;

• Some overlapping between versions may occur, for example, we can see that the set of properties of the candidate version

v i = { -------------→ architecturalStyle, --→ label} is included in the set of properties of the candidate version v j = { --→ label,
-------------→ architecturalStyle, ← ---------touristicSite}, and when the data source is queried to get the number of instances of version v i , the answer will include instances of both versions v i and v j .

Data Source Restrictions

Our goal is to find the versions of a class on a large remote data source. This means that we can not browse the data, but we can only query the server which manages the data source on-line. However, the Web server has generally some restrictions on the data access. Indeed, some queries generate exceptions when a restriction of the Web server is not respected. These restrictions are in place to make sure that everyone has an equal chance to query data from the server, and also to guard against badly written queries and robots. The restrictions could be the followings:

• A limited result size: a Web server limits the maximum size of the returned data to avoid clogging the network;

• A limited time for processing a query: when the number of properties contained in a query is large, this may cause a timeout;

• A limited number of queries: a Web server may have HTTP Access Control Lists which allow the administrator to state a limit for some IP addresses.

If too many queries are sent to the server, this may cause loss of processing priority and the server could even deny access to the source.

For example, if we consider the DBpedia data source, its online server 4 is configured to process queries with a timeout window allowing a maximum execution time of 120 seconds, and a maximum result set size of 2000 rows [START_REF] Lehmann | DBpedia-a largescale, multilingual knowledge base extracted from wikipedia[END_REF]. In addition, if too many queries are sent to the server, this may cause the loss of processing priority.

As our approach queries the server on the number of instances, it is not affected by the restriction on the result set size. However, as the number of properties in a query may be large to test a candidate version, the query cost estimation may exceed 120 seconds. In addition, finding all the versions of a class requires several queries, and a high number of queries may cause loss of processing priority.

Our additional requirements for finding the versions of a class are therefore: using a minimum number of properties in a query to reduce its execution time, and sending the minimum number of queries to the server in order to avoid loosing the processing priority.

SchemaDecrypt: Enabling On-Line Discovery of Schema Versions

Finding the versioned schema of a data source consists in finding the different versions of its classes. In order to find the versions of a class from a large remote data source, we propose the SchemaDecrypt approach. It is based on the construction of a probabilistic class profile which allows to: (i) guide the exploration of candidate versions by testing the most probable versions first; (ii) reduce the search space of candidate versions and (iii) define a stopping criteria for the exploration. We also propose to reduce the considered set of properties to be combined based on the class profile. To reduce the number of candidate versions and the number of queries sent to the data source, we propose to generate some rules between the properties of the class. These rules are exploited during the dynamic generation of candidate versions.

We present our probabilistic class profile in section 4.1, then the reduction of the set of considered properties for a class in section 4.2. We present our approach for deducing some rules between the properties of the class in section 4.3. The dynamic generation of candidate versions is presented in section 4.4, then the exploitation of the rules during the dynamic generation of candidate versions is presented in section 4.5. Finally, a case study for the SchemaDecrypt approach is presented in section 4.6.

Building a Probabilistic Class Profile

As the instances of the same class do not have to follow the exact description of the class, we define a class profile as follows.

Definition 7 (Class Profile).

A profile CP of a class c is formed by the set of considered properties P for a class c with their probabilities, as follows:

• CP = {(p 1 , α 1 ), ..., (p n , α n )}, p i ∈ P , and α i represents the probability for an instance of c to have the property p i .

Each p i represents a property of an instance of the class. The probability α i associated with a property p i in the profile of the class c is evaluated as the number of instances of the class c for which p i is defined over the total number of instances in c.

Note that a property can be incoming, such as the ← ---------touristicSite property, or outgoing, such as the -------------→ architecturalStyle property in Figure 2. The range and the domain of a property are therefore important when querying the data source. To build the profile of a class c, we query the data source on each incoming property p i of the set of considered properties P for a class c as in the Query 3 (a), and on each outgoing property p j as in the Query 3 (b).

• "Select (COUNT(DISTINCT(?e)) as ?propertyOccur) WHERE -{?e rdf:type c . ?e p i ?n }";

(Query 3 (a))

• "Select (COUNT(DISTINCT(?e)) as ?propertyOccur) WHERE -{?e rdf:type c . ?n p j ?e }";

(Query 3 (b))
The probability of a property is therefore the value of propertyOccur divided by the number of instances of the class.

Reduction of the Number of Properties

We propose to reduce the number of combinations to form candidate versions by decreasing the number of properties to test. Given P , the set of considered properties of a class, some properties in P always occur together for the instances of the class; in other words, they are defined for the same occurrences. We propose to identify properties that always occur together and represent them as a single property, which will reduce the number of properties to be tested and therefore the number of combinations and the number of candidate versions to explore.

Algorithm 1: Properties with the same occurrences

Input : The set of considered properties P , the class profile CP Output: All the subsets of properties with the same occurrences E i 1 for ∀p i ∈ P do 2 for ∀p j ∈ P with p i ! = p j do 3 if (α i = α j in CP ) then 4 α i,j = the occurrence probability of p i and p j ; Algorithm 1 represents our approach for detecting properties with the same occurrences. Two properties could have the same occurrences if they have the same probability. Therefore, each pair of properties from the class profile is tested only if these properties have the same probability. The two properties have the same occurrences if the probability to have an instance of the class described by the two properties is equal to the probability of one of the two properties. To compute α i,j , the probability of the properties p i and p j to be defined at the same time for an instance of a class c, we query the data source to get the number of instances in the class described by p i and p j , as follows:

5 if (α i,j = α i ) then 6 if (∃ p i ∈ subSet of properties E i ) then
• "Select (COUNT(DISTINCT(?e)) as ?x) WHERE -{?e rdf:type c . ?e p i ?n. ?e p j ?b }"; (Query 4) Then x is divided by the number of instances of the class c to compute α i,j , the probability of p i and p j . The direction of a property (incoming of outgoing) is taken into account when formulating the query.

We represent each subset E i (see Algorithm 1) of properties having the same occurrences by a single property in our approach. However, this single property is replaced in the discovered versions by the subset that it represents. In addition, the properties in the class profile with a probability of 1 are in all versions, and therefore it is not worth introducing them during version testing. However, they are added in each discovered version. In the same manner, the properties in the class profile having a probability of 0 are not considered because they are not present in any version of the class. We define the reduced set of considered properties for a class as follows.

Definition 8 (Reduced Set of Considered Properties). A reduced set E of the set of considered properties P for a class, is formed by properties of P such that ∀p i ∈ P , p i ∈ E if:

• ∃p j ∈ E, and p j with the same occurrences as p i

• and α i ∈ ]0, 1[

Rule Deduction

Due to the restrictions of the online server on the data source, if too many queries are sent, this may cause the loss of processing priority and may even result in a denied access by the server. In addition, when the number of properties contained in a query is large, this may cause a timeout. To reduce the number of issued queries and minimize the number of properties in a query, we propose to detect rules between the considered properties of the class.

We propose to deduce two types of rules between the properties of a class: (i) inclusion rules (p i ⇒ p j ) which indicate that the occurrences of the property p i are included in the occurrences of the property p j and (ii) exclusion rules (p i | p j ) which indicate that the properties p i and p j never occur together and therefore the occurrences of p i are disjoint from the occurrences of p j . These rules will allow, among other things, to know locally if some candidate versions can be actual versions of the class, without sending the associated queries to the remote data source. Indeed, if each time a property p i occurs then the property p j occurs, we can deduce that p i ⇒ p j . This means that the candidate versions with p i and without p j do not exist, and it is not worth sending the associated queries to the data source. Another type of rule is defined when the properties p i and p j never occur together; this Not AND (NAND) relation is denoted p i | p j . This means that candidate versions with p i and p j do not exist, and therefore there is no need to sent the associated queries to the data source.

Let E be the reduced set of considered properties of a class c, α i (resp. α j ) the probability of a property p i (resp. p j ) to describe an instance of a class c in the class profile, and α i,j the probability of the properties p i and p j to describe an instance of c. We propose to find inclusion and exclusion rules between the properties of the class c as follows.

Inclusion Rules

To determine the inclusion rules between the properties of a class, we do not test each pair of the considered properties for the class, but only the ones for which an inclusion is possible. Indeed, an inclusion is possible between two properties if the probability of one of them is higher than the probability of the other. We determine the inclusion rules in a class as follows:

• ∀ p i , p j ∈ E, if α i != α j in the class profile, then:

-Compute α i,j as in Query (3)

-If (α i,j = α i ) then (p i ⇒ p j ) is an inclusion rule -Else, if (α i,j = α j ) then (p j ⇒ p i )

is an inclusion rule

Note that an inclusion rule is not a functional dependency. Indeed, a functional dependency expresses a constraint on the values of the properties while in our approach, an inclusion rule expresses a constraint on the existence of the properties.

Exclusion Rules

To determine the exclusion rules between the properties of a class, we do not test each pair of the considered properties of the class, but only the ones for which an exclusion is possible. Indeed, an exclusion is possible between two properties if the addition of the probabilities of the two properties is less than 1 or equals to 1. We determine the exclusion rules in a class as follows:

• ∀ p i , p j ∈ E, if α i + α j ≤ 1 in the class profile, then: -Compute α i,j as in Query (3) -If (α i,j = 0) then (p i | p j ) is an exclusion rule 4.

Dynamic Generation of Candidate Versions

In order to find the different versions of a class, we gradually generate candidate versions from the reduced set of properties E, until all the versions of the class are found, as described in Algorithm 2. We use our version code as a binary codification of a candidate versions, where each property in E is represented by one bit. We propose to initialize the version code to its maximum value (2 |E| -1) and decrement it until finding all the versions of the class. This allows to test candidate versions in an ordered manner and avoid building the graph of combinations a priori, which optimizes the memory used during the process.

Initializing the version code to its maximum value allows to test first the versions which contain the highest number of properties, in order to obtain the exact number of their occurrences in the data source. Indeed, some overlapping between versions may occur, and testing the ones with the highest number of properties will avoid counting the same instances several times. For example, we can see that the properties of the version

v i = { --→ label, -------------→ architecturalStyle} are included in the set of properties of the version v j = { --→ label, -------------→ architecturalStyle, ← ---------
touristicSite}, and when the data source is queried to get the number of instances having the properties of the version v i , the answer will also include instances having the properties of both versions v i and v j . We consider the number of occurrences of a version Occurrences(v i ) as the number of instances having only the exact properties in the version, and Count(v i ) the number of instances returned by the data sources. Let V be the set of versions which are validated when v i is being tested. The number of occurrences of v i is computed as in Formula 1.

Occurrences(v i ) = Count(v i ) - ∀vj ∈V ∧vi⊂vj Occurrences(v j ) (1)
If Occurrences(v i ) > 0, the candidate version v i is validated and added to the set of validated versions V .

Each time a candidate version is validated, the class profile is updated so that the probabilities reflect only the versions which have not been discovered yet. This will allow to define the stopping criterion, which will be reached when the value of all the probabilities in the class profile are equal to 0, which means that all the versions of the class have been discovered (see lines 13 and 14). The corresponding profile of the class is updated using the UpdateClassProfile function presented in Algorithm 3, which updates the probability of each property in the discovered version.

If a property probability changes to 0 in the class profile, this means that all the versions that contain this property have been found. In this case, the property is removed from E, the set of properties from which the versions will be generated (see line 14 in Algorithm 2). We then reset the version code to have a bit number equals to the number of properties in E.

In order to test the most probable versions first, we order the set E from the most probable to the least probable property (see lines 2 and 17 in Algorithm Let q the corresponding query of v i ;

7

Reduce the size of q according to the inclusion rules in R;

8

Send the query q to the data source;

9 if (Count(v i ) > 0) then Occurrences(v i ) = Count(v i ) -∀vj ∈V ∧vi⊂vj Occurrences(v j ); if (Occurrences(v i ) > 0) then Add v i to V and save Occurrences(v i ); UpdateClassProfile(CP , v i );
Remove from E the property with probability equals to 0 in CP ;

α ← α -Occurrences(v)
nbInstancesInClass ; 4 end 2). For each generated candidate version, SchemaDecrypt checks whether this version complies with the rules. A candidate version has some instances in the data source if it complies with all the rules. If a candidate version complies with all the rules, we generate the corresponding query and use the inclusion rules to reduce its size. However, if a candidate version violates any of the rules, the algorithm jumps to the next candidate version which does not violate the rules. We exploit the deduced rules for different purposes in Algorithm 2: (i) testing if a candidate version is possible (see line 5); (ii) reducing the size of a query (see line 7) and (iii) jumping to the next candidate version that does not violate the rules (see line 23). In the next subsection, we detail each of these steps.

Rule Exploitation

We propose to exploit the inclusion and exclusion rules during class version discovery in Algorithm 2. Let r = p i ϕ p j be a rule, where ϕ ∈ {⇒ , |}. If r is an inclusion rule, this means that if any instance of the class is described by the property p i , then it is also described by the property p j . Therefore the property p j is unnecessary in a query which includes the property p i , and p j can be removed from the query to have a better response time. Indeed, the more properties in a query, the higher the response time, which may cause a timeout.

If a candidate version does not comply with a given rule, there is no need to send its query to the data source, because it will return a number of occurrences which is equal to 0: if r is an inclusion rule, there are no instances in the data source with bit(p i ) = 1 and bit(p j ) = 0; if r is an exclusion rule, there are no instances in the data source with bit(p i ) = 1 and bit(p j ) = 1.

If a candidate version does not comply with a rule, some of its following versions might not comply with the rule as well. In this case, it is more efficient to jump directly to the next version which complies with the rule, but the problem is how to find this version? The next version which complies with the rule is the first which modifies either bit(p i ) or bit(p j ). The first bit which will be modified by decreasing the version code is the minimum between i and j, as shown in Figure 5. The next version which complies with the rule has a version code calculated as described in Formula 2.

version code = version code -Jump

With the Jump calculated as described in Formula 3.

Jump = version code (mod 2 min(i,j) ) + 1 (3)

Rule Processing

Let r = p i ϕ p j be a rule, where ϕ ∈ {⇒ , |}. As previously described, we propose to exploit this rule as follows:

• The property p j is removed from the query if ((ϕ = ⇒) ∧ (bit(p i ) = 1) ∧ (bit(p j ) = 1))

• A candidate version is discarded if it does not comply with the rule, in the following cases:

-(ϕ = ⇒) ∧ (bit(p i ) = 1) ∧ (bit(p j ) = 0) -(ϕ = | )∧ (bit(p i ) = 1) ∧ (bit(p j ) = 1)
• If a rule is violated then the next version code to test is calculated as described in Formula 2.

Even if a property is removed from a query, its probability in the class profile will still be updated for each validated version to which it belongs.

Rule Selection

A candidate version may violate several rules, in this case which rule should be considered first? The problem here is whether there is an optimal order to process the rules.

Consider the set of rules R ={ p 0 ⇒ p 2 , p 2 | p 3 , p 4 | p 6 }. Figure 6 shows an example of versions which violate several rules. We can observe that the rule p 4 | p 6 cancels the effect of the rule p 0 ⇒ p 2 and p 2 | p 3 , which requires a new processing of these rules. More generally a rule r = p i ϕ p j , where ϕ ∈ {⇒ , |}, can affect the processing of all the rules r = p i ϕ p j having their min(i , j ) < min(i, j). This is due to the fact that for each property which index is less than min(i, j), the corresponding bit will be set to 1 after processing the rule r.

In order to avoid unnecessary loops, rules which are violated by the current version code must be ordered, so as not to cancel the effect of the previous rules. This requires maximizing the first jumps by processing the rules having the highest min(i, j) first. Let R = {r 1 , ...r n } be a set of rules, the first property Index to change is calculated as in Formula 4. Index = M ax n k=1 M in(i, j); r k = p i ϕp j (4) Figure 7 shows the example with the optimal exploitation of the same rules. We can observe that, for three rule violations, there are three rule processing instead of five in Figure 6.

Case Study

Considering our example given in section 2, let us assume that a data source have these different instances e i of Museum described as follows:

• e 1 : { --→ label, -------------→ architecturalStyle, ← --------- touristicSite, ------→ architect}; • e 2 : { --→ label, -------------→ architecturalStyle}; • e 3 : { --→ label, -------------→ architecturalStyle, ← --------- touristicSite, ------→ architect}; • e 4 : { --→ label, --------→ f loorCount, ← --------- touristicSite, ------→ architect}; • e 5 : { --→ label, -------------→ architecturalStyle, ← --------- touristicSite, ------→ architect}; • e 6 : { --→ label, -------------→ architecturalStyle, ← --------- touristicSite, ------→ architect}; • e 7 : { --→ label, --------→ f loorCount, ← --------- touristicSite, ------→ architect}; • e 8 : { --→ label, -------------→ architecturalStyle, ← --------- touristicSite, ------→ architect}; • e 9 : { --→ label, -------------→ architecturalStyle}; • e 10 : { --→ label, --------→ f loorCount, ← --------- touristicSite, ------→ architect}.
To find the different versions of a Museum from the schema of this remote data source, SchemaDecrypt first discovers the considered set of properties for the class Museum (see section 3.1):

• P = { --→ label, -------------→ architecturalStyle, --------→ f loorCount, ← --------- touristicSite, ------→ architect}.
Then, it builds the profile of the class (see section 4.1), which is the following:

• CP = {( --→ label, 1), ( --------→ f loorCount, 0.3), ( -------------→ architecturalStyle, 0.7), ( ← --------- touristicSite, 0.8), ( ------→ architect, 0.8)}.
After that, the set of considered properties is reduced if possible (see section 4.2). This is done according to the following steps:

• The properties with the same occurrences (see Algorithm 1) are detected:

the properties ← ---------touristicSite and ------→ architect have the same occurrences as they describe the same instances of Museum, therefore they are represented by a single property (considering ← ---------touristicSite this property);

• The properties with a probability equals to 1 are ignored, such as the property --→ label.

SchemaDecrypt deduces the following reduced set of considered properties:

• E = { -------------→ architecturalStyle, --------→ f loorCount, ← --------- touristicSite}.
From the remote data source, SchemaDecrypt discovers inclusion and exclusion rules between the properties in E (see section 4.3), as follows:

• The sum of probabilities corresponding to the properties --------→ f loorCount and -------------→ architecturalStyle in the class profile CP is less than or equal to 1 ( 0.3 + 0.7 <= 1), which indicates that they may never occur together. SchemaDecrypt queries the remote data source on the number of instances of Museum described by these two properties. The source returns 0 which indicates that these two properties never occur together and therefore the occurrences of the property --------→ f loorCount are disjoint from the occurrences of -------------→ architecturalStyle. Indeed, in the remote data source, the set of instances {e 4 , e 7 , e 10 } which are described by the property --------→ f loorCount is disjoint from the set of instances {e 1 , e 2 , e 3 , e 5 , e 6 , e 8 , e 9 } which are described by the property -------------→ architecturalStyle.

• The properties --------→ f loorCount and ← ---------touristicSite have different probabilities in the class profile CP . SchemaDecrypt computes, by querying the remote data source, the probability for an instance of Museum to be described by the two properties. This probability is equal to 0.3 which is the same probability of the property --------→ f loorCount. Therefore, the occurrences of the property --------→ f loorCount are included in the occurrences of the property ← ---------touristicSite. Indeed, in the remote data source, the set of instances {e 4 , e 7 , e 10 } which are described by the property --------→ f loorCount is included in the set of instances {e 1 , e 3 , e 4 , e 5 , e 6 , e 7 , e 8 , e 10 } which are described by the property ← ---------touristicSite.

The following rules are therefore valid:

• r 1 = --------→ f loorCount | -------------→ architecturalStyle; • r 2 = --------→ f loorCount ⇒ ← --------- touristicSite.
In the following, SchemaDecrypt gradually generates candidate versions from the reduced set of properties E, until all the versions of the class are found (see Algorithm 2).

The set E is ordered according to the probabilities of the properties in the class profile CP , as follows:

• E = { ← --------- touristicSite, -------------→ architecturalStyle, --------→ f loorCount}
The version code is initialized to its maximum value: version code = 2 |E| -1 = (111) 2 . The candidate version which corresponds to the version code violates the rule r 1 , therefore, the corresponding query is not sent, and SchemaDecrypt jumps to the next version which complies with the rule: next version code = version code -jump = version code -1 = (110) 2 . The candidate version complies with all the rules, therefore the corresponding query is generated and sent. The answer from the data source to this query is 5. SchemaDecrypt adds the following version to the set of validated versions V :

• v 1 = { --→ label, -------------→ architecturalStyle, ← --------- touristicSite, ------→
architect}, with a number of occurrences of 5.

In order to check if all the versions are found and if the stopping criterion is reached, SchemaDecrypt updates the class profile to take into account instances of version v 1 as follows: CP = {( --------→ f loorCount, 0.3), ( -------------→ architecturalStyle, 0.2), ( ← ---------touristicSite, 0.3)}. Since no probability has reached 0, the next version code is 101 2 . According to the rule r 2 , the data source is queried with the property --------→ f loorCount only, because the set of instances described by this property is included in the set of instances described by the property ← ---------touristicSite. The answer from the data source to this query is 3. SchemaDecrypt adds the following version to the set of validated versions V :

• v 2 = { --→ label, --------→ f loorCount, ← --------- touristicSite, ------→
architect}, with a number of occurrences of 3. ← ---------touristicSite, 0)}. We remove from E the properties which probabilities reach 0:

SchemaDecrypt updates the class profile to take into account instances of version v 2 as follows: CP

= {( --------→ f loorCount, 0), ( -------------→ architecturalStyle, 0.2), (
• E = { -------------→ architecturalStyle}.
The next version code = 2 |E| -1 = 1 2 . The candidate version complies with all the rules, therefore the corresponding query is built and sent. The answer from the data source to this query is 7 for version

v 3 = { --→ label, -------------→ architecturalStyle}. As v 3 ⊂ v 1 then Occurrences(v 3 ) = Count(v 3 ) -Occurrences(v 1 ) = 7 -5 = 2.
SchemaDecrypt adds the following version to the set of validated versions V :

• v 3 = { --→ label, -------------→
architecturalStyle}, with a number of occurrences of 2.

SchemaDecrypt updates the class profile which results in having all the probabilities set to 0. The properties for which the probabilities are equal to 0 are removed from E, and the stopping criteria is reached as E = ∅.

Note that properties ignored during version discovery are added in validated versions as follows:

--→ label property has been added to all versions (v 1 , v 2 , v 3 ) because it has a probability equals to 1;

------→ architect property has been added to versions (v 1 , v 2 ) which contain ← ---------touristicSite property because they have the same occurrences;

← ---------touristicSite property has been added to version (v 2 ) which contains --------→ f loorCount according to r 2 . The class Museum has 3 versions. SchemaDecrypt has generated 4 candidate versions and it has sent 3 queries to the data source which are all validated, while an exhaustive search (baseline approach) would have generated 32 candidate versions and sent 32 queries (see Figure 4).

SchemaDecrypt++: Parallel and On-Line Discovery of Class Versions

In this section, we present an extension of SchemaDecrypt which consists in parallelizing the exploration of candidate class versions. Two versions can be tested in parallel if their sets of instances are disjoint. In order to parallelize the discovery process, we propose to identify sets of versions that do not overlap, and we represent them using the notion of version template.

In this section, we present the generation of version templates which can be explorable in parallel in section 5.1. We describe the dynamic generation of the exploration graph of the version templates in section 5.2. Then, we describe our approach for pruning this exploration graph in section 5.3. In section 5.4, we describe how a version template is processed.

Building Version Templates

Exclusion rules highlight properties that never occur together. The approach SchemaDecrypt uses these rules to reduce the search space by avoiding the test of candidate versions that do not respect them. In SchemaDecrypt + +, we also propose to use these rules to parallelize the discovery process. This is done by forming subsets of properties from the reduced set of properties E of a class (see section 4.2), using the exclusion rules. We introduce the notion of version template to represent each subset of versions.

The parallelization of the exploration of two version templates is possible if there is no overlap between their respective sets of candidate versions. Two candidate versions have disjoint sets of instances if they respectively contain properties that never occur together, i.e. two properties that are part of the same exclusion rule. For example, consider the exclusion rule r 1 = p 3 | p 4 and the two candidate versions v 1 = {p 1 , p 2 , p 3 } and v 2 = {p 1 , p 2 , p 4 }; v 1 and v 2 have two disjoints sets of instances because they contain respectively the properties p 3 and p 4 , which are part of an exclusion rule. We define a version template as follows.

Definition 9 (A Version Template).

A version template M is a set of properties that characterizes a set of candidate versions V M . Let E be the reduced set of properties of a class c; the set M is such that:

• Each property in M is a property in E;

• Some properties in M may be mandatory; if p is mandatory in M then p must appear in all candidate versions of V M . A mandatory property is denoted p;

• The set V M is the set of all possible candidate versions generated from M .

Note that the reduced set of properties E is a particular version template where no property is mandatory. A version template is first extracted from the reduced set of properties E. It can also be extracted from another version template.

We propose to build version templates which are explorable in parallel by exploiting an exclusion rule. Let F = {p 1 , ..., p i , ..., p j , ..., p n } be a version template, and consider the exclusion rule r 1 = p i | p j . For F to be explorable in parallel, as described in Figure 8, three version templates are built:

• A version template M 1 = {p 1 , ..., pi , ..., p j-1 , p j+1 , ..., p n }, which contains all the properties of F except p j and in which the property p i is mandatory for all its candidate versions (noted pi );

• A version template M 2 = {p 1 , ..., p i-1 , p i+1 , ..., pj , ..., p n }, which contains all the properties of F except p i and in which the property p j is mandatory for all its candidate versions (noted pj );

• A version template M 3 = {p 1 , ..., p i-1 , p i+1 , ..., p j-1 , p j+1 , ..., p n } which contains all the properties of F except p i and p j . The version templates M 1 and M 2 are explorable in parallel because each contains a mandatory property that does not exist in the other version template.

As a result, there is no overlap between the candidate versions of M 1 and M 2 . However, the version template M 3 does not contain any mandatory property from the exclusion rule r 1 , which makes it non exclusive of M 1 and M 2 . As a result, there may be an overlap between the candidate versions of M 1 and M 3 , or between M 2 and M 3 . For example, let v 3 = {p 1 , p 2 , p 4 } a candidate version from M 3 , v 1 = {p 1 , p 2 , p i , p 4 } a candidate version from M 1 , and v 2 = {p 1 , p 2 , p j , p 4 } a candidate version from M 2 . When the data source is queried for the number of instances of v 3 , the answer will include instances of v 1 , v 2 , and v 3 . To obtain the number of instances of v 3 only, we must first query the source for the number of instances of v 1 and the number of instances of v 2 , then subtract these numbers from the number of instances returned for v 3 , as in Formula 1 (see section 4.4). Generally speaking, we first have to find versions of the templates M 1 and M 2 in parallel and then explore the template M 3 as described in Figure 8. In Figure 9, let us assume the version template M 1 = {p 1 , ..., pi , ...p k , ..., p n } and the rule r 2 = p i | p k . In this case, the exclusion rule r 2 is exploited by removing the property p k from M 1 because the property pi is mandatory in M 1 and therefore must be included in all its sub-sets.

Dynamic Generation of the Version Template Graph

The properties of a class can have several exclusion rules. We propose to order these rules starting from those which properties have the most constraints, i.e. which are affected by the largest number of exclusion rules, in order to minimize the potential size of the graph to explore. Let R = {r 1 , r 2 , ..., r n } be this ordered set of exclusion rules.

The number of version templates to explore in parallel at any given time should not be greater than the data source's ability to process queries in parallel. Indeed, each version template is explored by a sub-process which sequentially queries the source to validate its candidate versions. If the number of subprocesses is greater than the capacity of the data source to process queries in parallel, this will increase the response time. In this case, it is preferable not to parallelize some exploration tasks so as not to overload the data source and thus keep an optimal response time. We propose to generate parallel sub-processes without exceeding the maximum number of parallel queries supported by the data source denoted M axT ask. Indeed, it is better to exploit some exclusion rules locally by jumps, as described for the sequential exploration of versions with SchemaDecrypt (see section 4.5), than to introduce waiting times. Let version templates be the list of version templates from E to be processed in parallel at a given time. This list initially contains the property set E. Each element M r in the list version templates is checked with respect to the current exclusion rule r i . If M r violates the rule, new version templates are generated as described in section 5.1. Processing M r can generate two parallel version templates to be saved in the list version templates, and a version template to be explored later in stack M . The exclusion rule that caused the stack of a version template is also stacked in stack R to synchronize the processing of stacked version templates. When the number of version templates in the list version templates reaches M axT ask or when all exclusion rules have been processed, a sub-process is created for each version template in the list version templates.

We propose to prune the exploration graph of the version templates (line 17 in Algorithm 4) by removing the ones which have no instances in the data source. We describe this process in section 5.3.

Each version template is explored by a sub-process (line 27 in Algorithm 4), which will be described in section 5.4. In order to synchronize the discovery process among the parallel sub-processes, the following data is shared between them:

• P c: the class profile with the probabilities of the properties; this profile is updated each time a sub-process validates a version;

• version list: the list of validated versions. Each time a sub-process validates a version, it is added to this list with its number of occurrences;

• N bT hread: The number of parallel versions to explore. This number is incremented each time a sub-process is created to explore a version template, and it is decremented when the sub-process completes its exploration. N bT hread should not exceed the capacity of the data source to process parallel queries M axT ask.

Each sub-process updates the list of validated versions (version list) and the profile of the class (P c) according to the number of occurrences of the validated versions. Each time a sub-process finishes, the value of N bT hread is decremented. When all the sub-processes created by the current rule are terminated or when N bT hread = 0, the version templates stacked by the current rule are processed. Properties which probability has reached 0 in the type profile are removed from these version templates. The resulting templates are then checked against the other rules. The process stops when all the probabilities in the class profile are equal to 0.

Figure 10 illustrates the execution of Algorithm 4. We can see that the process of building and processing version templates is represented by a graph. The generation of the graph is done dynamically as the sub-processes are created and as they complete their execution, until all versions of the class have been found.

Figure 11 shows a possible instanciation of the graph in Figure 10, assuming that the data source can process at most 3 queries in parallel (M axT ask = 3). Exclusion rules is exploited for parallelization as long as the number of version templates has not reached M axT ask.

The function M akeCompatible described in Algorithm 5 is used to transform a version template M r that does not respect an exclusion rule r i into one or two version templates that respect this exclusion rule as described in section 5.1.

Pruning the Version Template Exploration graph

During the generation of the version templates, some of them may have no actual instances in the data source and are therefore not considered. In this section, we describe this pruning process. When creating a new version template with several mandatory properties in the exploration graph, a query is generated to check if there are instances in the data source having these mandatory properties. If the answer is equal to 0, then the version template is removed from the exploration graph. This reduces the number of combinations Figure 12 illustrates this pruning process on the example of Figure 10 assuming that the properties p 8 and p 9 are mandatory. When exploiting the rule r 1 = p 1 | p 2 , a version template is created, containing the mandatory properties p 2 , p 8 and p 9 . The data source is queried to find if there are instances of the class having the mandatory properties p 2 , p 8 , and p 9 . The data source returns a value of 0, and therefore the corresponding branch is pruned in the exploration graph. We can see that in Figure 12, 6 sub-processes are executed, whereas in Figure 10, 9 sub-processes are executed.

Version Template Exploration

In the previous sections, we have described the dynamic generation of version templates and the pruning of the exploration graph. In this section, we present the exploration of a given version template. This process is similar to the dynamic generation of candidate versions presented for SchemaDecrypt (see section 4.4), considering that there may be some mandatory properties in the candidate versions of the template. In addition, we propose to reduce the number of optional properties in a version template: an optional property p is removed if there are no instances having p and all the mandatory properties of the version template.

Discovering New Rules

A version template identifies a subset of instances of the class in the data source. Instances of a version template are characterized by the mandatory properties of the template. Inclusion and exclusion rules that characterize the class are checked for instances that match this version template; but in addition, other rules can characterize them in their own right. These new rules are detected in the same way as for the instances of the class, except that the mandatory properties of the version template are added to each query to be able to distinguish the instances of that version template from the other instances of the class.

In order to discover the exclusion and inclusion rules that hold for a given version template, the profile of the version template is first built: the probability of each non-mandatory property of the template is calculated, adding for each one the mandatory properties in the query so that it only considers the version template explored by the sub-process.

Each sub-process finds the inclusion and exclusion rules between the properties of its version template. Let P oblig be the set of mandatory properties, α i,P oblig (resp. α j,P oblig ) the probability of a property p i (resp. p j ) to describe an instance of a subset c of instances of a class c, and α i,j,P oblig the probability of the properties p i and p j to describe an instance of the subset c . We propose to find the inclusion and exclusion rules between the properties of the versions template M as follows:

Inclusion rule. The inclusion rules between the properties of a version template M are determined by testing each pair of properties p i , p j ∈ M , with α i,P oblig != α j,P oblig in the profile of the sub-set c of instances of the template M , as follows:

• If (α i,j,P oblig = α i,P oblig ) then (p i ⇒ p j in c )

• If (α i,j,P oblig = α j,P oblig ) then (p j ⇒ p i in c ) Exclusion rule. The exclusion rules between the properties of a version template M are determined by testing each pair of properties p i , p j ∈ M , with (α i,P oblig + α j,P oblig <= 1) in the profile of the sub-set c of instances of the template M , as follows:

• If (α i,j,P oblig = 0) then (p i | p j in c )

Rule Exploitation

In SchemaDecrypt + +, some inclusion rules are exploited specifically because of the presence of mandatory properties in the version template and because some of these rules apply only to this version template. Exploiting these rules for a version template M is as follows:

1. If there is an inclusion rule pi ⇒ p j , this means that the non-mandatory property p j is still present in the versions of the template. In this case, it is not useful to test it and it is removed from M and added directly to each validated version; 2. If all the versions containing a non-mandatory property p k are found, which corresponds to a probability of 0 for p k in the class profile, then p k and all the properties p j such that: p j ⇒ p k are removed from each version template M . Note that this case is only possible if this rule is specific to M . Indeed, if it was valid for all the instances of the class, a value of 0 for the probability of p k would only occur if the value of the probability for p j was also 0; 3. If the non-mandatory property with the highest probability is p k , and all versions containing this property are explored for M , then all the properties p j such that: p j ⇒ p k are removed from M . Note that this case is only possible if this rule is specific to M . Indeed, if it was valid for all the instances of the class, it would not be possible to have explored all the versions containing p k without having first explored those containing p j .

More generally, the inclusion rules are exploited by deleting each optional property p j in M , in the two following cases:

• p i is a mandatory property and pi ⇒ p j (p j is then added to each validated version in M );

• When deleting a non-mandatory property p k or completing its exploration, and p j ⇒ p k is an inclusion rule specific to M .

Note that despite the deletion of a property, its probability in the profile is updated for each version found. In addition, as in SchemaDecrypt, each exploration process of a version template exploits its inclusion rules by executing jumps in the version code and reducing the number of properties in a query as previously described in section 4.5.

In SchemaDecrypt + +, exclusion rules are initially exploited to find the version template graph. However, if the number of version templates reaches the maximum number of queries that the data source can process in parallel, as in Figure 11, some rules remain unexploited in some version templates, such as rule r 3 = p 4 | p 5 in version template M 2 = { p2 , p 3 , p 4 , p 5 , p 6 , p 7 }. Such rules are exploited by executing jumps as previously described in SchemaDecrypt (see section 4.5).

Analyzing the Cost of Version Discovery

In this section, we discuss the cost of the proposed approach. Each exclusion rule allows to parallelize the exploration of the candidate versions. However, for parallel exploration to actually improve performance, the data source must be able to process multiple queries in parallel. In this analysis of the cost of our approach, we consider the worst case where the source can only process one query at a time.

The number of queries sent to a data source reflects the cost of an on-line approach for discovering the versions of a class. SchemaDecrypt(++) performs a statistical analysis of the properties of a class before attempting to discover its versions. This results in building a probabilistic class profile by sending n queries to the data source, with n being the number of considered properties for a class. It also computes probabilities between some pairs of properties to deduce sets of properties with the same occurrences and identify inclusion and exclusion rules. Only the pairs of properties satisfying some conditions are tested, as seen in sections 4.2 and 4.3. Therefore, SchemaDecrypt(++) queries the data source at most C 2 n = n × (n -1)/2 times. This represents the number of combinations of each pair of properties among n.

The processing time for a query testing a candidate version is more important than the time required to detect a rule: a query for a candidate version is composed of all the properties of the candidate version while a query for detecting a rule is composed of only two properties. Note that the query answering time increases as the number of properties in the query increases. The key issue to evaluate the complexity of our approach is therefore the a priori estimation of the number of queries sent to the data source to find the versions.

We can not determine a priori the number of candidate versions tested by a query, as they are generated until all the versions of the class are found (we can not determine the number of versions of a class a priori ). However, we can estimate the number of queries sent to the data source in the worst case: the versions of the class are not found until all candidate versions are tested by issuing a query.

The number of queries sent by SchemaDecrypt(++) to the data source is related to the number of considered properties of a class and the number of discovered inclusion and exclusion rules. Let n be the number of considered properties for a class in the set E, the complexity of the exhaustive search of the class versions is therefore 2 n , which represents the number of candidate versions.

Let h be the number of discovered inclusion and exclusion rules for the entities of the class. Each rule decreases the complexity of an exhaustive search (2 n ) by 2 n-2 , because each rule implies two properties. For example, for a rule r = p i | p j , the number of combinations not to be tested is 2 n-2 (2 n -2 n-2 combinations remain to be tested), as follows:

Each rule decreases the complexity of an exhaustive search by 2 n-2 , because each rule implies two properties. However, a rule r 1 may collide with another rule r 2 . We consider that a collision between the rules r 1 and r 2 occurs when a candidate version does not comply with both rules r 1 and r 2 . In this case, the reduction in the number of combinations is not (2 * 2 n-2 ), but (2 * 2 n-2 -the number of collisions). More generally, let N bCollision be the number of collisions between the rules; the number of combinations combN b to test according to the number of rules h for a class is calculated as in Formula 5.

combN b = 2 n -h * 2 n-2 + N bCollision (5)
For example, consider the two rules: r 1 = p i ⇒ p j and the rule r 2 = p i | p k ; the discarded combinations are the followings:

In this example, the number of collisions is 2 n-3 , because the two rules involve three properties. Two rules are independent if they do not share any property and therefore, they involve four distinct properties. In this case, the number of collisions is 2 n-4 . For example, consider the rule r 1 = p i | p j and the rule r 2 = p k ⇒ p v ; the discarded combinations are the followings:

In some case, two rules never collide. For example, consider the rules r 1 = p i ⇒ p j and r 2 = p j | p k . A collision occurs when:

• r 1 is violated if: bit(p i ) = 1 and bit(p j ) = 0

• r 2 is violated if: bit(p j ) = 1 and bit(p k ) = 1
The collision is impossible because bit(p j ) can not be equal to 1 and to 0 at the same time, therefore the number of collisions between the rules r 1 and r 2 is equal to 0.

We can observe that the number of collisions between the rules differs according to the types of the rules and whether they are independent. We summarize the different cases to determine the number of collisions between two rules collisionN b(r a , r b ) in Formula 8.

The number of queries sent by SchemaDecrypt(++) to discover the versions depends on the number of deduced rules h and the number of considered properties n for a class. Each rule decreases the complexity of an exhaustive search (2 n ) by 2 n-2 , because each rule involves two properties. However, some candidate versions do not comply with several rules at the same time, which causes a collision between the rules. Let collisionN b(r a , r b ) be the number of collisions between two rules r a , r b as described in Formula 8. Let N bQueries be the number of queries sent to the data source to test candidate versions according to the number of collisions T otalColl between each pair of rules. The number of queries sent to the data source is calculated as in Formula 6.

N bQueries(n

, h) = 2 n -h * 2 n-2 + T otalColl (6)
The number of collision between each pairs of rules T otalColl is calculated as in Formula 7.

T otalColl = h a=2 a-1 b=1 collisionN b(r a , r b ) (7)

Evaluation

This section presents some experimental results using SchemaDecrypt + + to find different versions of a class. We have evaluated the performances of SchemaDecrypt and compared them to those of SchemaDecrypt + +, to show the effect of parallelism and dynamic pruning of the exploration graph on a real data source. We have also illustrated the usefulness of versions for the example presented in the motivation section.

Data Source and Methodology

We have evaluated the performance of our approach to provide exact versions of classes from the properties declared in the schema, using a real remote data source: DBpedia7 , which currently contains over 3.77 million instances; it contains more than 1.89 billion RDF triples. We chose this data source because the number of properties of an instance is rather high: 150 properties on average. To discover versions of a class, SchemaDecrypt(++) queries this remote data source through a SPARQL endPoint 8 .

We have used SchemaDecrypt(++) to discover the versions of the following classes in DBpedia: Historian, Poet, Restaurant, Museum, ShoppingMall, Stadium, Mountain and Park. We have deliberately selected classes with a high number of properties in the schema (between 243 and 462) to test the effectiveness of the approach. Note that DBpedia is in constant evolution because it is automatically enriched from Wikipedia. As a result, there may be a slight difference in the number of properties and versions of a class at different times, as between our experiments made in [START_REF] Kellou-Menouer | On-line versioned schema inference for large semantic web data sources[END_REF] and the one presented in this paper.

To illustrate the usefulness of versions to identify relevant sources, for the case presented in the motivation section, we have build from the instances of the class Museum three different data sources: S1, S2 and S3. These sources are not described by a versioned schema. To test our approach on a set of properties defined by the user, we consider for example that the user is interested by architectural informations about museums, which are described through the following set of specified properties:

P = { -------------→ architecturalStyle, ----------------→ yearOf Construction, --------→ f loorCount,
------→ architect, -----→ location}. SchemaDecrypt + + is used to discover, for each data source, the versions of the class Museum on this set of considered properties P . In this experiment, we conduct a preliminary user study to show how versions could help a user to identify relevant sources and reducing the number of queries send to these sources.

SchemaDecrypt + + is implemented in Java with multithread programming. A thread is started for each version template exploration. To synchronize the search for class versions, some resources (class profile, list of validated versions and the number of running threads) are shared among the threads which concurrently write in them. source (see Figure 13 (b)). Indeed, the response time of the query represents the most important part of the total processing time.

SchemaDecrypt + + is also influenced by the number of versions of a class which is represented by the number of validated versions in Figure 13 (b). The time required to find the versions of a class is proportional to the number of its versions: the more versions in a class, the longer it takes for SchemaDecrypt + + to find them. Indeed, the time required to reach the stopping criteria is proportional to the number of versions because the probabilities of the properties of the class profile decrease more slowly. For example, the class Historian and Poet have exactly the same number of properties (462); but the time required to generate the candidate versions for the class Historian is 279 seconds with 84 validated versions. For the class Poet the processing time is 26 seconds with 42 validated versions. The class Mountain has fewer properties (264), but it takes the most important time to generate the candidate versions (844 seconds) as it has the most important number of version (479).

Table 2 summarizes the performances of SchemaDecrypt, SchemaDecrypt+ + and the estimated performances of the baseline approach for finding class versions from a remote data source. The baseline approach is an exhaustive search of the versions as described in section 3.3. We have tested the baseline approach in order to estimate the time needed to find the first versions; however, no version was found because timeout exceptions occurred for queries sent to the Web server.

We have empirically estimated the performances of the baseline approach in table 2. The number of queries sent to the source by the baseline approach is 2 n , with n the number of considered properties of a class. We have estimated the execution time of the baseline approach as follows: as the DBpedia data source can test a maximum of 15 queries per second [START_REF] Lehmann | DBpedia-a largescale, multilingual knowledge base extracted from wikipedia[END_REF], the best estimated time for processing 2 n queries, is 2 n /15 seconds ≈ 2 n-4 seconds.

The results in table 2 show that the baseline approach is unrealistic even without restrictions of the Web server. Finding versions of these classes using the baseline approach takes more than a billion times the age of the universe. However, SchemaDecrypt(++) succeeds in discovering the different versions of the classes. The justification for these results in the field of cryptanalysis is simple: the baseline approach is a brute force attack that makes an exhaustive search for versions of a class; while SchemaDecrypt(++) is a probabilistic attack guided by the class profile, that allows to test the most probable versions first and therefore quickly reach the stopping criteria, in addition to the rules between the properties that can reduce the search space.

The execution time of SchemaDecrypt + + is always less than the execution time of SchemaDecrypt. The difference between the two execution times is even greater when the execution time of SchemaDecrypt is important, as for the class Mountain with an execution time of 39.8 hours for SchemaDecrypt and an execution time of 14 minutes for SchemaDecrypt + +, which is 160 times less important; a similar result can be observed for the class Historian with an execution time of 6.85 hours for SchemaDecrypt and an execution time of 4.65 minutes for SchemaDecrypt + +, which is 88 times less important. When the processing time of SchemaDecrypt is of the order of a few seconds, the difference between the processing time with SchemaDecrypt + + is not very visible, however, the processing time with SchemaDecrypt + + remains always lower.

The number of candidate versions generated by SchemaDecrypt + + is always less than the number of candidate versions generated by SchemaDecrypt. For example, for the class Historian, SchemaDecrypt + + generates 409 candidate versions to validate 84 versions, while SchemaDecrypt generates 48 times more, (19738 candidate versions) to find the same result.

The number of exclusion rules can significantly speed up the execution of SchemaDecrypt + +, especially for the class Historian. This is because the higher the number of exclusion rules between the properties of a class, the higher the number of generated version templates. Exploring parallel version templates not only speeds up the process, but also reduces the number of candidate versions, because for each version template, the first generated versions are the most probable ones. Table 3 shows the usefulness of versions for identifying relevant sources for a set of queries. To query 3 sources without versions, the user has always to send a query for each source, which results in 3 queries sent in total. Versions allow to identify relevant sources for a given query as follows:

• for the query Q 1 , the versions show that unlike S1 and S2, the source S3 has no version which contains the property ----------------→ yearOf Construction. Therefore, the source S3 is not relevant for the query Q 1 , and only S1 and S2 will be queried (2 queries sent);

• for the query Q 2 , there is no version in the three sources where the properties --------→ f loorCount and -------------→ architecturalStyle occur together. Therefore, it is useless to query these sources (0 queries sent);

• for the query Q 3 , the sources S1 and S3 contain versions with the property ------→ architect without the property --------→ f loorCount. However, in source S2, there are versions where these two properties occur together. Therefore, a query is sent to S2 only (1 query sent);

• for the query Q 4 , source S1 contains versions with -------------→ architecturalStyle without the property ------→ architect, while source S2 contains versions with the property ------→ architect without the property -------------→ architecturalStyle. Source S3 contains versions with these two properties. Therefore, a query is sent to S3 only (1 query sent);

• for the query Q 5 , the three sources contain versions with the properties -------------→ architecturalStyle and -----→ location, therefore all three are queried (3 queries sent).

The size of the returned result is the same with or without the use of the versions, which shows that the versions are useful for identifying the relevant sources.

Related Work

Proposed approaches for discovering structural versions of a data source are provided for local Json data sources [START_REF] Ruiz | Inferring versioned schemas from NoSQL databases and its applications[END_REF][START_REF] Baazizi | Schema inference for massive JSON datasets[END_REF][START_REF] Baazizi | Parametric schema inference for massive JSON datasets[END_REF], local RDF data sources [START_REF] Zneika | Rdf graph summarization based on approximate patterns[END_REF][START_REF] Zneika | Summarizing linked data RDF graphs using approximate graph pattern mining[END_REF][START_REF] Čebirić | Query-oriented summarization of rdf graphs[END_REF][START_REF] Arenas | A principled approach to bridging the gap between graph data and their schemas[END_REF], streamed RDF data [START_REF] Belghaouti | Fregrapad: Frequent rdf graph patterns detection for semantic data streams[END_REF] or distributed RDF data sources [START_REF] Konrath | Schemex: efficient construction of a data catalogue by stream-based indexing of linked data[END_REF]. Unlike our approach, all of these approaches only consider the outgoing properties of the instances. In addition, they require browsing the data to find the structural versions, making their use impossible on remote data sources. Some of these structural version discovery approaches [START_REF] Baazizi | Schema inference for massive JSON datasets[END_REF][START_REF] Baazizi | Parametric schema inference for massive JSON datasets[END_REF][START_REF] Zneika | Rdf graph summarization based on approximate patterns[END_REF][START_REF] Zneika | Summarizing linked data RDF graphs using approximate graph pattern mining[END_REF][START_REF] Čebirić | Query-oriented summarization of rdf graphs[END_REF]] provide approximate versions. Unlike an exact version, in an approximate version, the co-occurrence of some optional properties is not specified. In the approach proposed in [START_REF] Baazizi | Schema inference for massive JSON datasets[END_REF][START_REF] Baazizi | Parametric schema inference for massive JSON datasets[END_REF], the optional properties of a version are identified, whereas the approach proposed in [START_REF] Čebirić | Query-oriented summarization of rdf graphs[END_REF] does not identify them; the approaches proposed in [START_REF] Zneika | Rdf graph summarization based on approximate patterns[END_REF][START_REF] Zneika | Summarizing linked data RDF graphs using approximate graph pattern mining[END_REF], do not consider the optional properties as part of the description of a version.

Unlike SchemaDecrypt(++), most of these approaches require the use of powerful machines [START_REF] Ruiz | Inferring versioned schemas from NoSQL databases and its applications[END_REF][START_REF] Konrath | Schemex: efficient construction of a data catalogue by stream-based indexing of linked data[END_REF][START_REF] Baazizi | Schema inference for massive JSON datasets[END_REF][START_REF] Baazizi | Parametric schema inference for massive JSON datasets[END_REF][START_REF] Zneika | Rdf graph summarization based on approximate patterns[END_REF][START_REF] Zneika | Summarizing linked data RDF graphs using approximate graph pattern mining[END_REF][START_REF] Arenas | A principled approach to bridging the gap between graph data and their schemas[END_REF] and big data technology [START_REF] Ruiz | Inferring versioned schemas from NoSQL databases and its applications[END_REF][START_REF] Baazizi | Schema inference for massive JSON datasets[END_REF][START_REF] Baazizi | Parametric schema inference for massive JSON datasets[END_REF]. The approach proposed in [START_REF] Zneika | Rdf graph summarization based on approximate patterns[END_REF][START_REF] Zneika | Summarizing linked data RDF graphs using approximate graph pattern mining[END_REF] discovers the top-K approximate patterns of an RDF graph by applying a pattern mining algorithm (PaNDa+ [START_REF] Lucchese | A unifying framework for mining approximate top-k) binary patterns[END_REF]). It builds a binary matrix of size N x M , where N is the number of instances of the data source and M represents the number of properties and types if defined. The size of this matrix is very large and it even exceeds the size of the data source, which requires a large memory capacity, which is not the case for SchemaDecrypt(++). Indeed, our approach uses the memory optimally: (i) data are not loaded in memory; (ii) the exploration graph of the candidate versions is not generated in memory; (iii) the current candidate versions as well as the simulation of the exploration of all the search space of the versions are represented through a "version code" on a few bits. The work presented in [START_REF] Arenas | A principled approach to bridging the gap between graph data and their schemas[END_REF] discovers the co-occurrence of properties of the same class to refine the classes. A class is refined by dividing its instances according to their structure. The resulting refined classes, provided by a solver, improve the structural homogeneity; this discovery process is equivalent to finding class versions.

The work in [START_REF] Levandoski | RDF data-centric storage[END_REF] uses association rule mining to discover properties that are frequently defined together. However, the minimum support parameter is explicitly specified by the user, whereas our approach does not require such parameter. Besides, the association rule mining algorithm is not adapted for large data sources. SchemaDecrypt(++) could be applied to reduce the size of the data source before applying association rule mining algorithm. Indeed, the class versions and their number of occurrences provide the information enabling to find frequent item-sets and to generate association rules between the properties of a class.

Different pattern mining algorithms such as FP-Growth [START_REF] Han | Mining frequent patterns without candidate generation: A frequent-pattern tree approach[END_REF], GSP [START_REF] Srikant | Mining sequential patterns: Generalizations and performance improvements[END_REF], SPADE [START_REF] Zaki | SPADE: an efficient algorithm for mining frequent sequences[END_REF], could be used to discover versions. However, all these algorithms require browsing the data source and often several times, which does not allow processing a remote data source with restricted access.

The existing structural version discovery approaches [START_REF] Ruiz | Inferring versioned schemas from NoSQL databases and its applications[END_REF][START_REF] Belghaouti | Fregrapad: Frequent rdf graph patterns detection for semantic data streams[END_REF][START_REF] Konrath | Schemex: efficient construction of a data catalogue by stream-based indexing of linked data[END_REF][START_REF] Baazizi | Schema inference for massive JSON datasets[END_REF][START_REF] Baazizi | Parametric schema inference for massive JSON datasets[END_REF][START_REF] Zneika | Rdf graph summarization based on approximate patterns[END_REF][START_REF] Zneika | Summarizing linked data RDF graphs using approximate graph pattern mining[END_REF][START_REF] Čebirić | Query-oriented summarization of rdf graphs[END_REF][START_REF] Arenas | A principled approach to bridging the gap between graph data and their schemas[END_REF][START_REF] Levandoski | RDF data-centric storage[END_REF] can not process a remote data source because they require data browsing; our approach SchemaDecrypt(++) is able to discover the class versions of a remote data source without having to load it locally. The difficulty of this task lies essentially in the fact that we can not browse the data, the only access is performed using queries. In addition to access restrictions implemented by the server such as timeout on the execution of a query and the limitation of the number of queries sent to avoid clogging the network. Some works on summarization are presented in [START_REF] Cebiric | Summarizing semantic graphs: a survey[END_REF]. However, these works are not all interested in discovering versions and above all they do not allow processing a remote source with restricted access. ABSTAT [START_REF] Spahiu | ABSTAT: ontology-driven linked data summaries with pattern minimalization[END_REF][START_REF] Principe | ABSTAT 1.0: Compute, manage and share semantic profiles of RDF knowledge graphs[END_REF] summarizes a dataset exploiting an ontology and the triples of the dataset . It provides a minimal set of patterns for describing RDF data. For each triple (x P y) in the dataset, patterns of the form (C, P , D) are generated, where C is in the minimal type set of x and D is in the minimal type set of y. Note that C is in the minimal type set of x if it is not a super-type of another type of x. Unlike SchemaDecrypt(++), ABSTAT aims to discover patterns having a form which differs from our versions, and it could not process a remote data source with access restriction as it requires browsing the data.

In [START_REF] Song | Mining summaries for knowledge graph search[END_REF], the goal is to discover the k patterns which maximize an informativeness measure. The algorithm takes as input an integer distance, which will be used to control the neighborhood in which we will look for similar entities, and a bound k as the maximum number of the desired patterns. Unlike SchemaDecrypt(++), the patterns provided by this approach [START_REF] Song | Mining summaries for knowledge graph search[END_REF] represent the approximate possible versions for sets of entities grouped according to their similarities and not necessarily representing the same class. This method also does not allow processing a remote data source with restricted access since it requires browsing the data.

T. Zeimetz et R. Schenkel analyze in [START_REF] Zeimetz | Analyzing online schema extraction approaches for linked data knowledge bases[END_REF] some online approaches that provide a general overview of a schema, such as: LODeX [START_REF] Benedetti | Lodex: A tool for visual querying linked open data[END_REF][START_REF] Benedetti | Exposing the underlying schema of LOD sources[END_REF], ViziQuer [START_REF] Zviedris | Viziquer: A tool to explore and query SPARQL endpoints[END_REF] and LD-VOWL [START_REF] Weise | LD-VOWL: extracting and visualizing schema information for linked data endpoints[END_REF]. LODeX [START_REF] Benedetti | Lodex: A tool for visual querying linked open data[END_REF][START_REF] Benedetti | Exposing the underlying schema of LOD sources[END_REF] extracts a set of indices containing representative information about a data source. Then, the schema is generated offline by using only the previous extracted indices. A schema shows the classes and the properties involving these classes. However, LODeX might infer missing or additional links between classes and it does not work on large endpoints such as DBpedia. ViziQuer [START_REF] Zviedris | Viziquer: A tool to explore and query SPARQL endpoints[END_REF] deals with visual query languages at schema level. It does not describe how the schema is extracted as the focus is on the exploration and querying a part of knowledge base. In addition, the server must not have a limit on the answer size. LD-VOWL [START_REF] Weise | LD-VOWL: extracting and visualizing schema information for linked data endpoints[END_REF] discovers an approximate schema con-sidering the most used information. It extracts the top k classes of a knowledge base, then connects them using properties. However, weak servers or servers with large amounts of data are quickly brought to their limits, as the approach uses costly operators such as ORDER BY. Unlike SchemaDecrypt(++), these approaches do not discover class versions and often face restrictions imposed by the data source. Indeed, LODex [START_REF] Benedetti | Lodex: A tool for visual querying linked open data[END_REF][START_REF] Benedetti | Exposing the underlying schema of LOD sources[END_REF] can not handle a large data source such as DBpedia; in ViziQuer [START_REF] Zviedris | Viziquer: A tool to explore and query SPARQL endpoints[END_REF], the server must not have a limit on the answer size; and in LD-VOWL [START_REF] Weise | LD-VOWL: extracting and visualizing schema information for linked data endpoints[END_REF] some of these queries can not be executed due to the restrictions imposed by the source.

Our work can also be positioned in the broader context of inductive methods for acquiring or refining schema-level knowledge for semi-structured data. Indeed, SchemaDecrypt(++) could complement the existing approaches for schema discovery, such as [START_REF] Kellou-Menouer | Schema discovery in RDF data sources[END_REF][START_REF] Christodoulou | Structure inference for linked data sources using clustering[END_REF][START_REF] Völker | Statistical schema induction[END_REF] which discover the classes of a data source but not their different versions. Each version of a class may have a specific meaning which differs from the others versions of the class. This meaning could be captured using annotations techniques as proposed in [START_REF] Kellou-Menouer | Class annotation using linked open data[END_REF].

Conclusion

We have proposed SchemaDecrypt, the first on-line approach for discovering the versioned schema of a large remote data source, without having to upload or browse the data. To find the different versions of a class, we propose to build a probabilistic class profile to guide the exploration of the candidate versions. We reduce the number of candidate versions by discovering inclusion and exclusion rules between the properties of a class.

We have also proposed a parallel exploration of versions with the approach SchemaDecrypt + + which significantly improves the performances of version discovery. Indeed, the presence of exclusion rules allows to build version templates that can be explored in parallel. A version template must conform to the exclusion rules, and contain the properties of the class, so that there are no exclusion rules that imply them. Parallel exploration of versions with SchemaDecrypt + + greatly optimizes the number of candidate versions by exploring the most probable candidate versions first in each version template.

We have presented some evaluations on the DBpedia data source, accessed through a SPARQL endPoint. As a result, the exact class versions are provided. The good performances of SchemaDecrypt(++) show that it is a powerful tool for understanding the hidden structure of Web data. The experimentation also shows that SchemaDecrypt + + is always faster than SchemaDecrypt.

Note that our approach could also be used for a remote data source without access restrictions. Indeed, reducing the number of properties in a query not only avoids the timeout server exception but also significantly reduces the time required to answer a query. The jumps during the exploration and the pruning of the exploration graph not only reduce the number of queries sent to the server so that we do not lose the processing priority, but also reduce the time required to discover the class versions. Exploring parallel version templates not only speeds up the processing time considerably, but also allows to retrieve versions of a class by testing fewer candidate versions, because in each version template, the first versions generated are the most probable ones.

The discovered versions could be used for different tasks, such as decomposing a query into sub-queries and building an execution plan on distributed data sources. Indeed, the versions describe not only the number of occurrence of a property but also the co-occurrence between the properties. Unlike a schema, versions allow to describe the different structures of instances of the same class. Another interesting problem is to evaluate the gap between a data source and its versioned schema.

Figure 1 :

 1 Figure 1: On-line Access to Remote Data Sources.

Figure 1

 1 Figure 1 shows an example of user who wants to find the different descriptions of a museum in three remote data sources on the Web (S1, S2 and S3).Several descriptions might be found in each source. We assume that the search is performed using a desktop computer with limited computing power and that there is a limited time to answer the user's query. In the context of a remote data source on the Web, the user can not browse the data; his only access is through queries to the Web server that manages the data source.

Figure 2 :

 2 Figure 2: Example of a Versioned Schema for a Semantic Data Source.

3 .

 3 The set of properties of a class specified in the schema. In the data source, a property p is declared for the class c by these specific triples: (p rdf s:domain c) or (p rdf s:range c). In addition to the properties declared for a class c, an instance of this class may be described by the properties declared for the super-classes or the sub-classes of c. Indeed, the classes of a data source are organized in a hierarchy, as it is shown in the example of Figure3, extracted from DBpedia, which represents the hierarchy containing the class Museum. An instance e of the class ArchitecturalStructure in Figure3could be described by the property ← ---------touristicSite defined for the class Place.

Figure 3 :

 3 Figure 3: The Class Hierarchy of the Class Museum in DBpedia.

Figure 4 :

 4 Figure 4: Exhaustive Search of the Versions of the Class Museum.

7 add p j to E i ; 8 else 9 create

 789 subSet of properties E i with p i and p j ;

Algorithm 2 :

 2 Dynamic Generation of Candidate Versions Input : The class profile CP , the reduced set of properties E, the set of rules R Output: The set of validated versions V with the number of occurrences of each version 1 version code = 2 |E| -1; 2 Order the set E from the most probable property to the least probable; 3 while (E = ∅) do 4 Build candidate version v i from E formed by the properties with bit(p j ) = 1 in the version code; 5 if (∀r ∈ R: v i complies with r) then 6

  if (the size of E has changed) then version code = 2 |E| ; Order the set E from the most probable property to the least probable; end end end version code = version code -1; else version code = version code -Jump(version code, E, R); end 25 end Algorithm 3: UpdateClassProfile Input : The class profile CP , a validated version v Output: Updated CP 1 for ∀p ∈ v do 2 Let α the probability of p in CP ;

3

 3

Figure 5 :

 5 Figure 5: A Jump in version code.

Figure 6 :

 6 Figure 6: Example of Exploiting Several Rules.

Figure 7 :

 7 Figure 7: The Optimal Exploitation of Several Rules.

Figure 8 :

 8 Figure 8: Generation of Version Templates from F Guided by an Exclusion Rule.

Figure 9 :

 9 Figure 9: Exploiting an Exclusion Rule having a Mandatory Property.

Figure 10 :

 10 Figure 10: Example of an Exploration of a Graph of Version Templates.

Figure 11 :

 11 Figure 11: Example of a Dynamic Exploration of Version Templates with Parallelization Capability of the Data Source Limited to M axT ask = 3.

Figure 13 :

 13 Figure 13: Processing Time (a) of SchemaDecrypt + + According to: (b) the Number of Versions and Queries, (c) the Number of Inclusion and Exclusion Rules and (d) the Number of Properties of each Class.

Table 2 :

 2 The performances of the Baseline approach, SchemaDecrypt and SchemaDecrypt + +.

								Validated
	Classes	Number of candidate versions	Processing time		versions
		Baseline		Schema	Baseline		Schema
		ap-	Schema	De-	ap-	Schema	De-
		proach	Decrypt	crypt++	proach*	Decrypt	crypt++
					2 458 sec
					≈ 2 433
					years ≈	24692
			19738 ≈	409 ≈	10 129,9	sec	279 sec
	Historian		2 14,26	2 8,67	years	(6.85 h)	(4,64mn)	84
					2 458 sec
					≈ 2 433
					years ≈
			1130 ≈	121 ≈	10 129,9
	Poet		2 10,14	2 6,9	years	232 sec	26 sec	42
					2 281 sec
					≈ 2 256
					years ≈
	Restau-		1098 ≈	197 ≈	10 76,8
	rant		2 10,1	2 7,62	years	206 sec	59 sec	89
					2 281 sec
					≈ 2 256
					years ≈	585 sec
			2757 ≈	262 ≈	10 76,8	(9,75
	Museum		2 11,42	2 8,03	years	mn)	70 sec	148
					2 277 sec
					≈ 2 252
					years ≈	426 sec
	Shopping		2245 ≈	123 ≈	10 75,6	(7,1
	Mall		2 11,13	2 6,94	years	mn)	28 sec	79
					2 264 sec
					≈ 2 239
					years ≈	1828 sec	302 sec
			8004 ≈	619 ≈	10 71,7	(30,5	(5.03
	Stadium		2 12,96	2 9,27	years	mn)	mn)	234
					2 260 sec
					≈ 2 235
					years ≈	143395	844 sec
			92510 ≈	2501 ≈	10 70,5	sec	(14.06
	Mountain		2 16,49	2 11,28	years	(39.8 h)	mn)	479
					2 239 sec
					≈ 2 214
					years ≈
			396 ≈	76 ≈	10 64,2
	Park		2 8,62	2 6,24	years	80 sec	16 sec	44
	*1 year = 31 536 000 sec ≈ 2 25 sec; and 2 n = 10 n×log(2)

Table 3 :

 3 Results of querying data sources using versions.

				Total results
	Queries	Number of sent queries	size (lines)
		without versions	using versions
	Q1: What is the year of
	construction of each museum?	3	2	340
	Q2: What are the architects
	and the number of floors of
	museums by architectural style?	3	0	0
	Q3: What is the average floor
	number of museums by
	architect?	3	1	5
	Q4: What is the architectural
	style of museums by architect?	3	1	77
	Q5: What is the architectural
	style of museums by location?	3	3	223

Resource Description Framework: http://www.w3.org/RDF/

RDF Schema: http://www.w3.org/TR/rdf-schema/

Web Ontology Language: http://www.w3.org/OWL/

SPARQL Query Language: https://www.w3.org/TR/rdf-sparql-query/

VoID: https://www.w3.org/TR/void/

DBpedia Online Access: http://wiki.dbpedia.org/OnlineAccess

DBpedia Data Set 3.8: dbpedia.org

DBpedia, SPARQL endPoint : http://dbpedia.org/sparql

SchemaDecrypt(++): http://github.com/Kenza-Kellou-Menouer/SchemaDecrypt

Acknowledgments. This work was partially funded by the French National Research Agency (CAIR ANR-14-CE23-0006 project).

Algorithm 4: Dynamic generation of version templates exploration graph

Input: list of properties to combine E, the profile P c, list of validated versions version list, set of exclusion rules R, parallelizable task number for the data source M axT ask 1 version templates = {E}; setM = ∅; j = 1; N bT hread = 0; 2 while (∃α i ∈ P c: α i ! = 0 //α i the probability of a property in P c ) do

Remove from M r the properties of the rule r i ; A version template can be characterized by new inclusion and exclusion rules, in addition to those that characterize the class, because it has some mandatory properties. In what follows, we will show how these rules can be discovered in section 5.4.1, then we will present the exploitation of the rules in section 5.4.2.

SchemaDecrypt and SchemaDecrypt + + are available online 9 . We performed our experiment on November 15, 2017, with a bandwidth of 2.4 GHz, on a desktop computer: Intel (R) Xeon (R), 2.80 GHz CPU, 64 bit with 4 GB of RAM.

Results

Table 1 summarizes the description of the classes according to their number of properties, the number of discovered inclusion and exclusion rules and the number of versions. The number of properties of each class is very high: from 243 for the class Park to 462 for the classes Historian and Poet. Figure 13 represents the performances of SchemaDecrypt + + in terms of processing time and the number of candidate versions tested by a query, according to the number of properties of a class, the number of rules discovered and the number of validated versions that represent the actual versions of a class.

SchemaDecrypt + + allows to discover the different versions of a class even when the number of properties is very high, such as for the class Historian which has 462 properties. As Figure 13 (a) shows, SchemaDecrypt + + succeeds in discovering the different versions of the class in few minutes. This result is due to three main ideas in SchemaDecrypt + +: (i) using the class profile and ordering the properties according to their probabilities, which leads to testing the most probable combinations first and to converge quickly; (ii) parallelizing the exploration of the candidate versions, which accelerates the process of version discovery and (iii) exploiting the inclusion and exclusion rules to eliminate some combinations and executing jumps in the version code, which considerably reduces the search space.

The processing time to build the class profile (see Figure 13 (a)) is proportional to the number of properties of a class (see Figure 13 (d)). The processing time to discover the rules (see Figure 13 (a)) is proportional to the number of rules (see Figure 13 (c)). The processing time to discover the versions of a class (see Figure 13 (a)) is proportional to the number of queries sent to the data