M Souilah

A Boulle

A Debelle

RaDMaX: a graphical program for the determination of strain and damage profiles in irradiated crystals

RaDMaX (Radiation Damage in Materials analyzed with X-ray diffraction ) is a user-friendly graphical program that allows to determine the strain and damage depth profiles in ion-irradiated crystals. This task is achieved by fitting experimental X-ray diffraction data, recorded in symmetrical q-2q geometry, with a dynamical diffraction model parametrized with variable strain and damage profiles based on B-spline functions. The strain and damage profiles can be graphically manipulated so as to fit the calculated curve to the experimental data. Automatic fitting procedures (generalized simulated annealing and conventional least-squares) are also implemented.

Introduction

Ion beams produced by particle accelerators are used in many fields of materials science, for instance to simulate radiative environments (Thomé & Garrido, 2001), for the implantation of semiconductor materials (Elliman & Williams, 2015) or to synthesize nanostructured materials (Dhara, 2007). The collision of energetic ions with the atoms of the target material produces crystalline damage which, in the first irradiation stages, usually consists in the target atoms being displaced from their equilibrium positions and formation of Frenkel pairs (i.e. a target atom is transferred from its nominal site to an interstitial position, leaving behind a vacancy). With increasing irradiation dose, the initial point defects may further rearrange to form larger scale defects like point-defect clusters, dislocation loops or may even lead to a full amorphization of the material (Averback, 1994;Weber, 2000).

