Melanie Noyel
email: mnoyel@acta-mobilier.fr

Philippe Thomas
email: philippe.thomas@univ-lorraine.fr

André Thomas
email: andre.thomas@univ-lorraine.fr

Patrick Charpentier
email: patrick.charpentier@univ-lorraine.fr

Mélanie Noyel

Reconfiguration process for neuronal classification models: Application to a quality monitoring problem

Keywords: classification, control chart, learning, multilayer perceptron, neural network, quality, relearning

come

Reconfiguration process for neuronal classification models: Application to a quality monitoring problem

Introduction

In the smart industry domain, the elements of the physical system share information with each other and with a real time decision-making system. These decision systems must evolve and adapt according to the physical state of the environment. For example, in the quality control domain, we may consider the impact of environmental factors (such as temperature and humidity) on a die-casting process [START_REF] Thomas | Quality monitoring of a high pressure die casting process based on bayesian and neural networks[END_REF]) or a lacquering process (Noyel et al. 2013a), as well as the impact of tool wear on the finished surface in a machining process [START_REF] Sick | On line and indirect tool wear monitoring in turning with artificial neural networks: a review of more than a decade of research[END_REF]. Other examples of real-world change detection problems include modeling in bio-medicine monitoring and industrial processes, as described by [START_REF] Basseville | Detection of Abrupt Changes: Theory and Applications[END_REF].

These different contexts lead to classification or supervised classification problems, which can be resolved using machine learning algorithms, where various techniques can be applied, including logic-based algorithms (such as decision trees and rule-based classifiers), neural networks (NNs such as multilayer perceptrons (MLPs) and radial basis function networks), statistical learning (such as naive Bayes classifiers and Bayesian networks), and support vector machines (SVMs). The present study focuses on classification problems where continuous data are mainly considered. In this case, [START_REF] Kotsiantis | Supervised machine learning: A review of classification techniques[END_REF] has highlighted that the most suitable approaches are logicbased algorithms, NNs, and SVMs.

To extract a classifier from data using machine learning, the complete learning dataset is provided to the learning machine, which obtains descriptions for the underlying concepts in the dataset (Lazarescu et al. 2003). This type of learning is called batch learning. However, the target concept may be non-stationary and it can change over time, thereby leading to concept modification [START_REF] Michalski | The Multi-Purpose incremental Learning System AQ15 and its Testing Application to Three Medical Domains[END_REF]. [START_REF] Gama | Knowledge Discovery from Data Streams[END_REF] separated this conceptual evolution into concept drift when the evolution is gentle and concept shift when the evolution is sudden. For example, a concept drift may result from tool wear or filter clogging, whereas a concept shift may occur after the replacement of parts or a system modification. When a concept shift or concept drift occurs, the model obtained using batch learning may no longer be accurate. Therefore, incremental algorithms, online algorithms, and anytime algorithms have been proposed to respond to this problem. Incremental algorithms consider new data in order to adapt the model without restarting the complete learning process (Salperwick et al. 2009). Online algorithms are used when the stream of data is continuous and the data are used individually and sequentially (Salperwick et al. 2009). In these two approaches, the learning must be faster and the data are generally presented only once to the algorithm. Anytime learning is defined as learning the best model (considering a given criterion) until a break occurs (such as new data arrival) [START_REF] Dean | An analysis of time-dependent planning[END_REF]. In these three approaches, the learning and exploitation of the model must be performed simultaneously, so the computational time required may be prohibitive in real-time applications, even if anytime approaches include resource constraints. These learning approaches may exhibit slower convergence than batch approaches, thereby leading to an inaccurate model. Moreover, because the data are used individually, outliers may have a deleterious impact on the model obtained. Finally, incremental learning must address the plasticity-stability dilemma [START_REF] Bouchachia | Fuzzy classification in dynamic environments[END_REF], which demands a compromise between the stability and reconfigurability of the model.

Due to the limitations of the online approaches, batch learning is useful because it can be performed in real time whereas learning is performed offline. Batch learning can approximate every nonlinear function with the desired accuracy, as well as using a variety of algorithms to avoid bad local minima or the overfitting problem, and cross-validation can be performed based on the validation dataset. None of these processes can be performed with incremental learning, and [START_REF] Sarle | Comp.ai.neural-nets FAQ, part 2[END_REF] showed that it is generally more difficult and unreliable than batch learning. Considering the drift or shift concepts allows changes to be detected during batch learning, and change detection can be performed with different approaches (Salperwick et al. 2009), as follows:

-

Relearning the classifier from scratch, -Adapting the classifier, -Adapting the data summary used in the classifier (e.g., the kNN model), -Using the sequence of classifiers that is learned over time in a classifier ensemble as example [START_REF] Bifet | Learning from Time-Changing Data with Adaptive Windowing[END_REF].

Using of classifier ensemble allows to improve the accuracy of the classification. However, many individual classifiers must be evaluated simultaneously and this fact may be time consuming during the exploitation phase of the model. Adapting the classifier by parameters relearning allows to limit the computational cost by considering that even if a drift occurs, the original model is not so far of the desired one. However, in case of major context change, the model structure itself must be corrected. In this case, the classifier must be relearned from scratch.

We propose an adaption of the classifier in order to limit the computational cost. We focus on the use of a MLP classification model due to its adaptability to change. In fact, the adaptation of a MLP classifier may be performed by a learning process based on the new dataset using the initial model parameters as the parameter set for initialization. It is assumed that even if a concept shift or concept drift occurs, the initial classifier is no more accurate but its parameter set will remain close to the optimal set.

The following different approaches may also be used for change detection [START_REF] Gama | A survey on concept-drift adaptation[END_REF]):

-Using sequential analysis (e.g., sequential probability ratio test [START_REF] Wald | Sequential Analysis[END_REF]), Page-Hinkley test (PHT) [START_REF] Page | Continuous inspection schemes[END_REF][START_REF] Hinkley | Inference about the change-point from cumulative sum tests[END_REF], and cumulative sum [START_REF] Page | Continuous inspection schemes[END_REF])); -Using statistical process control (SPC) (Klinkenberg and Rentz 1998[START_REF] Gama | Learning with drift detection[END_REF][START_REF] Bouchachia | Fuzzy classification in dynamic environments[END_REF]); -Monitoring the distribution based on two different time windows [START_REF] Dries | Adaptive concept drift detection[END_REF]Ruckert 2009, Adae and[START_REF] Adae | Eve: a framework for event detection[END_REF]; -Contextual approaches [START_REF] Harries | Extracting hidden context[END_REF][START_REF] Bouchachia | Fuzzy classification in dynamic environments[END_REF].

Sequential analysis approaches are very sensitive to the choice of the detection threshold [START_REF] Ragot | Validation de données et diagnostic[END_REF]). The main limitation of time window-based approaches is the possibility of high memory consumption [START_REF] Gama | A survey on concept-drift adaptation[END_REF]. Contextual approaches are used mainly in conjunction with incremental learning. Thus, in the present study, a SPC approach is used to determine when relearning is required. However, even if a change is detected and the need for relearning is evident, a question remains: What dataset should we use for relearning? PHT can estimate the time when a drift or shift concept starts [START_REF] Ragot | Validation de données et diagnostic[END_REF]); thus, PHT may be used in conjunction with SPC to build the relearning dataset. Finally, industrial datasets are often affected by outliers so a robust learning algorithm is required in order to limit the impact of outliers on the classifier.

The main contribution of this paper is the proposition of a model monitoring procedure which associates SPC and PHT algorithms in order to adapt the model to change (by using relearning procedure). MLP is used as model and its adaptation is performed by using backpropagation algorithm. SPC is used to estimate the need of model's adaptation. PHT is used to determine the dataset which must be used during the relearning procedure.

In the following, after explaining the batch learning approach for designing the monitoring system, we discuss the impact of changing the context. The need for adaptation is highlighted and the proposed method is developed in two steps: determining when the system is finally drifting using control charts and evaluating how much data must be relearned. Finally, the proposed approach is tested on both a benchmark case and an industrial case, i.e., a quality monitoring problem for a lacquering company.

Description of the batch learning process

To predict the behavior of a real system, a classical approach involves the design of a forecasting model (Figure 1). The behavior of this forecasting system, which is parallel to the physical one, is as similar as possible to that of the real system. It can measure different parameters in the physical system and compare its forecasts with reality. For classification problems, the considered forecasting system can predict the class of the output data; therefore, it can be used to evaluate the decision taken upstream.

Figure 1 -Relationship between the forecasting model and physical system.

The classical approach to the design of the forecasting model employs a learning machine in order to extract the forecasting model directly from the data using batch learning. This task is performed according to a classical knowledge discovery and data mining (KDD) process, which comprises two main steps: collecting the dataset (including identification and data collection and pre-processing) and the data mining task (which needs to define

Physical system

+ -

Forecasting model

the training and validation datasets) [START_REF] Patel | A review on ensemble of diverse artificial neural networks[END_REF]. This KDD process is summarized by figure 2 and the two main task will be more detailed in the two following subparts.

Figure 2:

The process of supervised machine learning [START_REF] Kotsiantis | Supervised machine learning: A review of classification techniques[END_REF].

Dataset collection

To design the dataset collection, the first step is to define the objective function, which is the output of the forecasting model and it corresponds to the characteristics of the physical system that we aim to monitor.

Next, the factors that are most likely to affect the objective function must be identified. Different efficient strategies may be used in order to identify these influential factors, such as the Ishikawa method.

After the objective function and influential factors have been identified, the values of these different parameters must be collected. This step should aim to improve the instrumentation by adding some captors in order to collect influential factors that have not yet been collected. However, in some cases, automatic data collection is not possible and manual data collection must be performed. Unfortunately, manual data collection is often viewed as a waste of time by the operators, and the low priority given to this task often leads to corruption of the dataset by outliers. To reduce this risk, it is necessary to ensure that the operators consider the importance of this task and to make the interfaces as intuitive and quick as possible (Noyel et al. 2013b).

The data preparation process required before learning includes selecting, preprocessing, and transforming the data. For example, the data must be preprocessed in order to synchronize the different databases, delete evident outliers, and digitalize qualitative data (e.g., as colors) [START_REF] Patel | A review on ensemble of diverse artificial neural networks[END_REF].

After these steps, a dataset can be used to extract knowledge with learning tools.

Data mining or learning

Management and quality improvement using data mining methods were discussed by [START_REF] Kusiak | Rough set theory: a data mining tool for semiconductor manufacturing[END_REF]. Data mining is the main part of the KDD process, which involves data analysis to summarize the data in the form of useful information. The KDD process may be performed to identify valid, novel, useful, and understandable patterns by exploiting the full volume of data collected.