X-ray diffraction (XRD) is extremely sensitive to atomic displacements and is used to study radiation damage in single crystals since several decades (Speriosu, 1981;Zaumseil et al., 1987;Klappe & Fewster, 1994;Milita & Servidori, 1995;Boulle & Debelle, 2010;[START_REF] Rieutord | [END_REF].

From a phenomenological standpoint, despite the underlying structural complexity of irradiated materials, radiation damage gives rise to two simple distinct features when considering the coherent X-ray diffraction signal: strain, yielding a shift of the Bragg peaks, and random lattice displacements, leading to a lowering of the coherent intensity (and to the concomitant increase of diffuse scattering intensity). The strain and lattice displacements (hereinafter simply referred to as "damage") are in general inhomogeneously distributed within a subsurface region with thickness ranging from a few nanometers to several tens of microns, depending on the energy of the incident ions. Whether ion beams are used to intentionally modify the materials, or to simulate their degradation under irradiation, a detailed knowledge of the strain and damage profiles in irradiated materials is essential, as those might profoundly affect their properties. Additionally, the determination of strain and damage profiles is often also a necessary "first-step" before a more indepth analysis of the structure of irradiated materials.

Because irradiated single crystals actually resemble a simple film/substrate system the associated XRD data can be analyzed using formalisms developed for the study of epitaxial films and heterostructures [START_REF] Pietsch | High-Resolution X-ray Scattering -From Thin Films to Lateral Nanostructures[END_REF]. There are numerous, either freely available or commercial, simulation packages that have been developed to this end. One particularly popular program is Sergey Stepanov's X-ray server (http://sergey.gmca.aps.anl.gov/) which is a web-based graphical interface that allows to simulate the XRD intensity distribution in a variety of scattering geometries.

We here present a new program devoted to the analysis of radiation damage in crystals: RaDMaX (Radiation Damage in Materials analyzed with XRD). In contrast to existing solutions, RaDMaX has been developed to perform just one single task, i.e. the determination of strain and damage profiles in irradiated crystals, and to make this task as simple and fast as possible. The program is accessible to users with only little crystallographic knowledge, although the source code is open and advanced users can use it to adapt it to particular needs. Central to RaDMaX is the existence of interactive plots of the strain and damage profiles which allow the users to graphically modify the profiles and have the corresponding XRD curve computed and updated in real time. Once a roughly acceptable solution has been obtained, either graphically and/or via the import of strain/damage profiles obtained by complementary techniques, automatic procedures can be used to fit the calculated curve to experimental data, and in turn obtain the corresponding strain/damage profiles.

Features and implementation

In this section we briefly review the principles underlying the functioning of the program. Detailed mathematical information can be found in our previous publications (Boulle et al., 2003;Boulle et al., 2009, Boulle & Debelle, 2010). In RaDMaX, the determination of strain/damage profiles is achieved by fitting a computed XRD curve to experimental XRD data, and refining the strain/damage profiles until the best possible agreement is reached. The calculation of the XRD curves is performed within the framework of the dynamical theory of diffraction from distorted crystals (Takagi, 1969;Taupin, 1964) which has proven to be particularly relevant for the study of irradiated materials (Klappe & Fewster, 1994;Milita & Servidori, 1995;Boulle & Debelle, 2010), especially considering the strong diffraction from single crystals. In particular, we make use of the recursive solution to the Takagi-Taupin equations proposed by Bartels, Hornstra & Lobeek (1986).

In this approach the irradiated region is divided into N l lamellas where all structural properties (strain, damage, structure factor, etc.) are constant. Starting from the scattering at the film/substrate interface, which corresponds to the scattering from the undistorted bulk material, the total scattered amplitude is constructed iteratively by combining the amplitudes scattered and transmitted at each interface, up to the surface. The critical parameter in this approach is the number of lamellas which, for accuracy, has to be as high as possible, but not too high in order not to slow down the calculations. Guidelines for optimizing this parameter will be given in the next section.

The values of strain and damage within each lamella have to be progressively adjusted in order to match the computed curve to the experimental data. The number of lamellas being in general relatively large (typically 50-100 for both the strain and the damage profiles), this task might be particularly cumbersome and the results of an automatic fitting procedure might lead to unphysical (oscillating or discontinuous) solutions. In order to stabilize the solution, we model the strain/damage profiles with B-spline functions (Boulle et al., 2003):

e( z )= ∑ i=1 N w e w i e B i ,3 ( z) (1a) DW ( z )= ∑ i =1 N w DW w i DW B i ,3 ( z ) (1b)
where e(z) and DW(z) are the strain and damage as a function of the depth below the surface, z.

B i,3 (z) is the B-spline basis function of third degree and w i e (w i DW ) is the weight given to each basis function in the strain (damage) profile. N w e (N w DW ) is the total number of basis functions used for the strain (damage) profile. Typical values for N w e and N w DW are comprised between 5 and 15.

Guidelines for optimizing these parameters will be given in the next section. The static Debye-Waller (DW) factor is commonly used as a measure of lattice damage (Speriosu, 1981). The DW factor lowers the amplitude scattered from each lamella and is bounded between 1 (perfect crystal) and 0 (fully damaged crystal) (Boulle et al., 2005):

DW ( z )=⟨ exp [i Qu ( z )]⟩ (2)
where u(z) is the lattice displacement at depth z, Q is the scattering vector and the angular brackets indicate a spatial averaging over the random lattice displacements in the corresponding lamella.

From the above, it can be seen that the determination of 2N l (~100-200) values of strain and damage is reduced to the determination of N w e + N w DW (~10-30) B-spline weights. With the RaDMAX program, these parameters are determined by fitting the calculated curve to the observed data using either the classical Levenberg-Marquardt least-squares fitting algorithms (local optimization, fast)

or a generalized simulated annealing, GSA, algorithm (global optimization, slow) (Boulle & Debelle, 2010). Guess strain/damage profiles can be imported from complementary measurements and manually optimized through the graphical interface before the fitting procedure.

The RaDMaX program is written using the Python programming language (www.python.org) and the graphical user interface has been developed with the wxPython toolkit (www.wxpython.org).

The NumPy library (www.numpy.org) has been used to benefit from vector programming capabilities and hence increased computing performances (van de Walt, 2011). The SciPy library (www.scipy.org) provided advanced numerical and mathematical functions like random number generation, interpolation, fast convolution algorithms and least-squares fitting algorithms (Oliphant, 2007). Finally, the Matplotlib plotting library (www.matplotlib.org) has been used for all plots in the interface. With the present implementation the computation of a typical XRD curve is performed in a few tens of milliseconds.

Program description and usage

Screenshots of the graphical user interface of the RaDMaX program are displayed in Fig. 1 and Fig.

2

. In this section we provide details on each element of the interface and give guidelines for an optimal usage of the program.

The File menu

This menu is the necessary first step in the use of the program as it allows to load experimental XRD data. The data should be provided as a two-columns (2q, intensity) ASCII file in space-(or tab-) separated format. The 2q values have to be equally spaced (constant step). For the moment RaDMaX can only handle data recorded in symmetric coplanar geometry (i.e. the conventional q-2q scan), as this is the most commonly used geometry in the analysis of irradiated materials.

Additional entries in the File menu allow to import strain/damage depth profiles. Similarly to the XRD data, these profiles should be provided as a two-columns ASCII file with the depth below the surface (in Angstroms) as the first column. These profiles are automatically fitted with Eq. 1 and the corresponding B-spline weights are extracted from the fit (and stored in *.txt files when the session is saved). The corresponding curves are then displayed in the corresponding window. The two last entries in the menu allow to save a session, or to load a previously saved session. Saving a session results in writing all necessary parameters in a text file (*.ini) that can be manually modified if needed.

Main window

The main window is separated in four distinct sections: experiment (Fig. 1a), material (Fig. 1b), strain/damage (Fig. 1c) and plot (Fig. 1d) sections.

The experiment section gathers all informations regarding the XRD measurement: the X-ray wavelength (in Angstroms), the width (full-width at half-maximum, in 2q degrees) and shape (between 0 and 1) of the resolution function of the diffractometer and the background noise (normalized to the maximum intensity). The resolution function of the diffractometer is an essential aspect of the fitting procedure as it affects the width and shape of all features of the diffraction curve (the interference fringes as well as the Bragg peak from the virgin region of the crystal). The width and shape of the resolution function can be determined by the measurement of a virgin sample. The background noise is usually low and depends on the type of detector and optics used.

Because the angular range spanned by the data is in general relatively narrow, the background noise is assumed to be a constant that is added to the calculated profile.

The material section contains all information related to the nature and structure of the material, as well as the Miller indices of the reflection considered. The nature of the crystal is selected from a drop-down menu that lists the existing structures. These structures are given in the form of text files, located in the "structures" folder, that contain the name of the elements and the atomic coordinates. Users can hence easily add and use their own structure files. A structure file is organized as follows, for example in the case of cubic ZrO 2 :

Zr4+ O2-#Coordinates for atom1 0.00 0.00 0.00 0.00 0.50 0.50 0.50 0.00 0.50 0.50 0. The structure factor is computed from these coordinates. The atomic scattering factors are computed according to the method of Waasmaier & Kirfel (1995), and absorption and anomalous dispersion are included in the calculation using the Brennan-Cowan database (Brennan & Cowan, 1992).

The strain/damage section allows to define and parametrize the models used to describe the strain and damage profiles. The irradiated layer can be chosen to have either an abrupt or a smooth (default option) interface with the virgin crystal. In the latter case, three B-splines weights (equal to 0 for the strain and to 1 for the damage) are added to those defined by the user, to ensure a gradual transition from the irradiated region to the underlying virgin crystal.

The number of B-splines weights, N w e and N w DW , can be defined in the corresponding fields. There is no general rule for the choice of these parameters and each case must be carefully tested. Typical values are in the 5-15 range. Lower values result in smooth curves and faster fitting, but the model might be unable to render fine details of the strain/damage profiles. Conversely, higher values are necessary to describe subtle features of the strain/damage profiles but may lead to unphysical oscillations in the fitted profiles and in increased computing times. The Min./Max. fields are the acceptable variation ranges of the B-spline weights during the GSA fitting.

The thickness of the irradiated region and number of lamellas N l (required for the computation of the XRD curve) are also defined in this section. As mentioned earlier, the number of lamellas has a crucial influence on both the computing time and the accuracy of the computed curve. A simple rule to determine this parameter is, starting from a relatively low value, to progressively increase its value so as to remove all spurious oscillations in the computed curve, especially in the low intensity regions. The smallest value of N l yielding a flawless curve corresponds to the best accuracy/speed compromise. Typical values are in the 50-100 range and should be multiples of both N w e and N w DW .

In the plot section are represented the strain and damage depth profiles and the corresponding computed XRD curve superimposed on the experimental data. The strain/damage profiles are either plotted with default values of the B-spline weights (= 1), or using the values imported from guess strain/damage profiles. The strain/damage profiles are interactive in the sense that the user can modify their shape by locally dragging the curve via control points represented as circles in the plots (this action actually corresponds to changing the B-spline weights defined earlier). The overall curve can be scaled up or down by pressing the "u" key and using the mouse wheel. The corresponding XRD curve is updated in real time for an easy evaluation of the quality of the simulation. This step allows to adjust the guess strain/profile before moving to the automatic fitting procedure.

Fitting window

In this window (Fig. 2), it is possible to select the fitting algorithm (either GSA or Levenberg-Marquardt). GSA should be used only when the guess strain/damage profiles fail to approximately describe the XRD data, or when there are no guess profiles. GSA is a global search algorithm which randomly explores the parameters space and is therefore relatively slow as compared to local optimization algorithms. On the other hand, the conventional least-squares algorithm is fast but requires a rather good estimation of the starting strain/damage profiles to be refined. In this latter case, it must be borne in mind that the resulting fitted profiles may exhibit unphysical values, as for instance, DW larger than unity. When using GSA, the parameters are constrained to lie in the range defined in the previous window (a feature not implemented in the Levenberg-Marquardt algorithm we use). Both algorithms can be used successively to progressively refine the solution.

The parameters described below are only relevant to the GSA algorithm. Within this algorithm, the parameters perform random jumps in the parameters space (bounded by the Min./Max. values provided by the user). The length of the jumps is parametrized by an artificial temperature which is progressively lowered during the procedure. High temperatures (~ 1000) correspond to high "thermal motion" and long jumps are possible. Conversely, at low temperature (~ 1) the system is almost frozen and the parameters can only performed short jumps, which actually corresponds to a local search mechanism. The temperature is decreased in (cooling) steps to ensure that at each temperature, the parameters have been sufficiently varied. The algorithm stops when the predefined number of cycles is reached. Alternatively, the fit can be aborted at any moment by the user. The additional parameters (q a , q v and q T ) allow to modify the behavior of the GSA algorithm. The default values ensure an optimal functioning of the algorithm. Further details regarding this algorithm can be found in Boulle & Debelle (2010).

After each fitting cycle the calculated XRD curve and the corresponding strain and damage depth profiles are stored in ASCII files located in the same folder as the XRD data. The quality of the fit, measured using the residual error [equation ( 2) in Boulle & Debelle (2010)], is provided at the end of each fitting cycle.

Comments and examples

The main idea behind RaDMaX is to overcome the "phase problem" which originates from the fact that lattice displacements affect the phase of the diffracted amplitude, whereas the quantity measured in practice is the intensity (where the phase is lost). Nonetheless, the phase shifts induced by lattice displacements give rise to interference features from which the displacement profiles can be retrieved. An important consequence is that only XRD data with visible interference fringes can be used to reliably determine the strain/damage profiles.

In all the cases we investigated these last years (Boulle & Debelle, 2010;Debelle, Channagiri et al., 2014;Debelle, Boulle et al., 2014), the strain profiles were found to be extremely robust against sample alignment errors or sample quality: slightly misaligned samples, or even polycrystalline materials were found to give reliable and reproducible results regarding the strain profile (provided that a good fit could be obtained). On the contrary, the damage profiles were found to be extremely sensitive to sample alignment or sample quality. Any deviation of the diffracted intensity from its nominal value (due to a tilt of the crystal, or to crystals with finite lateral dimensions and irregular shapes) leads to unphysical values of the DW factor (i.e. DW >1).

Finally, in order to keep the computing time as low as possible, the convolution of the intrinsic diffraction profile with the resolution function is performed using a fast convolution algorithm. For optimal results, the data should be sampled in such a way that in the narrowest feature before convolution (in general the diffraction peak emanating from the virgin crystal) there should be at least three data points above the half-maximum to describe the peak shape. In general this condition is easily fulfilled except in the case of relatively light elements (such as in SiC for instance), where special care should be brought to data sampling. A too weak sampling rate will mainly results in a wrong DW profile.

In the last five years, the approach implemented in RaDMaX has been applied to several cases, and examples can be found in our previous publications (Boulle & Debelle, 2010;Debelle, Channagiri et al., 2014;Debelle, Boulle et al., 2014). Fig. 1 and Fig. 3 show the examples of 300 keV Csirradiated yttria stabilized zirconia (YSZ, with ion fluence = 3.75×10 13 ions /cm 2 ) and 100 keV Feirradiated cubic silicon carbide (3C-SiC, with ion fluence = 4×10 13 ions /cm 2 ). In both cases, the fits are close to perfect. All the associated parameters are given in the figures and the corresponding files can be found in the "examples" folder of the program. The case of YSZ is fairly simple and 6 B-spline functions, for both the strain and damage profiles, were sufficient to achieve a perfect fit.

The data has been recorded on a high-resolution laboratory diffractometer. The irradiated region extends over 200 nm with a maximum strain of 0.55% located around 50 nm below the surface, the profile being relatively flat between 15 and 80 nm. The damage is relatively weak with a DW factor of ~0.8 in the entire irradiated region. The case of 3C-SiC is more complicated, partly because of the very low intensity emanating from the irradiated region (10 4 weaker than the main Bragg peak); this data has been recorded at the BM2 beamline at the ESRF (Grenoble, France). Up to 15 splines were necessary here, especially to correctly describe the low strain region (i.e. the intensity close to the main Bragg peak). The strain profile appears more peaked than YSZ (with a maximum of 1.15% around 30 nm). Additionally, the region extending 80 nm below the surface is heavily damaged, with a very low DW factor of 0.1.

Finally, it is worth mentioning that since irradiated single crystals resemble simple film/substrate systems, the present program can be straightforwardly adapted to study irradiated (or even only defective) films grown on substrates. It is also possible to consider its adaptation for the analysis of irradiated multilayers. In this case, however, special care has to be taken to correctly take into account irradiation-induced roughening and intermixing that may occur at interfaces as these features are not implemented for the moment. Regarding this last point, we recall that the source

Fig. 1 .

 1 Fig. 1. Screenshot of RaDMaX running in Kubuntu 15.04. The simulation corresponds to irradiated yttria -stabilized zirconia.

Fig. 2 .

 2 Fig. 2. Screenshot of the fitting window.

Fig. 3 .

 3 Fig. 3. Screenshot of RaDMaX running in Windows 10. The simulation corresponds to irradiated silicon carbide.

code is available and users may adapt it to fit their particular needs.

Availability and installation

The program is distributed under the CeCILL license, a French license similar to and compatible with the General Public License. The program can be downloaded from the GitHub code hosting website: http://aboulle.github.io/RaDMaX.

RaDMaX has been successfully tested on Windows 7 and Windows 10, and different Linux distributions (Debian 8 and Ubuntu 15.04). RaDMaX requires the following programs to be installed on the computer: python 2.7, SciPy, MatPlotLib and wxPython.


Behrang Moradi
email: behrang.moradi@mines-ales.fr

Nicolas Daclin
email: nicolas.daclin@mines-ales.fr

Vincent Chapurlat
email: vincent.chapurlat@mines-ales.fr

Formalization and Evaluation of Non-functional Requirements: Application to Resilience

Keywords: System of systems engineering, Resilience, Non-functional property, "-ilities"

This paper introduces the development of a method for the specification, formalization and evaluation of resilience. The developed method is based on two working approaches. First, we study and analyze several resilience metrics and indicators as well as the relationship between resilience and other non-functional requirements namely "-ilities". Concepts for evaluation are identified and defined. Further, we map out these "-ilities" by positioning them according to the dynamic of the resilience represented as a set of zones. A set of indicators to evaluate the resilience and particularly indicators that are associated with these "-ilities" to each zone of the resilience has to be selected. The expected benefit of such method is to allow to evaluate resilience in order to master and improve it.

Introduction

To fulfil its mission adequately, a collaborative system must satisfy functional and non-functional requirements. Among the non-functional requirements a set is called "ilities" [START_REF]Advanced automation technologies and their applications -Part 1 : Framework for enterprise interoperability[END_REF] and represents "the desired properties of systems, […] that often manifest themselves after a system has been put to its initial use" [START_REF] De Weck | Investigating Relationships and Semantic Sets amongst System Lifecycle Properties ( Ilities )[END_REF]. For instance, let's mention the Flexibility, Robustness, Safety, Interoperability or Survivability. Figure 1 presents the network of "-ilities" correlations and their relationships as defined in [START_REF] De Weck | Investigating Relationships and Semantic Sets amongst System Lifecycle Properties ( Ilities )[END_REF]. The work proposed attempts to study and analyze "-ilities" as a whole rather than to study an "-ility" in isolation and focuses on the resilience assessment. Resilience is an important property because it must be mastered and maximized [START_REF] Chin | [END_REF] to effectively cope with disruptive events and maintain acceptable levels of services and performance (e.g. loss of an organization in a collaborative network, fire requiring the engagement and collaboration of different organization…). There exist several definitions of resilience. Generally speaking, it is defined as "the ability of the system to resist, absorb, recover or adapt to disturbances and diminish the consequences as well as to recover quickly and effectively" [START_REF] Haimes | On the Definition of Resilience in Systems[END_REF]. Lastly, resilience is practiced in various application area e.g., critical infrastructure monitoring, security, transport [START_REF] Francis | A metric and frameworks for resilience analysis of engineered and infrastructure systems[END_REF], [START_REF] Iii | National Infrastructure Advisory Council A Framework for Establishing Critical Infrastructure Resilience Goals Final Report and Recommendations by the Council[END_REF], [START_REF] Andrews | Fault Modelling in System-of-Systems Contracts[END_REF].

Fig. 1. Correlation network of "-ilities" [2]

The research question deals with the evaluation of the resilience. The prevention, preparation and management of negative perturbations for the security and protection of systems have become a major concern. Indeed, a disturbance may lead to heavy loss of performance and affect a system, so that the evaluation resilience can participate to the improvement of a performance of a system. The purpose is to study the resilience with the consideration of its ecosystem that means including the possible relationships with other non-functional requirements. Currently, resilience is evaluated without considering possible impacts coming from other requirements but also possible impacts generated by resilience as well. As a consequence, the targeted objective is to develop a metric to evaluate resilience numerically and sufficiently generic to be practicable to any networked system subject to any type of disruption. The paper is structured as follows. After this brief introduction, the concept of resilience is presented as well as different methods to evaluate it. The next section presents the concepts which act as foundation for the development of our approach to analyze and evaluate resilience. The final section presents the conclusion and the future perspective for this research.

Resilience Definition and Evaluation 2.1 Definition

There are numerous definitions of resilience. Let's mention the following ones:

-"the intrinsic ability of a system to adjust its functioning prior to, during, or following changes and disturbances, so that it can sustain required operations under both expected and unexpected conditions" [START_REF] Hollnagel | Resilience engineering in practice: A guidebook[END_REF]; -"the ability to anticipate, prepare for, respond to, adapt to disruptions and to mitigate the consequences as well as to recover in timely and efficient manner including preservation restoration of services" [START_REF] Cutter | Disaster Resilience: A National Imperative[END_REF]; They all suggest that resilient systems are able to manage disastrous situation due to several capacities requested throughout the classical phases of the disaster management lifecycle: Anticipation (Preparation, Prevention), Response (Absorption, Adaptation) and Recovery (Figure 2).

Fig. 2. The classical resilience dynamic

Anticipation (Prevention and Preparedness) aims at identifying and minimizing the risks of the occurrence of an event. This zone concerns also the preparation to face up an event [START_REF]Disaster Planning: prevention, response, recovery[END_REF]. Response (Absorption and Adaptation) expresses the absorptive capability (robustness), i.e., the ability to reduce the negative impacts caused by disruptive events and minimize consequences with less efforts [START_REF] Chin | [END_REF], [START_REF] Haimes | On the Definition of Resilience in Systems[END_REF]. The adaptive capability (adaptability) refers to the ability to adapt to disruptive events through self-organization (flexibility, interoperability) to minimize consequences and it can be enhanced by using emergency systems. Recovery is defined as a return to a qualified acceptable condition. The restorative capability refers to the ability of the system to rapidly be repaired (maintainability, repairability) and return to a, as much as possible, normal and a reliable functioning mode that meets the requirements for an acceptable and desirable level of quality of service and expected control [START_REF] Chin | [END_REF].

The study and synthesis of different definitions shows that the authors believe resilience is characterized by zones such as Anticipation, Recovery and Response; each author considers more or less zones in their study (e.g. for [START_REF] Nogal | Resilience of traffic networks: From perturbation to recovery via a dynamic restricted equilibrium model[END_REF] resilience is a problem of response and recovery) (Figure 3). As part of resilience assessment, we consider the three areas of dynamic of resilience, as defined by [START_REF] Cox | Transportation security and the role of resilience: A foundation for operational metrics[END_REF].

Fig. 3. Resilience dynamic

Resilience Metric

Resilience can be assessed in different ways. It can be evaluated by measuring the performance or loss of performance of a system before and after the disruptive event, the potential loss of functionality, the loss of quality of service, the effectiveness of the security barriers, as well as the activities recovery. Numerous works related to the evaluation of the resilience are provided in the literature e.g. [START_REF] Henry | Generic metrics and quantitative approaches for system resilience as a function of time[END_REF] [15] [START_REF] Francis | A metric and frameworks for resilience analysis of engineered and infrastructure systems[END_REF] and [START_REF] Zobel | Comparative Visualization of Predicted Disaster Resilience[END_REF] that evaluates resilience with different points of view. [START_REF] Henry | Generic metrics and quantitative approaches for system resilience as a function of time[END_REF] proposes a metric of resilience that can be associated in two types such as the focus attribute parameters, which usually consist of indices based on subjective assessments and the indicators built on databases, which quantify the system attributes that contribute to resilience. The performance-based methods, which measure the consequences of system disturbances and the impact that system attributes have on mitigating these consequences. [START_REF] Francis | A metric and frameworks for resilience analysis of engineered and infrastructure systems[END_REF] states the measurement of resilience is a function of the 3 capacities (absorption, adaptation and recovery) as well as recovery time, through the measurement of the performance and its evolution. The method is based on a resilience analysis framework and a metric for measuring resilience. The analysis framework consists of system identification, resilience objective setting, vulnerability analysis, and stakeholder engagement. Lastly, [START_REF] Zobel | Comparative Visualization of Predicted Disaster Resilience[END_REF] provides a quantitative measure of resilience in the face of multiple disaster-related events. It extends the concepts of the resilience triangle and predictive resilience in disaster by considering the trade-offs between several criteria. Its work is based on sudden disasters and the initial impact of each event as well as the recovery time of the system before the next event. In this work (Figure 4), robustness is used to increase the resilience so that it recovers its performance and returns to an acceptable state. Thus, there is a link between resilience and robustness. These works show three approaches to assess resilience (Figure 5). Let's note that [START_REF] Zobel | Comparative Visualization of Predicted Disaster Resilience[END_REF] highlights the link between resilience and another "-ility" (robustness in the Zone2-response). Its measurement shows the importance of considering the link between "-ilities" since the more the robustness, the more the resilience can be efficient. However, each metric treats the resilience in isolation, i.e., they do not consider the possible relationship with other "-ilities". In this sense, stakeholders don't have any information about the possible impact of the resilience onto other "ilities" and vice versa. Thus, the ecosystem of "-ilities" and their relationship can be used and study to evaluate a given "-ility", here, the resilience.

Research Work Proposal

The assessment of resilience relies on defining and analyzing the set of "-ilities", i.e., the analysis and formalization of the relationship between resilience and other "ilities" (Figure 6). In this hypothesis, we focus on the analysis of the resilience and its environment and highlight the various components to consider to evaluate resilience. The four components considered are (in red and numbered on Figure 6): 1. The influence. It identifies which "-ilities" influence resilience. Some influences are currently identified. However, as claimed in [START_REF] De Weck | Investigating Relationships and Semantic Sets amongst System Lifecycle Properties ( Ilities )[END_REF], some might exist but are not yet identified. In order to assess resilience based on all elements, it is necessary to identify any dependence between resilience and other "-ilities".

The orientation.

It means to define if the influence is unidirectional (ex. quality → resilience) or bidirectional (ex. quality ↔ resilience). This orientation must be considered "from" resilience "to" another "-ilities" as well as "from" another "ilities" to resilience.

Dependence. It defines the intensity of the variation between two "-ilities".

For instance a high variation (positive or negative) of an "-ility" leading to a high variation (positive or negative) of the impacted "-ility" expresses a high dependence. 4. The propagation. The chain represents a relation "starting from" the resilience and returning to the resilience via another "-ilities" (resilience → safety → sustainability). In this work we consider and limit a chain to a path with 3 "-ilities". In this hypothesis, we present the "-ilities" that have links with the resilience and thus we analyze their relations based on the four components (influence, orientation, dependence, and propagation). Figure 7 shows the set of "-ilities" in relation with the resilience. Some links stem from [START_REF] De Weck | Investigating Relationships and Semantic Sets amongst System Lifecycle Properties ( Ilities )[END_REF], and some are added following the study of the "ilities" and their possible relationships. For instance, interoperability is linked with resilience, since it enables a collaborative system to collaborate coherently to achieve the desired operational effect, so the relationship with resilience -e.g. to mitigate crisis situation -is needed and important. Adaptability is an "-ility" expected in the dynamic of resilience (response zone -ability to adapt), so it has a direct link to resilience, which helps to minimize a negative impact. Then a given link must be characterized by the four components defining a relation. For instance, the sustainability influences (component 1 -influence) the resilience that means a variation of sustainability leads a variation of the resilience. Then, the direction (component 2 -orientation) of this influence is directed from sustainability to resilience, because sustainability allows the system to withstand shocks (Zone 2 -response). The force (component 3 -dependence) is defined such as the high increase of sustainability leads to a high increase of the resilience. Lastly, the propagation (component 4 -propagation) represents the chain -limited to three path -starting from the sustainability via the resilience. In this example the chain is characterized by the path sustainability -resilience -safety (with a last feedback to sustainability). Figure 8 summarizes the relation between resilience and sustainability in agreements with the four items of the first hypothesis. In this end, each relationship between resilience and other "-ilities" (which impact resilience) have to be identified and formalized. In the same way, the components, such as dependence and propagation, must formally established to allow the evaluation of the resilience (e.g. quantification or qualification of dependence and definition of effect in the propagation chain).

Fig. 7. Network of correlation of "-ilities" and resilience

Based on these first components presented, we will define resilience indicator that will measure and manage the capacity of a collaborative system to recover from an event. The indicator considers the capacity to cope with the consequences of disturbances. In addition, the indicator explains the impact of anticipation, response and recovery activities that could be taken after the disruption to reach the acceptable level of service (performance).

Fig. 8. Characterization of the relation between resilience and sustainability

Moreover, the resilience dynamic must be considered. Indeed, the aim is to know the level of resilience for each zone to implement adapted solution to improve resilience. To this purpose, "-ilities" and their influences are mapped in each zone (e.g. flexibility can be expected during the prevention, Figure .9). This positioning is relative to the analysis of resilience and "-ilities" that have identified links in each area. The objective is to get a resilience indicator for each zone. In the end, the aggregation of each indicator will provide an evaluation of the resilience. Thus, each "-ilities" related to resilience is analyzed to be re-located precisely on the corresponding phase of resilience. This analysis is mainly related to the study of the intrinsic characteristics and their understanding of a given "-ility" with regards to characteristics expected during a given phase of the resilience. It is to note that a given "-ility" can cover several phases of resilience life-cycle. For instance, robustness is interpreted as a measure of performance change. It is positioned in anticipation zone, because the effect of robustness allows the system to increase the readiness to deal with disruptive events. It is also positioned in the response zone, which makes it possible to absorb the negative effects of a disturbing event and increase the level of resilience of the system. Adaptability is the ability of a system to change to perform its basic work in uncertain or changing environments. Thus, adaptability is positioned in the response zone (figure 9), by minimizing the negative impact by protection against shocks. As last example, flexibility can be defined as the ability of a system to comply with its core mission that is not included in the definition of system requirements in disrupted or changing environments. This can be conceptualized as minimizing the consequences with less effort [START_REF] Bordoloi | Flexibility, adaptability, and efficiency in manufacturing systems[END_REF]. Thus, the flexibility is positioned on response and recovery zones. Figure 9 shows the mapping of the "-ilities" with the different resilience zones (e.g. flexibility is positioned in zone 2, zone 3 and robustness in zone 1, zone 2, zone 3). Mapping makes possible to establish the resilience indicators associated with these "-ilities" and for each zone. These indicators ultimately enable the level of resilience to be accurately identified and assessed, so aggregation of all these indicators will provide an assessment of the overall resilience.

Conclusion

The here presented work aims, in the end, to evaluate the resilience relying on the dynamic of the resilience and on its study as an "-ilities" belonging to an ecosystem of "-ilities". The purpose is to support a collective of actors -for instance involved in a collaborative network -to manage their resilience based on the knowledge of its level and to improve it. First, several resilience metrics are studied and analyzed as well as the relationship between resilience and other "-ilities". Then, the components that defines the relationship between "-ilities" are defined and "-ilities" linked to the resilience are mapped by positioning them according to its dynamic. Future work is related to the formalization of the components of relationship to get metric and to evaluate the resilience.

Fig. 4 .

 4 Fig.4. The predicted resilience triangle as a proportion of T*[START_REF] Zobel | Comparative Visualization of Predicted Disaster Resilience[END_REF]

Fig. 5 .

 5 Fig. 5. Synthesis of different resilience assessment methods

Fig. 6 .

 6 Fig. 6. Partial correlation network of "-ilities" including components for evaluation.

Fig. 9 .

 9 Fig. 9. Resilience Dynamic and "-ilities" mapping


Iovka Boneva

Jérémie Dusart

Daniel Fernández Álvarez

Jose Emilio

Labra Gayo

Semi Automatic Construction of ShEx and SHACL Schemas

Keywords: RDF validation, SHACL, ShEx, RDF data quality, LOD usability, Wikidata

We present a method for the construction of SHACL or ShEx constraints for an existing RDF dataset. It has two components that are used conjointly: an algorithm for automatic schema construction, and an interactive workflow for editing the schema. The schema construction algorithm takes as input sets of sample nodes and constructs a shape constraint for every sample set. It can be parametrized by a schema pattern that defines structural requirements for the schema to be constructed. Schema patterns are also used to feed the algorithm with relevant information about the dataset coming from a domain expert or from some ontology. The interactive workflow provides useful information about the dataset, shows validation results w.r.t. the schema under construction, and offers schema editing operations that combined with the schema construction algorithm allow to build a complex ShEx or SHACL schema.

Introduction

With the growth in volume and heterogeneity of the data available in the Linked Open Data Cloud, the interest in developing unsupervised or semi-supervised methods to make this information more accessible and easily exploitable keeps growing as well. For instance, RDF graph summarization [START_REF] Čebirić | Summarizing semantic graphs: a survey[END_REF] is an important research trend that aims at extracting compact and meaningful information from an RDF graph with a specific purpose in mind such as indexing, obtaining high level descriptions of a given dataset, graph visualization, query optimization, or extracting a schema or an ontology.

The Shapes Constraint Language (SHACL) [START_REF] Knublauch | Shapes constraint language (SHACL). W3C Candidate Recommendation, W3C[END_REF] is the W3C standard for defining constraints for RDF graphs. The Shape Expressions Schemas (ShEx) language [14] has a similar purpose but is based on a slightly different set of operators. Both proposals allow to define a set of named shapes that constrain the RDF nodes and describe their close neighbourhoods. A set of such constraints is called a schema and provides high level information about the structure and contents of an RDF dataset. Such schema is usually constructed with a particular application in mind. SHACL and ShEx schemas allow to increase RDF datasets usability, as they facilitate RDF validation, understanding and querying.

More recently, several authors have used techniques close to graph summarization in order to automatically produce a SHACL [START_REF] Potoniec | Swift linked data miner: Mining OWL 2 EL class expressions directly from on-line rdf datasets[END_REF]15,[START_REF] Melo | Automatic refinement of large-scale cross-domain knowledge graphs[END_REF] or a ShEx [START_REF] Van Dam | RDF2Graph a tool to recover, understand and validate the ontology of an RDF resource[END_REF]16,[START_REF] Gayo | RDFShape: An RDF playground based on Shapes[END_REF][START_REF] Fernández-Álvarez | Inference of Latent Shape Expressions Associated to DBpedia Ontology[END_REF] schema. Nevertheless, shapes generated using noisy or incomplete data may contain incorrect data or imprecisions. Most of the times, the shapes should be reviewed and edited by domain experts in order to ensure they fit with the application requirements. The usability of tools letting a proper edition of those schemas has been identified as a challenge [START_REF] Gayo | Challenges in RDF Validation[END_REF]. The relative youth of consolidated constraint languages for RDF data causes that this kind of tools has not been thoroughly investigated yet, but a list of desirable features has been proposed [START_REF] De Meester | Towards a uniform user interface for editing data shapes[END_REF].

Contributions

In the current paper we describe the algorithms and the software components that are necessary for the development of an integrated, highly parametrizable and well automated tool that would allow to users with different levels of expertise to construct SHACL and ShEx schemas from data. As a first contribution, we define an algorithm that takes as input a set of sample nodes from the RDF dataset and outputs a so called uniform shape constraint that uses only a restricted number of features of ShEx and SHACL. The uniform constraint can either be satisfied by all the nodes in the sample, in which case it is the unique most specific such constraint. Or it can take into account possible noise in the data and be satisfied by most sample nodes except for a small number of them consistent with a predefined error threshold. As a next contribution, we introduce schema patterns as a general mechanism for guiding and tuning our schema construction algorithm. A schema pattern can be provided as input to the algorithm, in which case the latter can output a complex shapes schema with nested constraints and references between shapes. In particular, we show how to construct a schema pattern from an existing ontology so that the automatically constructed schema contains one shape for each class in the ontology and integrates the predicates' domain and range axioms. We finally describe an interactive workflow that allows to construct an arbitrarily complex schema with the help of appropriate schema edition operators, statistical information about the data, a comprehensive visualization of validation results, and integrated calls to the algorithm for automatic schema construction.

Most of the ideas presented here are already implemented in the open source java tool ShapeDesigner available at https://gitlab.inria.fr/jdusart/shexjapp. [START_REF] Van Dam | RDF2Graph a tool to recover, understand and validate the ontology of an RDF resource[END_REF] performs structural graph summarization on knowledge bases that can be exported to RDF, OWL, XGMML or ShEx. By default, this tool associates shapes to classes, taking into account class hierarchies. However, some tuning is possible, allowing to define constraints for sets of nodes that do not belong to the same class. It is limited w.r.t. expressible cardinalities but considers incoming and outgoing links in the neighbourhood of nodes. The resulting summary can be exported to ShEx or visualized as a graphical network, but none of these options are intended to be edited or refined by the user.

Related work RDF2Graph

RDF2Graph has been used as a base to perform shape construction in Wikidata [16], using a publicly available tool 4 . This tool allows to specify an initial custom set of focus nodes to be associated with a shape. It can relate other shapes to the initial one, being those shapes constructed w.r.t nodes of the same class. It ignores triples in reified models, thus the schema of the metadata associated to a given piece of knowledge in Wikidata is missed.

In [START_REF] Fernández-Álvarez | Inference of Latent Shape Expressions Associated to DBpedia Ontology[END_REF] and [START_REF] Gayo | RDFShape: An RDF playground based on Shapes[END_REF] the same authors propose two tools for automatic generation of ShEx schemas, which can be partially translated to SHACL in [START_REF] Gayo | RDFShape: An RDF playground based on Shapes[END_REF]. The tool in [START_REF] Fernández-Álvarez | Inference of Latent Shape Expressions Associated to DBpedia Ontology[END_REF] takes as input a set of classes of a Knowledge Base (KB) and produces a ShEx shape for each one computing the immediate neighbourhood of the instances of that class. It uses statistical methods to choose the neighbourhood constraints, being able to discard the infrequent constraints and providing statistical annotations about them. The approach presented in [START_REF] Gayo | RDFShape: An RDF playground based on Shapes[END_REF] is independent of classes and the resulting constraints go beyond the immediate neighbourhood, but it is more limited w.r.t. cardinalities and less parametrizable. None of those proposals define an interaction process, and they are both less parametrizable than our method w.r.t. the structure of the schemas to be constructed.

The tool presented in [START_REF] Potoniec | Swift linked data miner: Mining OWL 2 EL class expressions directly from on-line rdf datasets[END_REF] detects sets of nodes of an RDF graph that match some patterns, then combines those patterns to construct more complex OWL 2 EL class expressions and axioms. The latter can be exported to SHACL. The node groupings used for defining a shape are not necessarily related to the same class nor selected by the user, but they are automatically detected by the mining algorithm.

ABSTAT [13] is an ontology-driven tool able to produce semantic profiles of a given Knowledge Base (KB). Those profiles gather statistics about type and cardinality of features in the immediate incoming or outgoing neighbourhood of a set of target nodes. In [15], ABSTAT's profiles are translated to SHACL shapes associated to the instances of some target class.

PaTyBRED [START_REF] Melo | Detection of relation assertion errors in knowledge graphs[END_REF] is a hybrid classifier method which relies on path and type relations for the detection of errors in KBs. In [START_REF] Melo | Automatic refinement of large-scale cross-domain knowledge graphs[END_REF], the authors train decision trees using PaTyBRED to generate SHACL constraints. The core idea is to detect examples qualified as highly erroneous, turn them into logical conditions and use their negation as a constraint.

The novelties of our approach compared to those cited above are (1) we include a strategy to integrate the user in the refinement of the automatically constructed schemas; and (2) we introduce schema patterns as an expressive parametrization mechanism. This allows to feed the schema construction algorithm with useful information coming from an ontology, or with expert knowledge.

Organisation In Sect. 2 we introduce a shapes schema language as an abstraction of ShEx and SHACL. In Sect. 3 we define uniform schemas as restriction of the language and explain the construction of the most specific and the largely accepted consensus uniform constraints. Schema patterns are defined in Sect. [START_REF] Fernández-Álvarez | Inference of Latent Shape Expressions Associated to DBpedia Ontology[END_REF] and the interactive workflow in Sect. 5. We also discuss there the current status of the implementation of the method presented in this paper. We finally conclude and discuss future work in Sect. 6. This submission is accompanied by a long version extended with two appendices.

The Shape Constraint Language

We assume that the reader is familiar with RDF and has at least some basic understanding of the SHACL and ShEx constraint languages. We start by fixing notations related to RDF graphs then present the shapes constraint language.

Denote by IRI the set of IRIs, by Lit the set of literal values, and by Blank the set of blank nodes. Recall that an RDF graph G is a set of triples in (IRI ∪ Blank) × IRI × (IRI ∪ Lit ∪ Blank). If (s, p, o) is a triple, then s is the subject, p the predicate, and o the object of the triple. A graph G will be clear from the context all along the paper. The elements of IRI ∪ Lit ∪ Blank that appear in subject or object position of some triple of G are called nodes, and the elements that appear in predicate position are called predicates or also properties. If N is a set of nodes, we define props(N ) = {p | ∃(s, p, o) ∈ G s.t. s ∈ N }, i.e. the set of properties of the nodes in N . The neighbourhood of a node n is the set of triples of G with subject n. Node n is called a p-neighbour of node n if (n, p, n ) is a triple in G. Throughout the paper we use IRI prefixes without defining them and assume that different prefixes (e.g. p: and q:) always have different definitions.

SHACL [START_REF] Knublauch | Shapes constraint language (SHACL). W3C Candidate Recommendation, W3C[END_REF] and ShEx [14] are the two main languages used for defining constraints for RDF graphs. See [START_REF] Gayo | Validating RDF Data[END_REF] for an introduction to these languages. They both use the notion of shape in order to describe or constraint the neighbourhood of nodes in RDF graphs, as illustrated in Example 1.

Example 1 (The shapes <Person> and <Date>). The shape <Person> requires 1) an rdf:type link to foaf:Person; 2) zero or more owl:sameAs links to some IRI; 3) a foaf:name link and a foaf:familyName link to string literals; and 4) a bio:birth link to a xsd:gYear or a rdgr2:dateOfBirth link to a node that satisfies shape <Date>, but not both. On the other hand, shape <Date> requires 1) an rdf:type link to time:Instant; and 2) an rdfs:label that is an integer value. This is how the constraint for shape <Person> would be written in the shapes constraint language. In Fig. 1 we provide some turtle content with a couple of nodes to be validated against the shape <Person>. :virginia conforms with <Person>, since it includes all the requested features regarding outgoing links. Shapes are open in the sense that they allow nodes to have outgoing links with predicates that are not mentioned in the shape, as for instance the property rdgr2:placeOfBirth of :virginia. :william does not conform, since the information about Williams' name is provided using schema:name instead of foaf:name and foaf:familyName. In addition, :william also violates the requirement that only one among bio:birth or rdgr2:dateOfBirth links should be present. We now introduce the abstract Schapes Constraint Language (SCL) that containing the main features of ShEx and SHACL and has a quite straightforward translation to both of them described in Appendix A of the long version. Its syntax is very similar to ShEx compact syntax. A shape constraint Constr is defined by the abstract syntax in Fig. 2 using Extended Backus-Naur Form (EBNF) where the symbol '*' denotes the repetition of an element zero or more times. We next explain the semantics of SCL. A Constr is satisfied by a node if this node and its neighbourhood satisfy both the value and the neighbourhood constraints. Each ValueConstr restricts the value of a node to be one of the options in ValueConstr, where lit denotes a literal, nonlit a non-literal, blank a blank node, iri any IRI, and any imposes no value restriction, XSD defines a required XML Schema Definition type of the value, Prefix imposes it to be an IRI with the given prefix, and ListValues enumerates the admissible values. A NeighbConstr is satisfied by a node if its neighbourhood satisfies all the conjuncts. A Choice is satisfied when just one of the TripleConstrs composing it is satisfied. A TripleConstr is to be satisfied by the triples in the neighbourhood of the node having the specified predicate. The number of such triples must fit within the cardinality bounds given by min and max, where min is a natural and max is either a natural or the special value ' * ' for unbounded cardinality. The objects of those triples should be nodes satisfying the specified ObjectConstr, which can be a simple ValueConstr or another shape. The latter is either a reference to ShapeLabel or a nested shape with {NeighbConstr}. Note finally that a NeighbConstr constrains only the triples in the neighbourhood which predicate is mentioned in one of its TripleConstr. All other predicates can be present without restriction on their object value or cardinality.

A schema is a pair S = (L, def ) where L ⊆ IRI is a finite set of shape labels and def associates with every label in L its definition which is a shape constraint. How an RDF graph should conform to a schema is defined by a validation target. A validation target for schema S = (L, def ) and graph G is a pair T = (L, tgt) where tgt associates a set of nodes of G with every shape label from L. We say that graph G satisfies schema S with target T if for any shape label L in L, all nodes in tgt(L) satisfy the constraint def (L). Most typically, a target is specified using a class from an ontology or a SPARQL query. For instance, one might want to validate all nodes with class City and population greater than 1 million people against a shape <BigCity>. In this paper we consider nonrecursive schemas only that do not allow the definition of a shape label to refer to itself neither directly nor transitively.

Automatic Construction of Uniform Constraints

Consider a fixed RDF graph G. In this section we address the problem of automatically constructing a shape constraint to be satisfied by a given sample set of nodes of G. We define uniform constraints which enjoy the nice property that for any set of sample nodes N , there exists a unique most specific uniform constraint satisfied by all the nodes in N (see Sect. 3.1). We also explain how to construct a uniform constraint satisfied by most but not necessarily all sample nodes, thus allowing to take into account noise in the sample data (see Sect. [START_REF] De Meester | Towards a uniform user interface for editing data shapes[END_REF]

.2).