Data mining

As shown by [START_REF] Agard | Exploration des bases de données industrielles à l'aide du datamining -Perspectives[END_REF], the volume of data that needs to be analyzed is often large. Classically, the collected dataset is divided into two parts, where one is used for learning the model and the other for validation. This procedure allows us to check that our model exhibits the same behavior as the physical system. Different tools may be used to perform the data mining task, such as Naïve Bayes, decision trees, SVMs, and NNs. Decision trees are faster at classifying the data but they do not work well with noisy data [START_REF] Patel | A review on ensemble of diverse artificial neural networks[END_REF]; therefore, this approach is not efficient with industrial data. Naïve Bayes is appropriate for the treatment of discrete data, so we need to discretize the data to apply this approach to continuous data. Both SVMs and NNs employ very similar concepts, and thus they yield very similar results, where SVMs sometimes give better results [START_REF] Meyer | The support vector machine under test[END_REF] whereas NNs may give the best at other times [START_REF] Paliwal | Neural Networks and Statistical Techniques: A review of applications[END_REF]. These four tools (SVM, MLP, decision trees, and kNN) have been tested and compared based on the real example used in this study, and MLP obtained the best results [START_REF] Noyel | Contrôle intégré du pilotage d'atelier et de la qualité des produits, application à la société ACTA mobilier[END_REF]. The proposed approach presented section 3 may be adapted to each type of model. However, in the present study, we focus on the use of a MLP with only one hidden layer, a sigmoidal activation function, and an output neuron. Its structure is given by the following formula (1):

0 1 2 1 0 1 2 1 1 1 . . n n i ih h i i h z g w g w x b b = =     = + +         ∑ ∑ , ( 1
)
where 0 indicates the bias of the output neuron, g2(.) represents the activation function of the output neuron, and z denotes the network output. This problem involves classification between two classes 0 and 1. So g2(.) is selected as sigmoidal in order to allow the evolution of the output value between these two bounds 0 and 1.

In order to determine the number of hidden neurons and to discard spurious inputs, the learning phase starts with an overparameterized structure. This structure includes all the variables collected during the preceding step and a number of hidden units clearly greater than necessary (between 2 and 3 times greater than the inputs number). The weights of this overparameterized structure are initialized using classical Nguyen and Widrow algorithm [START_REF] Nguyen | Improving the learning speed of 2-layer neural networks by choosing initial values of the adaptive weights[END_REF], Mathworks 2016), and the learning of these weight is performed by using the Levenberg-Marquard algorithm with a robust criterion [START_REF] Thomas | Neurall modeling of an induction furnace using robust learning criteria[END_REF], Mathworks 2016) in order to avoid the outliers impact on the resulting model. Due to the overparameterized structure, the resulting model presents overfitting. In order to avoid it, a weight elimination algorithm (pruning) is used to discard spurious inputs and hidden nodes (Thomas andSuhner 2015, Mathworks 2016). All this procedure is performed on a part of the available dataset called learning dataset. The accuracy of the obtained model is determined by using the remaining data (not used for the learning) and is called validation dataset.

The completion of this process yields a classification model, which can be used as a forecasting system to monitor the real system. However, this model is static whereas the system or its environment can evolve. Therefore, an adaptation procedure is needed to fit the model to the real system if changes occur.

Proposition of classification neuronal model adaptation process

Limits of batch learning in a changing context

Two different types of changes can occur in the monitored system [START_REF] Sebastiéão | A study on Change Detection Methods[END_REF]):

• A "concept shift" refers to an abrupt change;

• A "concept drift" is associated with gradual change.

Concept drift is more difficult to detect and it is often confused with noise. However, this is the type of change that we must identify in order to ensure that the behavior of the monitoring system remains as close to reality as possible.

In our previous study (Noyel et al. 2013a), we highlighted two reasons why the behavior of the forecasting system starts to deviate from reality. The first concerns the evolution of the input parameters. Thus, with a learning model, the learning outcome is valid only in the learned domain. In many cases, the data range which can be determined with the dataset collected (weak bounds) don't correspond to the complete evolution range of the considered variable (strong bounds). As example, if we study the evolution of output temperature in Paris during January 2016, the bounds of the evolution range (weak bounds) are -4.4°C and 13.9 °C. However, by considering all the dataset available since 1873 the temperature has evolved between -14.9°C and 16.1°C and we can imagine that these record values may be outperformed in the future and so, the strong bounds are unknown.

For the learning process, the main risk is encountering a situation where one factor is outside the bounds of the learned domain (weak bounds) because the model cannot give a correct answer. For the example shown in Figure 3, the strong bounds are given by dashed lines when the colored sectors correspond to the known range given by the dataset. In this figure, forecasts are possible in cases 1 and 2 but not in cases 3 (factor 5 is out of weak bounds) and 4 (factor 2 is out of weak bounds). These points may be outside the learning domain due to concept drift (e.g., a gradual change) or concept shift (e.g., a pressure drop due to a compressor failure).

Figure 3 -Situations where a forecast may or may not be possible.

The second reason concerns the uncontrolled modification of the behavior of the real system. In fact, it is possible to affect the behavior of the real system by changing a parameter (voluntarily or not) that is not an input of the forecasting system.

Therefore, the main issue is synchronization with reality, where we have to optimize the synchronization frequency because synchronization is time consuming (a revision of the model can take several minutes to several days). It is better to rely on statistical findings (using SPC tools as example) rather than considering the resynchronization frequency in terms of the response to events (such as the arrival of new information from one of the connected devices (incremental learning) or solicitation by an operator) or over a period (e.g., every hour or week). Among the seven basic tools, control charts, also known as "Shewhart charts" or "process-behavior charts" [START_REF] Shewhart | Economic control of quality of manufactured product[END_REF], are useful SPC tools in the proposed monitoring system.

First, a prerequisite for detecting changes is the ability to verify hypotheses after being informed about reality. This step requires an improvement to the information technology system in order to collect data as the output from the real system. We can monitor the difference between theory and reality by comparing these data with the system hypotheses, where this value is called the error rate. The evolution of this rate can be disturbed by the normal production noise. At first glance, it appears to be difficult to determine when the system is actually drifting in reality.

Principe of classification neuronal model adaptation process

To take account these limitations, a model monitoring approach is proposed for adapting the forecasting model. The principle of model monitoring is illustrated in Figure 4 and is an extension of the classical process presented figure 1. In this approach, a forecasting model is extracted from a dataset in the first step by using a classical KDD process. In the second step, a monitoring procedure is used to detect the occurrence of drift and to react.

The main objective of this paper is related to this monitoring process.

Figure 4 -Monitoring the forecasting model.

Many optimization algorithms are subdivided in different tasks in order to reach their goals. We can cite, as example, pruning algorithms which tend to determine the optimal structure of neural network after learning step [START_REF] Thomas | A new multilayer perceptron pruning algorithm for classification and regression applications[END_REF], or METSK-HD algorithm [START_REF] Gacto | METSK-HD e : A multiobjective evolutionary algorithm to learn accurate TSK-fuzzy systems in high-dimensional and large-scale regression problems[END_REF]) which combines a classical evolutionary learning of fuzzy model in a first step and a post processing step allowing to perform rule selection and tuning of membership function. In this paper, two main tasks must be performed to design the monitoring system, each of which is subdivided into different subtasks, as follows.

1) Design the forecasting model (batch learning process described section 2) a. dataset collection (described section 2.1) b. data mining or learning (described section 2.2) 2) Design the model monitoring system c. Collect the data d. Detect the occurrence of drift between the forecasting and physical systems (described later section 3.3) e. Construct the relearning database (estimate the start time of the drift) (described later section 3.4) f. Adapt the forecasting system

The first main task (1) is a classical KDD process and it is described in section 2. It allows to obtain the initial forecasting model.

The design of the model monitoring system (2) includes the collect of data during the production (c) in order to construct the dataset. It corresponds to the same process as that one described section 2.1. This dataset is used firstly to detect a drift occurrence by using SPC tools (d) and then to estimate the start time of the drift in order to define the relearning dataset by using PHT (e). This start time estimated allows to design the dataset used during the last sub step (f). This dataset includes all the data collected between the estimated start time and the present time. The last step is a relearning step (f). Its goal is to fit the model with the reality by adapting the parameters of the forecasting model to the detected drift.

The process presented in Figure 5 can be followed to adapt the model to changes.

Physical system

Model Monitoring

+ -

Forecasting model

Figure 5 -Adaptation process.

The initialization process was described in section 2 and it corresponds to the design of the forecasting model, which is a classical KDD task, including here the dataset collection (and pre-processing), and the data mining step (including initialization, learning and pruning sub steps). The supervision step is conducted at the same time as model exploitation. During this step, the results obtained by the monitoring model are compared with the data collected from the physical system in order to detect the emergence of drift between both and its correction. The step employed to detect the occurrence of drift is discussed in section 3.3. The relearning database must be constructed when drift is detected. This step is discussed in section 3.4. The setup of the classifier is the relearning step which is performed by using the classical learning algorithm as during the KDD process, here, the Levenberg-Marquard algorithm with a robust criterion [START_REF] Thomas | Neurall modeling of an induction furnace using robust learning criteria[END_REF], Mathworks 2016). The relearning is initiated and performed as soon as a drift is detected, its start time estimated and the relearning dataset constituted.

Determining whether the system is drifting by using control charts

Control charts are particularly useful for dynamic control based on time-series data [START_REF] Tague | The Quality Toolbox[END_REF]. This method is useful for statistically determining whether the dimensional variation of parts is no longer under control. Indeed, it is known that even when a process is under control, there is a probability of approximately 0.27% that a point will exceed 3-sigma bilateral control limits (Pareto). These few isolated points should not trigger relearning, but an increase in the number of points will be detected to indicate the presence of a special cause, even if it is not yet known.

We propose the combination of a NN with control charts to exploit the robustness of statistical analysis and the adaptability of the NN. [START_REF] Du | The embedded Quality Control System of Product Manufacturing[END_REF] studied the inverse combination of both tools by using a recognition algorithm for control charts and NNs to obtain alerts in the case of quality problems, as well as providing clues to identify the causes. Control charts (p-charts) (NIST/SEMATECH 2012) aim to determine whether the misclassification rate is drifting according to the principle illustrated in Figure 6, where each point in the figure corresponds to the misclassification rate obtained with a sample of k data and k corresponds to the sample size (k is selected according to several criteria such as criticality and frequency). Traditionally, two bounds are determined with control charts in order to define an acceptable zone for the misclassification rate (dashed green and red lines on the graph). The misclassification rate is an average of several values, so we assume that if this rate is outside the green bounds, then many values are outside the bounds, and thus the system is effectively drifting. Therefore, we need to perform relearning when the misclassification rate obtained for one sample (e.g., sample 7 in Figure 6) falls outside these bounds. The dotted lines in Figure 6 represent the evolution of the misclassification rate when no relearning is performed. Three examples are presented which present the evolution of the misclassification rate if the relearning needed at the 7 th , 23 th and 34 th samples (misclassification rate > UCL95%) are not performed.