A uniform constraint is defined by the syntax in Fig. 3. We additionally require that the UTripleConstrs that appear in the same UNeighbConstr are without repeated properties, i.e. their predicates are pairwise distinct. Intuitively, uniform constraints allow to enumerate the predicates to appear in the neighbourhood of a node and to specify for each predicate a constraint for its value and its cardinality among a restricted choice of four possible cardinalities. Re- mark that uniform constraints belong to the SCL language defined in Sect. 2.

Most Specific Constraint

Let F be the set of all constraints definable by ValueConstrs and let be the (partial) ordering relation over F defined by V 1 V 2 if all nodes that satisfy V 1 also satisfy V 2 . Then for any prefix pr: and for any XSD datatype X it holds pr: iri nonlit any blank nonlit X lit any Moreover, is defined for prefix constraints by p: q: if q is a prefix of p, and also for XSD datatypes, for instance int decimal. Finally, is defined for UValue constraints by [r] X if r is a literal and X is its XSD type; [r] p: if r is an IRI and p: is its longest prefix, and [r] blank if r is a blank node.

Let K be the set of uniform cardinalities, then the subset relation ⊆ on intervals defines an ordering relation over K. It is not hard to show that Lemma 1. (F, ) is an upper semilattice with least upper bound F = any. (K, ⊆) is a complete lattice with least upper bound K = {0; * } and greatest lower bound K = {1; 1}. Therefore, for any set of RDF nodes R, there exists a unique most specific uniform value constraint satisfied by all nodes in R that we denote by R. Similarly, for any set U of natural numbers, there exists a unique most specific uniform cardinality that includes U and we denote it U . Definition 1 (Most specific constraint). Let N ⊆ Nodes(G) be a sample set of nodes. The most specific constraint associated with N is the uniform constraint msc(N ) that contains exactly one TripleConstr p V C for every predicate p ∈ props(N ) whose value constraint V and cardinality C satisfy: The schema defined in Lemma 2 is the most precise schema using uniform constraints that one can construct for matching with the nodes of the sample N .

-V = N p where N p is the set of p-neighbours of N ; -C = U where U = {|(n, p, n ) ∈ G| | n ∈ N }.

It easily follows from the definition that

Largely Accepted Consensus Constraint

The largely accepted consensus constraint allows to account for potential errors in the neighbourhoods of the sample nodes. Imagine that most p-neighbours of the nodes in N have an IRI value, except for a very small number of them whose value is a literal. In this case, msc(N ) will consider any as value constraint for p, while it is also possible that the literal p-neighbours are errors in the data.

We start by presenting a decision making algorithm used in the definition of the largely accepted consensus constraint. The largely accepted consensus constraint is defined using a consensus where the voters are (some of) the nodes of the sample N . For every p ∈ props(N ), let N p ⊆ N be the set of sample nodes that have at least one p-neighbour and assume we are given:

(o) = o o |{n | π(n) = o }|.
π F,p : N p → F a vote function that gives the preferred value constraint for property p of every sample node that has a p-neighbour; π K,p : N → K a vote function that gives the preferred cardinality for property p of every sample node.

Definition 2 (Largely accepted consensus constraint). Let N ⊆ Nodes(G) be a sample set of nodes and 0 ≤ e < 0.5 be an error rate value. The largely accepted consensus constraint associated with N and assuming error rate e is the uniform constraint lac e (N ) that contains exactly one TripleConstr p V C for every predicate p ∈ props(N ) and it has value constraint V = consensus(F, , N p , π F,p , 1 -e), and cardinality