Two pairs of bounds may be determined using the confidence level. The warning bounds, i.e., the lower (LCL95%) and upper (UCL95%) bounds, are defined with a confidence level of 95%, as follows.

95% 95%

(1 ) 1.96

(1 ) 1.96

p p LCL p p k p UCL p k  - = -    -  = +   2
The forbidden bounds, i.e., the lower (LCL99.8%) and upper (UCL99.8%) bounds, are defined with a confidence level of 99.8%, as follows: 99.8% 99.8%

(1 ) 3

(1 ) 3

p p LCL p k p p UCL p k  - = -    -  = +   , 3
where k corresponds to the size of the sample and p is the center line, which must be estimated. The center line corresponds to the misclassification rate obtained for the validation dataset (defined section 2.2) during the initial learning process (Noyel et al. 2013b). The decision about relearning may be made when the misclassification rate of a sample is outside the warning bounds (e.g., for sample 7 in Figure 6). This step highlights when to trigger relearning and the next step determines the amount of data required to perform this action.

Determining the amount of data required for relearning

Control charts allow us to determine whether the system is actually drifting. To correct our forecasting system, we need to perform relearning based on a specific amount of new data. The relearning is achieved by using a batch second order backpropagation algorithm which includes the determination of hessian and gradient matrix whose size depends on the number of parameters (complexity of the model) and on the number of data (size of the dataset) [START_REF] Thomas | Neurall modeling of an induction furnace using robust learning criteria[END_REF]. So the re-learning speed is improved by reducing model size (pruning step, section 2.2) and reducing re-learning dataset (estimation of the start time of the drift). It can be noticed that the re-learning speed is not crucial. In fact, re-learning must be launched only when a new drift is detected by SPC, and so when k new data corresponding to the size of one sample in SPC are collected since the last supervision step (figure 5). The re-learning step disposes of the time of collect of these k new data to run.

The control charts enhance the data if drifting is detected, but they cannot determine when the drift started, and thus they cannot estimate the precise amount of data required to perform relearning. The following two cases must be considered.

• The time since the last relearning process is not crucial because it is possible to perform relearning based on all of the newly available data. Thus, the task is very simple and fast (similar to classical learning). • The time since the last relearning process is crucial, and to save time, it is possible to restart the entire learning process based on a defined amount of data, where we can consider "sliding windows." This solution allows the system to forget old behaviors that may no longer be relevant so the behavior of the forecasting system is more flexible. The best data window size must be defined correctly. Thus, the system will learn the noise if it is too short, whereas there will be insufficient flexibility if it is too long. The aim is to determine the point of inflexion based on the error rate, i.e. the estimated start time of the drift.

Different methods may be used to determine the point of inflexion, such as adaptive windowing (ADWIN) [START_REF] Bifet | Learning from Time-Changing Data with Adaptive Windowing[END_REF], SPC [START_REF] Gama | Learning with drift detection[END_REF]), the fixed cumulative windows model (FCWM) [START_REF] Sebastião | Monitoring incremental histogram disctribution for change detection in data streams[END_REF], and PHT [START_REF] Page | Continuous inspection schemes[END_REF]. Sebastião and Gama (2009) tested and compared these different algorithms, where the results suggested that PHT and SPC are less time consuming than ADWIN and FCWM. This is crucial because one of the main objectives is to reduce the calculation time by optimizing the relearning dataset size. SPC cannot estimate the time when drifting begins but it can determine the drift detection time. This is important because the difference between these two times may be significantly large, and thus many data that are useful for relearning might be discarded from the relearning dataset. PHT can detect a drift (not used in the present study) and estimate the time drifting begins.

The goal of PHT is to detect a mean jump in a constant signal polluted by white noise [START_REF] Page | Continuous inspection schemes[END_REF][START_REF] Hinkley | Inference about the change-point from cumulative sum tests[END_REF][START_REF] Basseville | Detecting changes in signals and systems[END_REF]). This test can determine whether a jump occurs and estimate the time of this jump. In our case, the signal considered is the absolute value of the error obtained based on different data, where we conduct a search to determine the time drifting occurs between the behavioral model and the real system. This signal may be represented by a sequence of random Gaussian variables: E = [ei], i = 1, …, l, with variance 2 σ and mean mi.

According to the hypothesis that only one jump occurs at an unknown time r with 1 r l ≤ ≤ , detecting this jump corresponds to accepting hypothesis H1 of a change rather than hypothesis H0 of no change.

2 0 0 0 2 1 0 0 2 1 1 : ~( , ), ( )
 = =  = = -   = =  ⋯ ⋯ ⋯ 4
The use of this test implies that the two mean values m0 and m1 are known a priori. In our case, the mean m0 may be estimated based on the mean of the error obtained for the validation dataset during the forecasting system design task. However, the mean m1 is unknown and the minimal absolute value of the amplitude of the jump m δ that needs to be detected is fixed, where the two tests are performed in parallel to detect an increase and a decrease in the mean, respectively. These tests may be calculated recursively to detect the increase in the mean as follows:

0 1 0 0 1 0, , 1 2 0, min( , ) , 1 m i i i i i i U U U e m i U i δ γ γ γ - -  = = + -- ≥    = = ≥  , 5
and the time ri of the last increase in the mean is given as follows. max( )

i i i r i U γ = = 6
For the decrease in the mean, the test is given by

0 1 0 0 1 0, , 1 2 0, min( , ) , 1 m i i i i i i T T T e m i T i δ η η η - -  = = + -+ ≥    = = ≥  , 7
and the time rd of the last decrease in the mean is given as follows. max( )

d i i r i T η = = 8
Therefore, if the control chart detects that relearning is required at time l, then relearning must be performed using all of the data collected between time r and l, where r given by: min( , )

i d r r r = . 9 Tests ( 5) and ( 7) use the minimal absolute value of the amplitude of the jump m δ , which may be fixed as a multiple of the standard deviation σ of the error obtained for the validation dataset. In the present study, we set m δ as:

3 m σ δ = .
10

In function of the complexity of the neural model (number of parameters) and in the goal to avoid overfitting the minimal size of the relearning dataset must be limited to a threshold ∆ such that l-r > ∆. It can be noticed that the overfitting risk is limited by the use of a robust learning criterion [START_REF] Thomas | Neurall modeling of an induction furnace using robust learning criteria[END_REF].

Application to a benchmark

In order to propose a simple and comprehensive application of the proposed approach, a simulation example is used to illustrate the procedure, which is derived from the example proposed by [START_REF] Lin | Support vector machines for classification in nonstandard situations[END_REF]. The main advantage of this simulation is the possibility to create artificially drifts (concept shift and concept drift) and to evaluate the capacities of the approach to detect the drifts, evaluate their start time and fit the model to the new reality. This example considers a population that comprises two subpopulations. The positive subpopulation follows a bivariate normal distribution with mean (0, 0) T and covariance matrix diag(1, 1), whereas the negative subpopulation follows two bivariate normal distributions with mean (2, 2) T and covariance diag(2, 1) for the first subpopulation, and mean (-2, -2) T with covariance diag(2, 1) for the second subpopulation. The population is unbalanced where the positive and negative subpopulations account for 80% and 20% of the total population, respectively. The negative subpopulation is balanced and follows two different laws in order to ensure that the two classes cannot be linearly separable.

Initial forecasting model

The first step is to determine the initial forecasting model as presented section 2. A dataset comprising 1000 pieces of data is constructed and divided into two datasets with 500 pieces of data in each: one for learning and the other for validation. A classification model is constructed using these data. The initial structure is constructed with two inputs and 10 hidden neurons. A pruning phase allows the deletion of three of the 10 hidden neurons. The resulting model obtains a misclassification rate of 8.1%. Figure 7 shows the validation dataset and the separation of the input space into the two classes given by the forecasting model.

Two supplementary datasets are constructed in order to illustrate the procedure, i.e., a concept shift and a concept drift.

Impact of concept shift

A dataset comprising 2000 pieces of supplementary data is constructed for the same simulation example, except the means of the normal distributions change at time 300. At this time, the mean of the positive population becomes (1.5, 0) T and the means of the two normal distributions for the negative population become (3.5, 2) T and (-0.5, -2) T . The covariance matrix remains unchanged.

A control chart is constructed to monitor the forecasting model. The sample size for the control chart is fixed to 100. Two relearning procedures are used to adjust the model to reality. The first uses all of the available data based on the last relearning process, whereas the second uses the PHT procedure described in the previous section. Figure 8 shows the control chart used to monitor the forecasting model, where UCL99.8% and LCL99.8% are shown in the graph, but they are not useful. Each point outside the range [LCL95% -UCL95%] triggers relearning. The evolution of the control chart without relearning is shown by the dotted cyan line, whereas that with relearning by using PHT to determine the appropriate size of the dataset is represented by the dashed line blue, and that with relearning using all of the available data based on the last relearning process is represented in magenta. The concept shift in the real system occurs at time 300, and the control chart detects this concept shift based on the fourth sample (which corresponds to time 400 because the size of each sample is 100). If relearning is not performed, the forecasting model cannot maintain good accuracy. The two relearning strategies allow us to adapt the model to the new behavior of the system even if other relearning steps are required after time 400 to maintain the accuracy of the forecasting model. The results obtained by the two relearning strategies are equivalent. Using the two strategies, no sample is outside the forbidden bounds.

Table 1 -Number, dataset size, time, and duration of relearning: concept shift.

Table 1 shows the number of relearning cycles, time, dataset size for each relearning cycle, and the duration of the overall procedure. This table shows that even if only three relearning cycles are required when PHT is not used (compared with four using PHT), the duration of the total procedure is 100% greater than with PHT. This is because the relearning procedures are performed based on relatively large datasets when PHT is not used.

Impact of concept drift