C = consensus(K, ⊆, N, π K,p , 1 -e).
The error rate value e is intuitively a bound on the proportion of sample nodes that could have expressed an incorrect5 vote due to noise in the data. It is not hard to see that lac 0 (N ) = msc(N ).

Finally we define the vote functions π F,p and π K,p . For any node n ∈ N and any p ∈ props(N ), π K,p (n) is defined as follows, where m is the number of p-neighbours of n:

π K,p (n) =      {0; 1} if m = 0 {1; 1} if m = 1 {1; * } if m > 1
As for π F,p , it is itself defined as a consensus: π F,p (n) = consensus(F, , M, best-match, 1e ) where 0 ≤ e < 0.5 is an error rate that might be different from e, the voters M = {n | (n, p, n ) ∈ G} are all p-neighbours of n, and the voting function best-match : M → F is defined by best-match(n ) = [n ] (i.e. the singleton ListValues containing n ).

Discussion The msc and lac constraints are implicitly parametrized by F that could be replaced by any upper semilattice. For instance, F = {any, blank, lit} might be sufficient for some use cases. We choose to present this particular value for F because it is useful in practice.

Schema patterns

The main limitation of uniform constraints is that they do not allow for nested neighbourhood constraints or references to other shapes. A possible alternative could be to construct a schema up to some fixed nesting depth given as parameter [16,[START_REF] Gayo | RDFShape: An RDF playground based on Shapes[END_REF] but the same nesting depth is seldom appropriate to all shapes. We propose to use schema patterns instead. They allow for a fine tuning of automatic schema # head of gov.: Len Brown pq:P580 "2010-01-01T00:00:00Z"^^xsd:dateTime ; # start time pq:P582 "2016-10-08T00:00:00Z"^^xsd:dateTime ; # end time prov:wasDerivedFrom [ pr:P143 wd:Q328 ]

# provenance ] .

Fig. 4. Extract of the Wikidata entry for Auckland

construction by describing a general form for the target schema, but can also be used simply to restrict the namespaces of predicates of interest, or to give a particular role to some values such as the value of rdf:type.

We start by a motivating example based on Wikidata that we use for an informal description of schema patterns in Sect. 4.1. Then in Sec 4.2 we give the syntax of schema patterns.

Informal Definition

Fig. 4 presents an extract of the Wikidata entry for the city of Auckland 67 . Entities in Wikidata are encoded by identifiers that start with Q, and properties by identifiers that start with P. The entry in Fig. 4 includes a statements for the property country (P17) with value New Zealand (Q664), and two statements for the property head of government (P6) with values Phil Goff (Q597909) and Len Brown (Q4116955). The most significant value of each property is given as a direct statements (ds) (prefix wdt:), while richer information is presented in a qualified wikibase:Statement in which the claim is accompanied by context or scope information (under which conditions the claim holds), as well es meta information such as provenance. Note that the structures of such statements are similar. They usually contain property statements (ps:), qualifiers (pq:) and provenance information.

In Fig. 5 is presented the msc(N ) constraint where the sample N contains the Wikidata entries for Auckland, Monterey, Vienna and Kobe poor to represent the actual structure of the data. A more appropriate schema S city for cities in Wikidata 7 is given in Fig. 6. It accounts for the possible qualifiers of the different properties.

A schema similar to S city can be automatically constructed using the schema pattern P city in Fig. 7 as input of the constraint construction algorithm. A schema pattern is similar to a schema but it omits cardinalities, it allows predicate filters (p:, iri, ps:, . . . ) instead of predicates, it replaces value constraints by placeholders or [ ], and it replaces some shape names by variables (Y ).

The pattern P city defines one non-variable shape label <City>, therefore it will be used with one set of sample nodes, say N city , in order to construct a shapes schema. Denote P city the pattern for <City> and assume that N city contains the single node wd:Q37100 from Fig. 4. We start by matching all properties q in props(N city ) with the predicate filters that appear in the P city , and every such property q is matched with the most specific possible filter. That is p:P17 and p:P6 are matched with p: and we write matched (p:) = {p:P16, p:6}, while matched (iri) = {wdt:P17, wdt:P6, rdf:type}. Now every property in matched (p:) yields a triple constraint, and the pattern requires that its object is @Y, a shape reference to a freshly created shape label. We can see that schema S city in Fig. 6 contains indeed two triple constraints p:P17 @<Y P17> and p:P6 @<Y P6>. The cardinalities of these triple constraints are not relevant here as they were obtained by considering a bigger sample set N city . In the general case, any property q ∈ matched (p:) defines its corresponding sample N q = {n | ∃n ∈ N city .(n, q, n ) ∈ G} composed of the q-neighbours of the nodes in N city . This sample is used to determine the cardinality of the triple constraint on the one hand, and as a sample for the definition of shape label <Y q> on the other hand. Similarly, every property in matched (iri) yields a triple constraint which object constraint is a value constraint, as indicated by the placeholder . Now regarding the pattern P Y for Y , we already saw that it defines two different shapes as defined by matched (p:), and each of these has its associated sample. Remark that P Y does not contain filter iri, therefore some of the properties of the sample nodes might match none of the filters. These properties will not be considered. For instance, property prop:wasDerivedFrom appears in the sample nodes in Fig. 4, but not in the schema S city . We finally explain the triple constraint rdf:type [ ] in P Y . Its predicate holder is not a filter but a property, so it will be matched only by this same property. Its object constraint is the placeholder [ ] indicating that we want to construct a ListValues constraint for the set of values. In the example this is the singleton list that contains wikibase:Statement. As we saw, schema patterns are particularly fitted for the Wikidata dataset as it strongly relies on reification. But they are also useful for all datasets that use reification [START_REF] Frey | Evaluation of Metadata Representations in RDF stores[END_REF] or repetitive local structure. Simpler schema patterns can also be used for e.g. restraining the properties of interest.

Formal Definition

Assume a countable set V sch of shape label variables ranging over X, Y, . . ..A constraint pattern (or pattern for short) is defined by the syntax in Fig. 8. A schema pattern is a triple P = (PL, pdef , sample) where:

-PL ⊆ L ∪ V sch is a finite set of shape labels and shape label variables; with every label or variable in PL, pdef associates a shape pattern that uses shape variables from PL ∩ V sch only; -sample associates a set of nodes from G with every label in PL ∩ L. A schema pattern defines a most specific uniform schema (or a largely accepted consensus schema) which definition is given in Appendix Bof the long version due to space limitations.

Patterns for Ontologies

We show here how a schema pattern can be used to encode some of the information available in an existing ontology that might be relevant for the schema construction. Consider the toy RDFSchema ontology R that defines three classes :Human, :Teacher and :Subject with :Teacher subclass of :Human, and three properties :name, :teaches, :description with axioms :name rdfs:domain :Human. :description rdfs:domain :Subject. :teaches rdfs:domain :Teacher. :teaches rdfs:range :Subject.

We can automatically retrieve the following schema pattern ] ; :description } with tgt(<Human>) defined by the SPARQL query SELECT ?x WHERE ?x a :Human. and similarly for <Teacher> and <Subject> shapes. The shapes schema constructed with this pattern will contain only the properties of the ontology vocabulary attached to their respective domains.

Interactive Improvement of the Schema

We are convinced that an optimal shapes schema, i.e. a schema that encodes correctly the requirements for a particular application, cannot be obtained by a fully automatic process. Automatically constructed schemas are necessarily simple: if we allowed the choice operator or repeated properties 8 in uniform constraints, then a unique most specific constraint would not exist. Schema patterns (or other forms of parametrization) can bring a partial solution, but they may require user expertise and good knowledge about the data, which is often the reason why we want to build a schema at the first place: a chicken-and-egg situation.

Our solution is to let the user build the schema but within the interactive workflow described hereafter that gives access to automatic schema construction and to useful information about the data, and provides appropriate feedback.

Assume an RDF graph G for which we want to build a schema. The interactive workflow maintains a schema S = (L, def ) together with associated validation target T = (L, tgt) and schema pattern P = (PL, pdef , sample) with sample = tgt.A target tgt(L) is given as a tuple (Q, N + , N -) of a SPARQL query Q to be executed against G and sets of nodes N + and N -, to be added, resp. removed from the result of query Q. The schema and the targets can be modified using the following editing operations:

modify def (L) for shape label L using these actions:

• add or remove a Conjunct or ValueConstraints;

• group two or more triple constraints into a Choice, or split a choice;

• split a TripleConstr of the form p V C in two TripleConstrs p V 1 C 1 and p V 2 C 2 having the same predicate, or regroup two such triple constraints; • change the cardinality or the ObjectConstr of some triple constraints with predicate p. In particular, the object constraint can be replaced by the automatically constructed {msc(N )} or {lac(N )}, where N is the set of p-neighbours of tgt(L); modify tgt(L) for shape label L. This action is triggered automatically when some triple constraint is changed and becomes of the form p @L C (with shape reference to L). Then the set N of all IRI p-neighbours of tgt(L) is added to tgt(L ). In the latter case, the NeighbConstr M is automatically constructed as msc(N ) or lac(N ). add a new shape label L to L with corresponding target tgt(L) = N and pattern pdef (L), which triggers the automatic construction of msc(N ) or lac(N ) using pdef (L) as pattern and assigns the result to def (L).

These operations allow to construct an arbitrarily complex SCL schema starting e.g. from an automatically constructed one. At any time the user can visualize the result of validating G against S with target T. Additionally, the user has access to the following information:

for any shape label L and triple constraint p V C that occurs in def (L) or in pdef (L), and denoting N = tgt(L):

• the number of nodes in N that have p as predicate;

• the minimal, maximal and average number of occurrences of predicate p in the neighbourhood of N ; • the lattice of uniform value constraints (F, ) annotated with acc π F (V ) for every V ∈ F (see Sect. 3.1); for any pair of predicates p, p , the number of nodes from N in which p and p co-occur; this is useful to detect possible Choices.

Implementation We have already implemented several components of our method, some of which are illustrated in the video attached to the submission:

the algorithm for automatic construction of the most specific schema with only limited support of schema patterns tailored for Wikidata (video), simple visualisation of statistics about the data, enhanced visualisation of validation results that allows to navigate synchronously in the schema and in the graph to understand why a given node is valid or not w.r.t. a given constraint (video).

Currently our implementation is based on ShEx validation. In order to complete the implementation we need to: (1) complete the implementation of schema patterns;

(2) add support for SHACL validation; (3) provide a nice visualisation of the about the data; and (4) integrate the different components into a single application. Fig. 9 shows a consolidated view of three of the already implemented components. We consider a sample with four Wikidata entries: Auckland, Monterey, Vienna and Kobe (restricted to a part of their predicates only). The top right panel contains the schema that was automatically constructed using a schema pattern similar to the one presented in Fig. 7. We changed a single cardinality in that schema that produced a validation error. In the bottom panel we see the list of validated nodes on which the error is highlighted. The top left panel shows part of the information provided to the user, i.e. the list of the properties of sample nodes and their frequencies of occurrence. We have presented a method that allows to define ShEx or SHACL schemas for existing datasets. The construction of simple (uniform) schemas is fully automatic and is accessible to novice users, while experts can supply their knowledge about the data using schema patterns an expressive parametrization mechanism, and further edit the resulting schema. A prototype implementation of the method allows to extract and refine ShEx schemas for Wikidata. We are currently extending the implementation in order to integrate the still missing features: full support for schema patterns, translation to SHACL and integrated SHACL validation, a more readable representation of the statistics about the data using GUI widgets. As a future work we are planning to enhance schema patterns in order to capture richer information that comes from ontologies such as cardinalities, and also to allow to describe more complex references between shapes. A The Shape Constraint Language, SHACL and ShEx

We explain here how SCL is translated to SHACL and to ShEx, then we explain the small differences in semantics depending on the target language.

Translation to SHACL SCL's ValueConstrs are represented using sh:nodeKind (for lit, nonlit, blank, iri), using sh:datatype for XSD, using sh:pattern for Prefix, and using sh:in for ListValues. A NeighbConstr yields a sh:shape that is a conjunction (sh:and) of the encodings of its Conjuncts. The Choice operator can be represented by sh:or or by sh:xone (which one to use is a parameter of the translation). TripleConstr is encoded using sh:property with sh:path constraint for its predicate, while its ObjectConstr is represented by sh:node if it is a shape reference or a nested NeighbConstr, and by the encoding of the ValueConstr otherwise. Cardinality is represented by sh:minInclusive and sh:maxInclusive as expected. Additionally, if two or more triple constraints in the same neighbourhood constraint have the same predicate, then all these triple constraints are encoded using sh:qualifiedValueShape, and their cardinalities using sh:qualifiedMinCount and sh:qualifiedMaxCount. Finally, SHACL shapes have associated target declarations that are not provided by the SCL schema but by its accompanying validation target. In Fig. 10 we give as example the shapes <Person> and <Date> from Sect. 2 written in SHACL.

Translation to ShEx

The syntax of SCL is based on the compact syntax of ShEx, therefore the translation to ShEx is almost straightforward, except for Conjunct that becomes EachOf also denoted ; in the compact syntax, and Choice that becomes OneOf denoted |. Additionally, cardinality {1;1} is omitted, cardinaity {0;*} becomes *, {1;*} becomes + and {0;1} becomes ?, while any other cardinality remains as it is. In Fig. 11 we represent the translation to ShEx of shapes <Person> and <Date> from Sect. 2.

Discussion