A new dataset comprising 2000 pieces of supplementary data is constructed for the same simulation example, except the drift occurs at time 300. At this time, the mean of the positive population becomes (0.02*(k -300), As mentioned in the previous section, a control chart is constructed to monitor the forecasting model. The sample size for the control chart is fixed to 100. The same two relearning procedures are tested.

Figure 9 shows the control chart used to monitor the forecasting model. The evolution of the control chart when no relearning is performed is shown by the dotted line cyan, relearning using PHT to determine the appropriate size of the dataset is represented by the dashed line blue, and relearning using all of the available data based on the last relearning process is represented in magenta. The concept drift occurs at time 300, and the control chart detects this concept drift in the eighth sample (time 800). When relearning is not performed, the forecasting model cannot maintain good accuracy. The two relearning strategies allow the model to be adapted to the new behavior of the system and new relearning processes are launched periodically in order to maintain the accuracy of the forecasting model. The results obtained for the two relearning strategies are equivalent. Using the two strategies, no sample is outside the forbidden bounds. Table 2 shows the number of relearning cycles, time, dataset size for each relearning cycle, and the duration of the overall procedure. This table shows that using PHT avoids one relearning process. Moreover, as in the previous example, using PHT decreases the time required for the overall procedure by 50%. This is also because the relearning procedures are performed based on relatively large datasets when PHT is not used.

Application to an industrial quality monitoring problem

In order to illustrate the applicability of this approach a real industrial case is presented. Acta-Mobilier is a company that produces high-quality lacquered panels made of medium-density fiberboard (MDF) for kitchens, bathrooms, offices, stands, shops, and hotel furniture. According to its certifications (ISO 9001, ISO 14001, and OHSAS 18001), the product quality is a constant concern for this company. The manufacturing processes are implemented on several shop floors. In these workshops, each workstation is likely to generate defects and the company has to include a quality control step in each case. In this study, we focus on a robotic lacquering workstation because it has the highest defect rate. In literature, many industrial optimization problems have been considered and we can cite without to be exhaustive, logistics infrastructure problems (Kazakov and[START_REF] Lempert | Mathematical model and program system for solving a problem of logistic objects placement[END_REF], or continuous regulation problems [START_REF] El Sehiemy | Multi-objective fuzzy-based procedure for enhancing reactive power management[END_REF][START_REF] David | Gravitational search algorithm-based design of fuzzy control systems with a reduced parametric sensitivity[END_REF]. The main objective of this application is to determine the optimal tuning of the robotic lacquering workstation in order to reduce the defects rate.

The production quality of this workstation is unpredictable (the risk of defect occurrence is unknown) and fluctuating (the percentage of defects may vary from 45% one day to 10% the next day without any changes in the settings). It is very time consuming and difficult to obtain and plan a Taguchi experimental design in order to improve this setting. Thus, a robotic lacquering workstation is considered as a bottleneck workstation, but it is very difficult to reduce the time required for the experiments or to plan throughout the production lots according to the experimental conditions. In addition, the cost of these experiments is very high because they consume semi-finished products (which already have a high added value).

Therefore, a forecasting system is implemented to predict the occurrence of defects and to determine the optimal setting of the controllable factors considering the characteristics of the products and the environmental conditions. This forecasting system should highlight the relationships between process parameters and the quality of the finished products, which may be extracted from the dataset by using a NN [START_REF] Yu | Intelligent monitoring and diagnosis of manufacturing processes using an integrated approach of KBANN and GA[END_REF][START_REF] Xiaoqiao | Research on assembly quality adaptive control system for complex mechanical products assembly process under uncertainty[END_REF].

Forecasting system

The forecasting system can be represented as shown in Figure 10. The aim is to give the operator the best production range or the best parameters to set up the machine directly. So, we need a forecasting system able to predict the risk of defect occurrence considering the characteristics of the considered products, the state of the environmental factors and the different available settings. These defect

To give to the operator the best production range to use

Environmental factors recognized as influent by experts

Lot characteristics recognized as influent by experts

List of production range available with their characteristics recognized as influent by experts

List of predictable defects

Best production range to use risk predictions allow to propose to the operator the best setting to use in the present condition. Thus, the system needs three different types of inputs, each of which requires many settings, as follows.

1. Environmental factors and lot characteristics, where there are two prerequisites. The first is the computerized production monitoring system, for which real-time production information must be collected in a semi-automated or automated manner. We do not consider that the operator has to enter data (e.g., temperature) at each production lot. The second is the virtualization of expert knowledge. A database must be implemented to consider the fact that only experts can know whether a factor is important for quality or not. 2. The list of available production range or parameter settings. In most cases, the workstation has one production range/setup according to the type of product. To obtain this high quality level, the production system needs to be flexible and adaptable. In the case where we consider different production ranges, alternative routings should be implemented. Similarly, in the case where we consider the parameter settings, adjustments to the limits of the parameters must be implemented. 3. The list of predictable defects and their criticality value. Experts can list the possible defects that may occur, but they cannot know whether a defect is actually predictable. This is one of the tasks that we discuss later in the learning step. However, experts can determine whether a defect is actually important. They need to attribute a criticality value to each possible defect according to different factors, such as the possibility of repair or the repair cost. Thus, if the system cannot find a solution with a zero defect probability, it will try to find a solution that minimizes the penalizing defects.

The forecasting system can be decomposed into two subsystems, as illustrated in Figure 11.

Figure 11 -Decomposition of the forecasting system.

The system needs to compare each production range, so we calculate a confidence level for each production range. This confidence level is obtained as shown in Figure 12 (decomposition of the "To test production range" in figure 11).

To determine best production range on each production range's confidence level To calculate the production range's confidence level, we first need to calculate the probability of occurrence for each defect. Thus, we use all of the factors validated by experts (such as environmental factors, lot characteristics, and production range characteristics) and a prediction model can be estimate for the probability of occurrence for each defect in this condition. The confidence level of production range is calculated as follows:

= ∑ × , 11
where denotes the probability of occurrence for defect with 1 ≤ ≤ , indicates the number of different defects identified by experts, and ∝ represents the criticality level of defect .

The only missing component is the probability of occurrence . This probability is given by a forecasting model built using the approach proposed in Section 2.

Implementation of the forecasting system

In this application, 25 different quality defects should be considered, thereby leading to the design of 25 quality prediction neural models. The resulting quality monitoring system (set of 25 neural classifiers) is embedded in the supervision tool of the lacquering workstation for use by the operators. The memory of these NNs is physically remote in an SQL database; therefore, each independent program may access this memory if needed. This tool is a decision support system and it requires a human/machine interface, which is as intuitive as possible. The tool is implemented directly in the setup interface of the robotic lacquering workstation (Figure 13). Using this additional function, after entering the production information (such as the selected production range and the number of units produced), the operator may assess the risk of occurrence for a defect (Figure 14). If the risk appears to be too large, the production parameters can be changed (e.g., choosing another production range) and the program can be run in parallel to compare the evaluation results until a satisfactory result is obtained.

The current version of the quality monitoring system requires an average of 12 seconds to display the result. Thus, within 12 seconds, it can recover the memory from the SQL database, traverse the 25 NNs, and visually synthesize the results to facilitate interpretation by the operator, so less than half a second is required for the calculation by the NN. Figure 13 -Interface for collecting production data. Figure 14 -Forecast example However, as expected, the answers provided by our system drift away from reality shortly after its implementation.

Design of the initial forecasting neural model

As explain in section 5.2, 25 different quality defects must be monitored leading to the design of 25 different neural forecasting models. In the sequel, we focus our presentation on one particular defect: "stain on back". The different factors which may have an impact on this defect occurrence are collected. These factors are technical factors (load factor, number of passes, time per table (lacquering batches), liter per table, basis weight, number of layers, number of products and drying time), environmental ones (as temperature, atmospheric pressure and humidity). Some of the technical factors are imposed by the products (number of passes, time per table, liter per table, number of layers, and number of products). The three last factors (load factor, basis weight, drying time) are the tunable parameters whose optimal setting is seeking. Some of these factors are discrete and are binarized. So the initial structure of the neural model includes 15 inputs (9 continuous and 6 binary) and 25 hidden neurons.

The dataset is constituted of 2270 data and is split into 2 data sets for identification (1202 data) and validation (1068 data). After initialization and learning, pruning phase is able to eliminate spurious inputs and hidden neurons. 6 hidden neurons and 1 input (passes number) are eliminated.

During the validation phase, we therefore compare the results of the NN with the real defects detection. The defect "Stains on back" occurs 127 times on the 1068 data validation set. The NN can detect 112 defects which lead to a non-detection rate of 11.8%. The proportion of false positive is 19.2%, which may be partly explained by the fact that some defects haven't been identified out of the machine (Noyel et al. 2013a).

Drift

Two apparent reasons lead our monitoring system to drift away from reality. The first concerns the evolution of the input parameters. Using a learning model, the learning outcome is valid only in the learned domain, so the model can only provide a valid solution in this domain.

Figure 15 -Difference between the learning and running domains.

For our implementation, the learning and validation databases were collected during spring and summer. For the new database (UCI 2016), 446 items of data were collected during autumn and winter, and the exploitation of the quality monitoring process led to 73% non-detections and 32% false positives for one of the 25 defects monitored. These poor results can be explained by the different process conditions in the two periods. As shown in Figure 15, in the first database, the temperature range varies between 0 C ° and 32 C °, whereas in the new database, the temperature range varies between 5.2 C -° and 24 C °. These negative temperatures represent 25%

of the new database and they correspond to the operating range of the process, which is not learned during the quality monitoring process.

Figure 16 -Historic data on the defect percentage for grains on edges.

The second reason concerns the uncontrolled modification of the machine behavior. Indeed, it is still possible to affect the behavior of the machine by changing a parameter (voluntarily or not) that is not an input of the neural classifier. For example, this parameter may change due to the clogging of a filter or the replacement of a dirty filter. These changes may or may not be known. Thus, in the application considered, we know that the lacquering nozzles are changed during the exploitation phase, but the time of this change is not known. In this case, we can conclude that this parameter should be part of the model inputs, but because it is considered constant for the duration of the learning step, it is not actually retained. The model will produce results that do not agree with reality because of this change, which may be unknown to the operators and managers.

For example, as shown in Figure 16, it is clear that the studied defect rate (grains on edges) increases sharply after June 22, which is due to an unknown change in the real system, so the forecasting system is no longer pertinent.

It is not always possible to control changes in the production parameters (such as uncontrollable parameters, weather, and unanticipated changes made by the operator), so it is necessary to be capable of detecting them. By providing the quality monitoring system with the capacity to verify its hypotheses about reality, it can have the ability to recognize its failure and react accordingly.

Therefore, a control chart is designed to monitor the forecasting system, where the sample size for the chart is fixed to 100 values, which corresponds to slightly less than one week of production.

Only the UCLs are considered because the model is better when the misclassification rate is lower. Therefore, only the UCLs are calculated to represent 95% and 99.8% of the data.

Figure 17 shows the control charts obtained with the new dataset during the exploitation phase. The dotted line corresponds to a control chart without relearning. We can see that the quality process is under control for sample 1 but the second sample shows that the process is no longer under control (the results are between UCL95% and UCL99.8%). This is due to the new operating range detected in the data, as explained in the previous section. Therefore, the quality monitoring process must be improved by relearning the NN using the data from the first two samples.

The initial structure and weights of the network are those given by the original quality monitoring process, so a pruning phase is note needed. The initial weights are close to the optimal values; therefore, the relearning phase is fast and it requires only a few iterations.

Figure 17 -Industrial application of forecast improvement by relearning.

The evolution of the control chart when no relearning is performed is shown by the dotted cyan line, relearning using PHT to determine the appropriate dataset size is represented by the dashed blue line, and relearning using all of the available data based on the last relearning process is represented by the continuous magenta line. This chart shows that relearning allows the quality monitoring process to be adapted to the new operating range. Thus, the results for sample 3 are greatly improved and the process remains under control until the end. The relearning processes with and without PHT obtain very similar results. Table 3 shows the number of relearning cycles, time, dataset size for each relearning cycle, and the duration of the overall procedure. This table shows that using PHT reduces the time required by the overall procedure by 36%. This approach allows us to determine whether the quality monitoring process needs to be adapted without systematic relearning.

All this procedure is applied in order to maintain the accuracy of the defect prediction models on the robotic lacquering workstation. These prediction models are use in a second step in order to find the optimal tuning of parameters which limits the defect risk considering the product characteristics and the environmental condition (Noyel et al. 2013a).

Conclusion

Predicting the behavior of a real system requires the use of a forecasting model that behaves in as similar manner as possible to the real system. However, drifts and shifts can rapidly create a difference between the model's behavior and reality.

Therefore, in the present study, we proposed a method for adapting a classification neuronal model to this particular changing context by using control charts and PHT. The main goal is to keep under control the misclassification rate in order to maintain the model close to the reality. This novel hybrid system allows us to reduce the time required because of the following two reasons: the relearning process is not systematic and it is triggered only when a drift is finally detected; and the relearning process is not performed based on all of the available data, but instead it only uses the data that reflect the drift. Thus, we proposed a model monitoring approach, which aims to detect drifts and shifts between reality and the forecasting model. We tested this method based on a benchmark case and the results were promising. The results obtained for the industrial quality monitoring problem demonstrate that the process can be brought under control after adapting the model. These results based on the management of quality indirectly influence the management of flows in the system.

This approach tends to adapt the model when each drift is detected. However, in some cases, a drift may be a symptom of a process failure, so the process (and not the model) must be repaired. In our future research, we will try to determine whether the process or the model should be corrected when a drift occurs.

hx

  denote the n0 inputs of the MLP, 1 ih w indicate the weights connecting the input layer to the hidden layer, 1 i b represent the biases of the hidden neurons, g1(.) refers to the activation function of the hidden neurons (in this case, the hyperbolic tangent), 2 i w denote the weights connecting the hidden neurons to the output, b

  Figure 6 -Control chart for monitoring the real-time forecasting model.

Figure 7 -

 7 Figure 7 -The validation dataset divided into two classes and the limits between the two classes.

Figure 8 -

 8 Figure 8 -Monitoring the forecasting model: concept shift.

Figure 9 -

 9 Figure 9 -Monitoring the forecasting model: concept drift.

Figure 10 -

 10 Figure 10 -Forecasting system.

Figure 12 -

 12 Figure 12 -Details of the production range's confidence level module.

  T and the means of the two normal distributions for the negative population become (2 + 0.02*(k -300), 2) T and (-2 + 0.02*(k -300), -2) T , where k denotes the index of the data. The covariance matrix remains unchanged.

	rate Misclassification 0)									Relearning without PHT Relearning with PHT Without relearning
	0.25
	0.2
		UCL 99.8%
	0.15	UCL 95%
	0.1
	CL
	0.05
		LCL 95%
	0	LCL 99.8%
	1 -0.05	3	5	7	9	11	13	15	17	19	sample
		number of relearning time to relearning size of the dataset duration
					400			400
	without PHT			1000		600		0.35s
					1800		800
					400			143
	with PHT				1100 1400		141 209		0.17s
					2000		339

Table 2 -

 2 Number, dataset size, time, and duration of relearning: concept drift.

	Misclassification
	0.5 rate		Relearning without PHT Relearning with PHT Without relearning
	0.4
	0.3
	0.2	UCL 99.8%
	CL 0.1	UCL 95%
	0	LCL 99.8% LCL 95%
	1 -0.1	3	5	7	9	11	13	15	17	19	sample

Table 3 -

 3 Number, dataset size, time, and duration of relearning: industrial example.

	Misclassification
	rate		Without relearning
			Relearning with PHT
	0.35		Relearning without PHT
	0.3	UCL 99.8%
		UCL 95%
	0.25
	0.2
	CL
	0.15
	0.1	LCL 95%
		LCL 99.8%
	1 0.05	2		3	sample
		number of relearning time to relearning size of the dataset duration
	without PHT	1	200	200	0.22s
	with PHT	1	200	101	0.14s


Michel Leclère

Marie-Laure Mugnier

Federico Ulliana

On Bounded Positive Existential Rules

We consider the existential rule framework, which generalizes Horn description logics. We study and compare several boundedness notions in this framework. Our main result states that (strongly-) bounded rules are exactly those at the intersection of two well-known abstract classes of existential rules, namely fes (finite expansion sets, which ensure the finiteness of the core chase) and fus (finite unification sets, which correspond to UCQ-rewritable rules).

Introduction

Existential rules [START_REF] Baget | Extending decidable cases for rules with existential variables[END_REF][START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF][START_REF] Krötzsch | Extending decidable existential rules by joining acyclicity and guardedness[END_REF] are a fragment of first-order logic generalizing most ontological languages studied in ontology-mediated query answering (OMQA), in particular Horn description logics [START_REF] Calvanese | DL-Lite: Tractable description logics for ontologies[END_REF][START_REF] Krötzsch | Complexity boundaries for Horn description logics[END_REF][START_REF] Lutz | Conjunctive query answering in the description logic EL using a relational database system[END_REF]. In the OMQA setting, databases (or fact bases) are added with an ontological layer, which allows to deduce new facts from incomplete datasources, thereby enriching answers to database queries.

As OMQA can be directly implemented on top of relational database systems, many research efforts have been devoted to make the paradigm efficient. At the core of the techniques developed for existential rules, and to some extent for Horn description logics, we find the two classical paradigms for processing rules, namely forward chaining and backward chaining. In the OMQA setting, both approaches are recast as ways of reducing the problem to a classical database query answering problem, by embedding the rules into the facts or into the query. Forward chaining is decomposed into a materialization step (applying the rules to the data, hence materializing inferences into the data) followed by the evaluation of the query against the enriched database. Backward chaining is decomposed into a query rewriting step (rewriting the query using the rules) followed by the evaluation of the rewritten query against the database, thereby leaving the data untouched.

Both approaches rely on a fixpoint operator to cope with rule semantics. Indeed, materialization should continue until the point where only redundant facts are added to the dataset, while rewriting should continue until the point where only redundant queries are added to the rewriting set. It is understood that both processes may not terminate since entailment with existential rules is undecidable (e.g., [START_REF] Chandra | The implication problem for functional and inclusion dependencies is undecidable[END_REF]). Deciding halting of these processes is undecidable as well [START_REF] Deutsch | The chase revisited[END_REF][START_REF] Baget | Walking the decidability line for rules with existential variables[END_REF]. Following the terminology introduced in [START_REF] Baget | Walking the decidability line for rules with existential variables[END_REF], we say that a set of existential rules is a finite expansion set (fes) if it ensures that a finite sound and complete materialization can be computed for any fact base, and a finite unification set (fus) if it ensures that any conjunctive query can be rewritten into a finite sound and complete set of conjunctive queries (such a set being seen as a union of conjunctive queries). As concrete examples of fes rules, one can cite (plain) datalog [START_REF]Foundations of Databases: The Logical Level[END_REF] and sets of rules satisfying various acyclicity conditions [START_REF] Grau | Acyclicity notions for existential rules and their application to query answering in ontologies[END_REF][START_REF] Baget | Extending acyclicity notions for existential rules (long version)[END_REF]. Some prominent classes of fus rules are linear rules (which generalize some DL-Lite dialects [START_REF] Calvanese | DL-Lite: Tractable description logics for ontologies[END_REF][START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF]), sticky rules [START_REF] Calì | Query answering under non-guarded rules in datalog+[END_REF] and more generally rules with the "backward shyness" property [START_REF] Thomazo | Conjunctive Query Answering Under Existential Rules -Decidability, Complexity, and Algorithms[END_REF]. Note that [START_REF] Baget | Walking the decidability line for rules with existential variables[END_REF] defines a third property ensuring decidability of OMQA, namely bounded-treewidth sets (which contains EL [START_REF] Lutz | Conjunctive query answering in the description logic EL using a relational database system[END_REF] and the family of guarded rules [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF][START_REF] Baget | Walking the complexity lines for generalized guarded existential rules[END_REF]), however this class is out of the scope of this paper.

To fes (resp. fus) rules is naturally associated a finite breadth-first materialization (resp. query rewriting) process, whose maximal number of steps generally depends not only on the set of rules but also on the data (resp. on the input query). In contrast, bounded rules are exactly those rules that can be evaluated without a fixpoint operator. A set of rules is said to be bounded if breadth-first materialization computes all consequences from a knowledge base (composed of a fact base and the rules) in a predefined number of steps k. More precisely, there is k independent from any fact base, such that the materialization of any fact base at step k > k is equivalent to that obtained at step k. As relational database systems may lack a fixpoint operator (see for example MySQL), bounded rules form an interesting intersection point between databases and ontologies, because they can be seamlessly evaluated on any relational system, which is not the case in general.

The goal of this work is to further investigate the properties of bounded existential rules, in particular the precise relationships between fes, fus and bounded sets of rules.

Our contributions are more precisely the following:

1. We first define a breadth-first query rewriting technique which is precisely the dual of breadth-first materialization. Let K = (F, R) be any knowledge base, where F is a fact base and R a set of existential rules, and let q be a (Boolean) conjunctive query. From earlier work on existential rules, we know that K entails q iff there is k (depending on R and F ) such that F k , the saturation of F at step k, entails q (e.g., [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF][START_REF] Baget | On Rules with Existential Variables: Walking the Decidability Line[END_REF]); equivalently, K entails q iff there is k (depending on R and q) such that F entails Q k , the set of rewritings of q obtained at step k (see [START_REF] König | Sound, complete and minimal ucqrewriting for existential rules[END_REF][START_REF] Gottlob | Query rewriting and optimization for ontological databases[END_REF] for practical algorithms). We define a variant of the breadth-first query rewriting technique from [START_REF] König | Sound, complete and minimal ucqrewriting for existential rules[END_REF] that fulfills the following property: for any i ≥ 0, F i entails q iff F entails Q i (Theorem 1), hence k = k in the above sentence. 2. We point out that boundedness can also be defined in terms of query rewriting instead of materialization, and using Theorem 1, we obtain the same bound for both definitions: for any k, it holds that F k is equivalent to F k+1 for all F iff it holds that Q k is equivalent to Q k+1 for all q (Theorem 2). We also show that the notion of "bounded-depth derivation property" introduced in [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF] is equivalent to fus, and define variants of this property corresponding to fes and boundedness respectively. 3. By definition, every bounded set of rules is both fes and fus. The question of whether the reciprocal statement holds was open. We show that, indeed, bounded rules are exactly those at the intersection of fes and fus (Theorem 3).

Preliminaries

We consider a first-order setting with constants but no other function symbols. A term is either a constant or a variable. In the examples we will denote constants by letters at the beginning of the alphabet (a, b, ...,) and variables by letters at the end of the alphabet (v, w, x, y, z). An atom is of the form p(t 1 , . . . , t k ) where p is a predicate of arity k and the t i are terms. Given an atom or set of atoms A, vars(A), consts(A) and terms(A) denote its set of variables, constants and terms, respectively. We denote by |= the classical logical consequence and by ≡ the logical equivalence. Given two sets of atoms A and A , a homomorphism h from A to A is a substitution of vars(A) by terms(A ) such that h(A) ⊆ A . If there is a homomorphism h from A to A , we say that A maps to A (by h), which is also denoted by A ≥ A . It is convenient to extend any substitution s to unchanged terms (we set s(t) = t for all considered constants and unchanged variables).

A fact is an existentially closed conjunctions of atoms. We denote by F a fact base, that is a set of facts. Since a conjunction of facts is equivalent to a single fact, we also see a fact base as an existentially closed conjunction of atoms. A Boolean conjunctive query (in short CQ) is also an existentially closed conjunction of atoms. Next, fact bases and conjunctive queries will be seen as sets of atoms. The answer to a CQ q in a fact base

F is true iff F |= q. It is well known that F |= q iff q ≥ F . A union of conjunctive queries (UCQ) Q = q 1 ∨ q 2 . . . ∨ q n is seen as a set of CQs Q = {q 1 , . . . , q n }. The answer to Q in F is true iff F |= Q, i.e., F |= q i for some q i ∈ Q. An existential rule r = ∀x, y(B [x, y] → ∃z H [x, z]
) is a closed formula where B is a conjunction of atoms constituting the body of the rule, H is a conjunction of atoms for the head of the rule, x and y are sets of universally quantified variables, and z is the set of existentially quantified variables of the rule. The variables in x, i.e., those shared by B and H , are called the frontier variables of the rule. In the following we will refer to a rule as a pair of sets of atoms (B , H ), interpreting their common variables as the frontier. In the examples, we will use the simplified notation B → H , for instance the rule ∀x(q(x) → ∃y (p(x, y) ∧ q(y))) will be written q(x) → p(x, y), q(y). A set of rules is denoted by R. We implicitly assume that all rules employ disjoint sets of variables. A knowledge base (KB) K = (F, R) is a pair where F is a fact base and R is a set of rules. The conjunctive query entailment problem consists in deciding for given KB K and CQ q whether K |= q (where K is seen as the first order theory associated with F ∪ R). It has long been shown that this problem is undecidable (this follows e.g., from [START_REF] Chandra | The implication problem for functional and inclusion dependencies is undecidable[END_REF]).

A rule r = (B , H ) is applicable to a fact base F if there is a homomorphism h such that h(B ) ⊆ F . The application of r to F with respect to a homomorphism h is denoted by α(F, r, h) and defined as α(F, r, h) = F ∪ h safe (H ) where h safe is a safe extension of h to H , i.e., it substitutes existential variables from H with fresh variables (not used elsewhere). It holds that F, R |= q iff there is a fact base F derived from F with rules in R,1 such that F |= q.

We now define fact materialization by (breadth-first) forward chaining, a useful tool, also known as saturation or (breadth-first) chase. 2 The one-step saturation of F with R, denoted by α(F, R), is defined as α(F, R) = F ∪ (r,h) h safe (H) for all r = (B, H) ∈ R and h homomorphism from B to F . The k-saturation of F with R, denoted by α k (F, R), is inductively defined as follows: α 0 (F, R) = F and, for any

k > 0, α k (F, R) = α(α k-1 (F, R), R).
Next, when R is fixed, we will denote the set α k (F, R) by F k . Saturation is sound and complete, i.e., for all F , R and Q, F, R |= Q iff F k |= Q for some positive integer k (see e.g., [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF][START_REF] Baget | On Rules with Existential Variables: Walking the Decidability Line[END_REF]). A set of rules R is said to be a fes (finite expansion set) if for all fact base F there exists a positive constant k such that [START_REF] Baget | Extending decidable cases for rules with existential variables[END_REF]. Note that k generally depends on F . It follows that when R is fes, the saturation process is finite, hence it can be used to decide if F, R |= Q. The following example illustrate the fes property.

F k |= F k+1 (hence F k ≡ F k+1 )
Example 1 (fes). Let K = (F, R) with F = {p(a, b)} and R = {r : p(x, y) → p(y, z), p(z, y)}. Then F 0 = F , F 1 = F ∪ {p(b, z 0 ), p(z 0 , b)}, F 2 = F 1 ∪ {p(z 0 , z 1 ), p(z 1 , z 0 ) , p(b, z 2 ), p(z 2 , b) , p(b, z 0 ), p(z 0 , b)} (the
rule applications corresponding to homomorphisms already found at the preceding step are written in gray font, next we will omit them). We have F 2 ≡ F 1 (note that there is no k such that F k = F k+1 , even by considering only new homomorphisms at each step, which shows the importance of checking equivalence and not only equality). Actually it holds that F 2 ≡ F 1 for any F , hence R is fes (and even bounded, see Sect. 4). Let us consider R = {r : p(x, y) → p(y, z)}.

Then F 0 = F , F 1 = F ∪ {p(b, z 0 )}, F 2 = F 1 ∪ {p(z 0 , z 1 ), p(b, z 2 )} and so on. There is no k such that F k ≡ F k+1 , hence R is not fes.
Backward chaining is a dual approach to deciding conjunctive query entailment, which involves rewriting the input query using the rules. The key operation is unification between (a subset of) a query and (a subset of) a rule head, which requires particular care due to the presence of existential variables in the rules. For this reason, we use the notion of a piece-unifier (introduced in [START_REF] Baget | Extending decidable cases for rules with existential variables[END_REF]). Given a subquery q ⊆ q, we call separating variables of q the variables occurring in both q and (q \ q ); the other variables from q are called non-separating. The definition of piece-unifier below ensures that, q being the unified part of q, only non-separating variables from q can be unified with an existential variable of the rule.

Definition 1 (Piece Unifier) Let q be a query and r = (B , H ) a rule. A piece-unifier of q with r is a triple µ = (q , H , u) where q = ∅, q ⊆ q, H ⊆ H , and u is a substitution of T = terms(q ∪ H ) by T such that (i) u(q ) = u(H ) and (ii) for all existential variable x ∈ vars(H ) and t ∈ T , with t = x, if u(x) = u(t), then t is a non-separating variable from q .

Given a CQ q, a rule r = (B , H ) and a piece-unifier µ = (q , H , u) the direct rewriting of q with r and µ, denoted by β(q, r, µ), is the CQ u safe (B ) ∪ u(q \ q ), where u safe is a safe extension of u to B substituting variables in vars(B ) \ vars(H ) with fresh variables.

Example 2 (Piece Unifier). Let r = r(x) → p(x, y) and q 1 = {p(w, v), s(v)}. There is no piece-unifier of q 1 with r since, with q 1 = {p(w, v)}, v is a separating variable of q 1 , hence cannot be unified with the existential variable y. Let q 2 = {s(z), p(z, v), p(w, v), t(w)}. The triple µ = (q , H , u) with q = {p(z, v), p(w, v)}, H = {p(x, y)} and u = {x → z, y → v, w → z} is a piece-unifier of q 2 with r, which yields the direct rewriting {r(z), s(z), t(z)}.

It holds that F, R |= q iff there is a rewriting q of q with rules in R, 3 such that F |= q . A set of rewritings Q of q (with R) is said to be sound and complete if for any F it holds that F, R |= q iff there is q ∈ Q such that F |= q . When Q is finite it can be seen as a UCQ, hence the previous condition can then be recast as follows: F, R |= q iff F |= Q. The set R is said to be fus (finite unification set) if for any q, there is a finite sound and complete set of rewritings of q with R [START_REF] Baget | Extending decidable cases for rules with existential variables[END_REF][START_REF] König | Sound, complete and minimal ucqrewriting for existential rules[END_REF].

Similarly in spirit to saturation, one can consider breadth-first query rewriting: starting from the UCQ Q = {q}, at each step we compute all the direct rewritings of CQs in the current UCQ. Formally: the one-step rewriting of a UCQ Q with R is β(Q, R) = Q ∪ (q,r,µ) {β(q, r, µ)} where q ∈ Q, r ∈ R and µ is a piece-unifier of q with r. Then, the (breadth-first) k-rewriting of Q with R, denoted by β k (Q, R), is inductively defined as follows:

β 0 (Q, R) = Q, and for all k > 0, β k (Q, R) = β(β k-1 (Q, R), R).
It holds that F, R |= q iff F |= β k ({q}, R) for some positive integer k (follows from [START_REF] Baget | On Rules with Existential Variables: Walking the Decidability Line[END_REF]). This property yields an alternative characterization of fus: a set of rules is fus iff for all q, there is k such that β k ({q}, R) ≡ β k+1 ({q}, R). 4Example 3 (fus).

Let r = p(x, y), p(y, z) → p(z, t). Let q = {p(v, a)}, where a is a constant: since t is an existential variable, there is no piece-unifier of q with r. Let q = {p(a, v)}. β 1 ({q }, {r}) = {q } ∪ {{p(x 0 , y 0 ), p(y 0 , a)}}; β 2 ({q }, {r}) = β 1 ({q }, {r}) ∪ {{p(x 0 , y 0 ), p(y 0 , a)}}, where the last CQ corresponds to the piece-unifier already found in the preceding step. Hence, β 2 ({q }, {r}) = β 1 ({q }, {r}) if we restrict the computation to new piece-unifiers. Finally, let q = {p(v, w)}. β 1 ({q}, {r}) = {q} ∪ {q 1 = {p(x 0 , y 0 ), p(y 0 , v)}}. β 2 ({q}, {r}) = β 1 ({q}, {r}) ∪ {{p(x 1 , y 1 ), p(y 1 , y 0 ), p(x 0 , y 0 )}} (we consider only new piece-unifiers). Since existential variables can only be unified with non-separating variables, there is only one new piece-unifier ({p(x 0 , v)}, {p(z, t)}, {z → y 0 , t → v}), which yields q 1 . β 3 ({q}, {r}) = β 2 ({q}, {r}) ∪ {{p(x 2 , y 2 ), p(y 2 , y 1 ), p(x 1 , y 1 )}}, where the new the piece-unifier is ({p(x 0 , y 0 ), p(y 1 , y 0 )}, {p(z, t)}, {z → y 1 , x 0 → y 1 , t → y 0 }). And so on. There is no k such that β k = β k+1 (up to bijective variable renaming), however any UCQ β i is equivalent to q. As these examples suggest it, {r} is indeed fus.

Note that there is k such that F |= β k ({q}, R) if and only if there is k such that α k (F, R) |= q. However, the above breadth-first rewriting is not exactly the dual of breadth-first saturation, in the sense that α(F, R) |= q does not imply F |= β({q}, R). In other words, a single step of breadth-first rewriting is not able to "simulate" a step of saturation. Let us illustrate this observation with a simple example.

Example 4 (Saturation vs rewriting step). Let K = (F, R) with F = {p 0 (a), q 0 (a)} and R = {r p : p 0 (x) → p 1 (x); r q : q 0 (x) → q 1 (x)}. Let q = {p 1 (u), q 1 (u)}. A single saturation step α(F, R) = {p 0 (a), q 0 (a), p 1 (a), q 1 (a)} allows to entail q. However, a single rewriting step β 1 ({q}, R) = {{p 1 (u), q 1 (u)}, {p 0 (u), q 1 (u)}, {p 1 (u), q 0 (u)}} does not allow to prove that K |= q, i.e., F |= β 1 ({q}, R). The trouble is that each direct rewriting is performed with respect to a single rule, hence the desired CQ {p 0 (u), q 0 (u)}, which requires to rewrite q with both r p and r q , is obtained only at the second rewriting step (from {p 0 (u), q 1 (u)} or from {p 1 (u), q 0 (u)}).

A New Breadth-First Query Rewriting

In order to obtain the precise dual of saturation, we define another breadth-first rewriting mechanism able to unify a CQ with several rules from R at once. Instead of a piece-unifier, we consider an "aggregated unifier" (as introduced in [START_REF] König | On the exploration of the query rewriting space with existential rules[END_REF] for algorithmic purposes), which aggregates several piece-unifiers of a CQ with rules from R, provided that these piece-unifers are compatible (briefly, they involve disjoint subsets of the query and unify common variables in a way that does not lead to unify different constants together). To avoid technical developments, we will consider here an alternative way of defining exactly the same kind of rewriting by modifying the set of rules instead of the unifier (this alternative definition is not practically relevant but it is suitable for our study).

Let R = {r 1 , . . . , r l } be a set of rules with each r i = (B i , H i ). We recall that distinct rules have disjoint sets of variables. The aggregated rule assigned to R , denoted by r 1 . . . r l , is defined as B 1 ∧ . . . ∧ B l → H 1 ∧ . . . H l . Let R be the (infinite) set of aggregated rules assigned to multisubsets of R (i.e., an aggregated rule may involve several "copies" of the same rule from R, with a safe renaming of variables in each copy).

Then, for any UCQ Q, β (Q, R) = Q ∪ (q,r,µ) {β(q, r, µ)}, where q ∈ Q, r = r 1 . . . r l ∈ R with l ≤ |q|, and µ is a piece-unifier of q with r. We denote by β k (Q, R) the associated breadth-first k-rewriting. 5Example 5. Consider again Ex. 4. We have β 1 ({q}, R) = β 1 ({q}, R)∪{{p 0 (u), q 0 (u)}}, where the additional query is obtained by unifying q with the aggregated rule r 1 r 2 = p 0 (x 0 ), q 0 (x 1 ) → p 1 (x 0 ), q 1 (x 1 ).

We now prove that the new breadth-first rewriting fulfills the desired properties.

Lemma 1 For all F, R and q, it holds that α(F, R)|= q iff F |=β ({q}, R).

Proof:(Sketch) (⇒) Let F 1 = α(F, R). As F 1 |= q there is h such that h(q) ⊆ F 1 . Let q 0 be the largest subset of q such that h(q 0 ) ⊆ F and {q 1 , . . . , q l } be the partition of q \ q 0 such that each q i (0 < i ≤ l) maps to the atoms produced by the application of a rule r i = (B i , H i ) ∈ R to F with a homomorphism h i , i.e., h(q i ) ⊆ h safe i (H i ) (and F ∪ h safe 1 (H 1 ) ∪ . . . ∪ h safe l (H l ) ⊆ F 1 ). For each i > 0, let H i ⊆ H i denote the useful part of H i , i.e., h(q i ) = h safe i (H i ). If q 0 = q, i.e., F |= q, then F |= β ({q}, R) since q ∈ β ({q}, R). Otherwise, let r = r 1 . . . r l and µ be the piece-unifier of q with r naturally associated with the homomorphisms h and h 1 ∪ . . . ∪ h l (i.e., µ = (q 1 ∪ . . . ∪ q l , H 1 ∪ . . . ∪ H l , u) where for all terms e and e in the domain of

u, u(e) = u(e ) iff (h ∪ h safe 1 ∪ . . . ∪ h safe l )(e) = (h ∪ h safe 1 ∪ . . . ∪ h safe l
)(e )). We easily check that F |= β(q, r , µ). Since β(q, r , µ) ∈ β ({q}, R), we obtain that F |= β ({q}, R).

(⇐) If F |= q then α(F, R) |= q. Otherwise, we know there is q 1 = q in β 1 ({q}, R) s.t. F |= q 1 where q 1 is obtained by rewriting q ⊆ q with an aggregated rule r = r 1 . . . r l and a piece-unifier (q , H 1 ∪ . . . ∪ H l , u). Let h be a homomorphism from q 1 to F . For each

r i = (B i , H i ) composing r , h • u safe is a homomorphism from B i to F . Hence, (h • u) safe (H i ) ⊆ α(F, R).
We build the following homomorphism h from q to α(F, R): for all x ∈ vars(q), if x ∈ vars(q) \ vars(q ) then h(x) = h (x), otherwise, let any e ∈ H i such that u(x) = u(e), then h(x) = (h • u safe ) safe (e).

Theorem 1. For all F, q, R and k ≥ 0, it holds that

α k (F, R)|= q iff F |=β k ({q}, R) Proof:
The proof is by induction on k. For k = 0, the property is trivially true. Assume the property holds for any k < n. First note that, for any i ≥ 1,

α i (F, R) = α i-1 (α(F, R), R) and β i ({q}, R) = β i-1 (β ({q}, R), R
), which directly follows from the definitions. We have

α n (F, R)|= q iff α n-1 (α(F, R), R)|= q iff α(F, R)|=β n-1 ({q}, R) (by induction hypothesis) iff F |=β (β n-1 ({q}, R), R) (by Lemma 1) iff F |=β n ({q}, R). Hence, α k (F, R)|= q iff F |=β k ({q}, R) holds for any k ≥ 0.
This correspondence between α k and β k allows us to rely on the soundness and completeness of breadth-first forward chaining to establish the soundness and completeness of breadth-first rewriting:

Corollary 1. It holds that F, R |= q iff F |= β k ({q}, R) for some positive integer k.

Breadth-first rewriting yields an alternative definition of fus.

Proposition 1 A set of rules R is fus iff for all query q there is a positive constant k such that β k ({q}, R) ≡ β k+1 ({q}, R).

From now on, for a UCQ Q and a fixed set of rules R, we will denote the set

β k (Q, R) simply by Q k .

Several Notions of Boundedness

We now define bounded rules and clarify their relationships with other properties found in the literature. Two meaningful notions of boundedness can be provided, with the bound being based on fact saturation or on query rewriting.

Definition 2 A set of existential rules R is (saturation-bounded) if there exists k ∈ N such that for all F , F k ≡ F k+1 . (rewriting-bounded) if there exists k ∈ N such that for all Q, Q k ≡ Q k+1 .
We first show that these two notions precisely coincide. Theorem 2. Any set of existential rules R is saturation-bounded iff it is rewritingbounded. Moreover, the bound is the same, i.e., for all F and all Q, for all k,

F k ≡ F k+1 iff Q k ≡ Q k+1 .
Proof: (⇒) Assume that R is saturation-bounded and let k be the bound. Then for all Q and F it holds that

F, R |= Q iff F k |= Q. Let q be any query in Q k+1 . Since q |= Q k+1 , by soundness of rewriting, it holds that q, R |= Q; since R is saturation- bounded, {q} k |= Q hence, by Th. 1, q |= Q k . Since this holds for any query q ∈ Q k+1 , we have Q k+1 |= Q k . Furthermore, by definition, Q k |= Q k+1 . Thus Q k ≡ Q k+1 .
(⇐) Assume that R is rewriting-bounded and let k be the bound. Then for all Q and F it holds that

F, R |= Q iff F |= Q k . By soundness of forward chaining, it holds that F, R |= F k+1 ; since R is rewriting-bounded, F |= (F k+1 ) k hence, by Th. 1, F k |= F k+1 . Furthermore, by definition, F k+1 |= F k . Thus F k ≡ F k+1 .
In light of this, next we will simply say bounded rules. In [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF], Calì et al. introduced the notion of bounded-depth derivation property for existential rules, for which the number of saturation steps is bounded for all query (in short, Q-BDDP). We define the analogous of the bounded-depth derivation property for facts (F-BDDP), as well as a natural property issued from both from (Q-BDDP) and (F-BDDP), we call strong bounded-depth derivation property (strong BDDP). We show that these three properties coincide with the classes fus, fes and bounded. Definition 3 (Bounded-Derivation Properties) Let R be a set of existential rules. Then, R enjoys the property

(F-BDD) if for all F there is k ∈ N such that for all Q: F, R |= Q iff F k |= Q (Q-BDD) if for all Q there is k ∈ N such that for all F : F, R |= Q iff F k |= Q (strong BDD) if there is k ∈ N such that for all F and Q: F, R |= Q iff F k |= Q.
We now show that these notions respectively correspond to fes, fus and boundedness. 6Proposition 2 Any set of existential rules is fes iff it has the F-BDD Property.

Proof: (⇒) Let R be fes: for all F , there is k such that F k ≡ F k+1 . By soundness and completeness of forward chaining, for any Q we have F, R |= Q iff there is n such that F n |= Q. For any F and such n, it holds that F k |= F n . Hence, F k |= Q.

(⇐) Assume R has the F-BDD Property and set Q = {F k+1 } (where k is the bound of the F-BDD Property). We thus have

F, R |= F k+1 iff F k |= F k+1 . Forward chaining is sound, so F, R |= F k+1 . Hence F k |= F k+1 . By definition, F k+1 |= F k . Therefore, F k ≡ F k+1 .
Proposition 3 Any set of existential rules is fus iff it has the Q-BDD Property.

Proof: (⇒) Let R be fus: for all Q, there is k such that Q k ≡ Q k+1 . By soundness and completeness of breadth-first rewriting (Corollary 1), for any F , we have

F, R |= Q iff F |= Q k . Equivalently, by Th. 1, F k |= Q. (⇐) Assume R has the Q-BDD Property.
For any q ∈ Q k+1 (where k is the bound of the Q-BDD Property), let us set F = q: we have q, R |= Q iff (q) k |= Q. Breadth-first rewriting is sound, so q, R |= Q. Hence q |= Q k . Since this holds for any q ∈ Q k+1 , we have

Q k+1 |= Q k . Since Q k is included in Q k+1 , we also have Q k |= Q k+1 . Therefore, Q k ≡ Q k+1 .
Proposition 4 Any set of existential rules is bounded iff it has the strong BDD Property.

Proof: The proof goes like that of Prop. 2.

(⇒) Let R be saturation-bounded and let k such that for all F , F k ≡ F k+1 . By soundness and completeness of forward chaining, for any F and Q, we have

F, R |= Q iff F k |= Q.
(⇐) Assume R has the strong BDD Property and set Q = {F k+1 } (where k is the bound of the strong BDD Property). We thus have F, R |= F k+1 iff F k |= F k+1 . Forward chaining is sound, so F, R |= F k+1 . Hence F k |= F k+1 . By definition, F k+1 |= F k . Therefore, F k ≡ F k+1 .

Boundedness = fes ∩ fus

We now prove that bounded rules are exactly those at the intersection of fes and fus classes.

Theorem 3. R is fes and fus iff R is bounded.

One direction of the proof (⇐) is straightforward, and follows by Prop.s 2 and 3, simply picking the k of the bound. We dedicate the remaining of this section to the formal development of the other direction. We first consider the set of all objects of the form ( B , H ) where B is a rewriting of a rule body in R and H is the saturation of B with R. When R is fes, such objects correspond to rules (i.e., each H can be made finite). When moreover R is fus, the set of all rewritings to be considered is finite, hence the set of all rules of interest is finite. Definition 4 (Rule Completion) Let R = {r 1 , . . . , r n } be a fes and fus set of rules of the form r i = (B i , H i ). We define the set C R as follows:

1. For any r i = (B i , H i ), let k i be the smallest integer such that β ki (B i , R) ≡ β ki+1 (B i , R) (such a k i exists since R is fus). 2. For any q ij ∈ β ki (B i , R), let k ij be the smallest integer such that α ki j (q ij , R) ≡ α ki j +1 (q ij , R) (such a k ij exists since R is fes).

3. Then:

C R = {( B , H ) | r i = (B i , H i ) ∈ R, B ∈ β ki (B i , R), H = α ki j ( B , R) } The bound associated with R is d R = max ri∈R,qi j ∈β k i (Bi,R) (k ij ).
Note that C R is finite and unique (up to bijective variable renaming). Most importantly, its size depends solely on R.

Proposition 5 For any fes and fus set of rules R, it holds that C R ≡ R.

Proof: The direction C R |= R holds since, for each rule r i = (B i , H i ) ∈ R, B i ∈ β ki (B i , R), hence there is a rule r = ( B , H ) ∈ C R with B i = B and H i ⊆ H . Direction R |=C R
follows from the soundness and completeness of saturation. Indeed, for each rule ( B , H ) ∈ C R , let ( B , H ) be obtained by replacing each frontier variable with a distinct fresh constant (i.e., that does not occur in R). By definition of C R , we have B , R |= H , and equivalently R |= B → H . We now show that each saturation step with C R can be computed by a bounded number of saturation steps with R (again with a bound independent from any fact base, Prop. 6). Next, we will show that a single saturation step with C R is actually sufficient to saturate any fact base (Prop. 7), therefore it is equivalent to a bounded number of saturation steps with R. Proof: (Sketch) Let F = α d R (F, R). We show that for each rule r = ( B , H ) ∈ C R and each homomorphism h from B to F , F |= α(F, r, h) holds, which suffices to prove that F |= α(F, C R ) since all rules are applied "in parallel" in a single saturation step. Consider the sequence S of rule applications leading from B to H . The choice of d R implies that α d R ( B , R) ≡ H . Let h from B to F . The sequence S can be applied "similarly" to F (i.e., each homomorphism h i associated with a rule application is replaced by h

•h i ), yielding S(F ) with S(F ) |= h( H ). Since H is obtained in at most d R breadth-first steps, this is also true for S(F ), hence F |= S(F ). Since F ⊆ F , we obtain F |= F ∪ h safe ( H ) = α(F, r, h).
Proposition 7 Let R be a set of rules both fes and fus. For any fact base F , it holds that α(F, C R ) ≡ α k (F, C R ) for all k≥1.

Proof: (Sketch) We focus on proving that α(F, C R ) |= α(α(F, C R ), R) which suffices to derive the thesis. Indeed, we know that for any F and R if F |= α(F , R ) then

F |= α k (F , R ), for all k ∈ N. Hence α(F, C R ) ≡ α k (α(F, C R ), R), in particular for k = d R .
Moreover, as R is both fes and fus by Prop. 6 we have that α

(F, C R ) |= α(α(F, C R ), C R ).
Let r = (B , H ) be any rule of R. If r is applicable to α(F, C R ) with a homomorphism h, then h(B ) ⊆ α(F, C R ). By Prop. 6 we thus have α d R (F, R) |= h(B ). By Th. 1, we get that F |= β d R ({h(B )}, R), so there exists h(B ) rew ∈ β d R ({h(B )}, R) such that F |= h(B ) rew . Any rewriting sequence from h(B) to h(B ) rew can be performed "similarly" from B yielding B rew ∈ β d R ({B }, R) with B rew ≥ h(B ) rew . Besides, by definition of C R , we know there exists r = ( B , H ) ∈ C R with B = B rew and H ≡ α d R (B rew , R). We show that any derivation sequence from B to H can be applied to h(B ) rew to entail h(B ). Since r = (B , H ) ∈ R and this sequence is applied until saturation, h(H ) is also entailed. We conclude that α(F, C R ) |= h(H ).

Proof: [Proof of Th. 3] We now prove that if R is fes and fus then it is bounded.

For any fact base F and any CQ q, F, R |= q iff F, C R |= q (Prop. 5). From Prop. 7, F, C R |= q iff α(F, C R ) |= q. Hence, F, R |= q iff α(F, C R ) |= q. It remains to show that there is k independent from F and q such that α k (F, R) ≡ α(F, C R ). From Prop. 6, we have a constant k (k = d R ) independent from F and q such that α k (F, R) |= α(F, C R ); moreover, since F, R |= α k (F, R) for any k, we have α(F, C R ) |= α k (F, R). We conclude that R is bounded.

Concluding Remarks

In this paper, we provide several results that clarify the relationships between fundamental properties of existential rule sets, namely fes, fus and boundedness. The main result is that bounded rule sets are exactly those that are both fes and fus.

Recognizing if a set of rules is bounded is a difficult problem, which is already undecidable for plain datalog [START_REF]Foundations of Databases: The Logical Level[END_REF], hence for many fes classes of existential rules. A significant exception are monadic datalog programs, for which boundedness is recognizable [START_REF] Cosmadakis | Decidable optimization problems for database logic programs (preliminary report)[END_REF]. An open question is whether boundedness is recognizable for specific classes of existential rules, in particular those known to be fus. Whether restricting predicate arity to two could have an impact on the problem decidability is also an interesting issue.

Besides, the halting condition for the saturation process considered here relies on logical equivalence (i.e., F k ≡ F k+1 ). This condition corresponds exactly to the halting of the chase variant known as the core chase [START_REF] Deutsch | The chase revisited[END_REF]. Other chase variants have been proposed in the literature, in particular the restricted chase [START_REF] Beeri | A proof procedure for data dependencies[END_REF], the skolem chase [START_REF] Marnette | Generalized schema-mappings: from termination to tractability[END_REF] and the oblivious chase [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF], which are known to halt in (increasingly) fewer cases (see, e.g., [START_REF] Baget | Revisiting chase termination for existential rules and their extension to nonmonotonic negation[END_REF] for examples illustrating the differences between these mechanisms). With each of these variants could be associated a different boundedness notion. Note however that all the chase variants collapse on rules without existential variables (i.e., plain datalog), hence the undecidability of boundedness recognition in plain datalog applies to all these potential variants of boundedness.

Proposition 6

 6 Let R be fes and fus and C R be the associated completion set. Then: for any fact base F , α d R (F, R) |= α(F, C R ) (where d R is the bound introduced in Def. 4).

i.e., F is obtained by a sequence of fact bases F (= F0), F1, . . . , F k (= F ) such that, for all i > 0, Fi = α(Fi-1, ri, h) with ri ∈ R and h a homomorphism from the body of ri to Fi-1.

Several chase variants have been defined, see the last section.

i.e., q is obtained by a sequence of direct rewritings q(= q0), q1, . . . , q k (= q ) such that, for all i > 0, qi = β(qi-1, ri, µ) with ri ∈ R and µ a piece-unifier of qi-1 with ri.

The breadth-first rewriting algorithm in[START_REF] König | Sound, complete and minimal ucqrewriting for existential rules[END_REF] builds β(βi(Q, R), R) by considering only queries that are not contained in a query from βi(Q, R); in this case the fus condition becomes: there is k such that β k+1 (Q, R) = β k (Q, R).

We could state β (Q, R) = β(Q, R ), however it must be clear that, for each CQ, only a finite subset of R needs to be considered.

The three following propositions were first proven by J.-F. Baget and M.-L. Mugnier and presented in a seminar at Oxford University in December 2012.

Acknowledgments. This work was partially supported by project PAGODA (ANR-12-JS02-007-01).