The semantics of a SCL schema can be different if it is translated to ShEx or to SHACL. The two differences come from the choice operator and from the use of different triple constraints with the same property in the same neighbourhood constraint. This is not an issue for our approach because we make the hypothesis that the user constructs a schema for one of the two languages, not for both, depending on the application she or he has in mind and on her/his production suite. The validation results in the interactive tool are computed using the translation to the chosen target schema language, whichever it is. When the desired abstract SCL schema is ready, it is exported and can be used in production.

B Formal Definition of Shape Patterns

A schema pattern is defined by the syntax in Fig. 8. We additionally require that (1) no PredFilter is used more than once in the same constraint pattern, and (2) every shape label variable Y ∈ V sch is used exactly once in the range of pdef .

Denote by E the set of PredFilters of constraint patterns. Remark that E is a subset of the set F of value constraints defined in Sect. 3, and that (E, ) is an upper semilattice with least upper bound E = iri. For any PNeighbConstr P , denote E(P ) the set of predicate filters that appear in the direct PTripleConstrs of P (that is, excluding those that appear in some nested PNeighbConstr). Because E(P ) ⊆ E and (E, ) is a lattice, it holds that for every property q either no element of E(P ) matches q and we write match(P, q) = ⊥, or there is unique most precise f in E(P ) s.t. [q] f and we write match(P, q) = f . For a property q, denote E(P ) q the set of filters in E(P ) that match q, i.e. E(P ) q = {f ∈ E(P ) | [q] f }. For instance, if P is pdef (Y ) from Fig. 7 then ps: ∈ E(P ) and ps: ∈ E(P ) ps:foo .

Fix a pattern schema P = (PL, pdef , sample) for the sequel. Its associated most specific schema with uniform constraints msc(P) is defined below. We point out first that msc(P) is not a uniform schema as it allows nested neighbourhood constraints and shape references, but likewise uniform schemas, its neighbourhood constraints satisfy do not use choice or repeated properties. So let msc(pat) = (L, def ), we explain now which are the shape labels in L and which are their definitions.

For every shape label L ∈ PL, L is in L and its its definition P = pdef (L) together with its sample N = sample(L) define a NeighbConstr S = msc(P, N ). S is a conjunct of TripleConstrs (without Choices). Denote by filters(P ), resp. by predicates(P ), the set of Predicates, resp. of PredFilters, that occur in the PTripleConstrs of P . For instance, filters(pdef (Y )) = {ps:, pq:} and predicates(pdef (Y )) = {rdf:type} for the pattern for shape Y in Fig. 7. Then let props(P, N ) be the set that contains exactly the properties that apper in P and all properties that appear in the neighbourhood of N and match some of the filters in P .

props(P, N ) = predicates(P ) ∪ {q ∈ props(N ) | match(P, q) = ⊥} .

Finally, for every predicate q ∈ props(P, N ), its associated sample s(q) is the set of q-neighbors of N .

Each q ∈ props(P, N ) yields a triple constraint q O C which object constraint O and cardinality constraint C are defined as follows. Let H q be the object constranint holder for q by P . That is, if q ∈ predicates(P ), then H q is the object constraint holder associated with q in P . Otherwize, H q is the object constraint holder associated with match(P, q), the most precise predicate filter that matches q. Now, the object constraint O is, depending on the form of H q , and denoting N q the set of q-neighbours of N :

-If H q = (a value constraint holder), then O = N q .

-If H q = [ ] (a list of values holder), then O is the list that contains exactly the values in N q .

-If H q = {M } (a nested neighbourhood constraint pattern), then M = msc(P, N q ). -If H q is of the form @X (shape reference), then we create a fresh shape label <X q> and O = @<X q>. We add <X q> to L and its definition def (<X q>) = msc(pdef (X), N q ).

Because the pattern P is not recursive (requirement (2) above), this procedure terminates and construcs a shapes schema.

We finally point out that schema patterns might suffer of the problem of "shrinking samples". Even if the size of sample(L) for some L ∈ PL is sufficient, its nested neighbourhood constraints are constructed using samples of q-neighbours of the nodes in N for the appropriate predicate q. If predicate q occurs only a few times in the neighbourhood of N , then the corresponding sample can be very small. In our implementation we warn the user if such situation occurs, and allow her to add additional nodes to that sample without necessarily augmenting sample(L) (for efficiency and readability reasons).

{

  rdf:type [foaf:Person] {1;1}; owl:sameAs IRI {0;*} ; foaf:name xsd:string {1;1}; foaf:familyName xsd:string {1;1} ; ( bio:birth xsd:gYear {1;1} | rdgr2:dateOfBirth @<Date> {1;1} ) } In Appendix A we show how these shapes are expressed in ShEx and SHACL.

Fig. 1 .

 1 Fig. 1. Nodes of type foaf:Person

Fig. 2 .

 2 Fig. 2. Syntax of the constraint language.

Fig. 3 .

 3 Fig. 3. Syntax of uniform constraints.

Lemma 2 .

 2 For any sample N ⊆ Nodes(G), it holds that G satisfies the schema ({S}, [S → msc(N )]) with target ({S}, [S → N ]).

  It is then easy to see that acc π (o ) is the total number of votes, i.e. acc π (o ) = |W |.Let 0.5 < t ≤ 1 be a threshold value. We define the consensus option that is acceptable for at least a proportion t of the voters. Let a = min acc π (o)| accπ (o) |W |≥ t be the least value in the range of acc π s.t. a |W | is above the threshold. Thenconsensus(O, , W, π, t) = {o | acc π (o) = a} .Note that, by definition, consensus(O, , W, π, t) is uniquely defined for all semilattices (O, ), sets of voters W , vote functions π : W → O and thresholds t.Example 2 (Consensus). Below on the left, consider the tree (thus also upper semilattice) (F , ) with F ⊆ F , where V is a child of V whenever V V . Assume a set W of 20 voters and a voting function π : W → F . For every option V we give between parentheses (x; y) where x is the number of direct votes (i.e. x = |{w ∈ W |π(w) = V }|) and y = acc π (V ). Then for different values of the threshold we obtain: consensus(F , , W, π, 17 20 ) = iri, consensus(F , , W, π, 18 20 ) = nonlit and consensus(F , , W, π, 19 20 ) = any. Below on the right is presented the latitice K, again annotated with (x, y) as above for a set W of 20 voters and a voting function π : W → K. Then consensus(K, ⊆, W , π , 17 20 ) = {{0; 1}, {1; * }} = {0; * }.

Fig. 7 .

 7 Fig. 7. Schema pattern Pcity for Wikidata cities

Fig. 8 .

 8 Fig. 8. Syntax of constraint patterns.

Fig. 9 .

 9 Fig. 9. Screenshot of some parts of the tool

  Assume a non-empty set O of options to choose from by a finite set of voters W , and let (O, ) be an upper semilattice with least upper bound o , where o o indicates that if option o is acceptable for given voter, then o is acceptable for him/her as well. Every individual n votes for its preferred option π(n) ∈ O, and let acc π (o) be the number of voters that consider option o as acceptable. Formally, for any total function π : W → O, we define acc π

  7 , which is clearly too

	<City> {
	a [ wikibase:Item ] {1;1} ;
	wdt:P17 wd: {1;1} ;	p:P17 blank {1;*} ;
	wdt:P6	wd: {0;1} ;	p:P6	blank {0;*} }
		Fig. 5. Most specific constraint for a sample of Wikidata cities
	<City> {
	a	wikibase:	{1;1} ;
	wdt:P17 wd:	{1;1} ; # exactly one direct country statement
	p:P17	@<Y_P17>	{1;*} ; # several country statements
	wdt:P6	wd:	{0;1} ; # optional direct h. gov. statement
	p:P6	@<Y_P6>	{0;*} } # 0 or more h. gov. statements
	<Y_P17> {
	a [ wikibase:Statement ] {1;1} ;
	ps:P17 wd:	{1;*} } # at least one country statement
	<Y_P6> {
	a [ wikibase:Statement ] {1;1} ;
	ps:P6	wd:	{1;1} ;
	pq:P580 xsd:dateTime	{1;1} ; # mandatory start time
	pq:P582 xsd:dateTime

{0;1} } # optional end time Fig. 6. Schema Scity for Wikidata cities

  13. Principe, R.A.A., Spahiu, B., Palmonari, M., Rula, A., De Paoli, F., Maurino, A.: ABSTAT 1.0: Compute, Manage and Share Semantic Profiles of RDF Knowledge

	Graphs. In: European Semantic Web Conference. pp. 170-175 (2018)
	14. Prud'hommeaux, E., Boneva, I., Labra Gayo, J.E., Gregg, K.: Shape Expressions
	Language (ShEx). W3C Shape Expressions Community Group Drat Report (2018)
	15. Spahiu, B., Maurino, A., Palmonari, M.: Towards Improving the Quality of Knowl-
	edge Graphs with Data-driven Ontology Patterns and SHACL. In: WOP@ISWC
	(2018)
	16. Werkmeister, L.: Schema Inference on Wikidata. Master Thesis (2018)

https://tools.wmflabs.org/wd-shex-infer/ retrieved on 2019/04/11.

Incorrect w.r.t. a supposedly existing correct uniform constraint that the user aims at.

From https://www.wikidata.org/entity/Q37100.ttl retrieved on 2019/03/27.

restricted to the properties rdf:type, P17 and P6.

that is, allow two triple constraints with same predicate in the same neighbourhood constraint