Time Series Data Cleaning: A Survey <s> B. PROBLEM CHALLENGE <s> We address the problem of minimal-change integrity maintenance in the context of integrity constraints in relational databases. We assume that integrity-restoration actions are limited to tuple deletions. We focus on two basic computational issues: repair checking (is a database instance a repair of a given database?) and consistent query answers [in: ACM Symposium on Principles of Database Systems (PODS), 1999, 68] (is a tuple an answer to a given query in every repair of a given database?). We study the computational complexity of both problems, delineating the boundary between the tractable and the intractable cases. We consider denial constraints, general functional and inclusion dependencies, as well as key and foreign key constraints. Our results shed light on the computational feasibility of minimal-change integrity maintenance. The tractable cases should lead to practical implementations. The intractability results highlight the inherent limitations of any integrity enforcement mechanism, e.g., triggers or referential constraint actions, as a way of performing minimal-change integrity maintenance. <s> BIB001 </s> Time Series Data Cleaning: A Survey <s> B. PROBLEM CHALLENGE <s> Managing inconsistency in databases has long been recognized as an important problem. One of the most promising approaches to coping with inconsistency in databases is the framework of database repairs, which has been the topic of an extensive investigation over the past several years. Intuitively, a repair of an inconsistent database is a consistent database that differs from the given inconsistent database in a minimal way. So far, most of the work in this area has addressed the problem of obtaining the consistent answers to a query posed on an inconsistent database. Repair checking is the following decision problem: given two databases r and r', is r' a repair of r? Although repair checking is a fundamental algorithmic problem about inconsistent databases, it has not received as much attention as consistent query answering. In this paper, we give a polynomial-time algorithm for subset-repair checking under integrity constraints that are the union of a weakly acyclic set of local-as-view (LAV) tuple-generating dependencies and a set of equality-generating dependencies. This result significantly generalizes earlier work for subset-repair checking when the integrity constraints are the union of an acyclic set of inclusion dependencies and a set of functional dependencies. We also give a polynomial-time algorithm for symmetric-difference repair checking, when the integrity constraints form a weakly acyclic set of LAV tgds. After this, we establish a number of complexity-theoretic results that delineate the boundary between tractability and intractability for the repair-checking problem. Specifically, we show that the aforementioned tractability results are optimal; in particular, subset-repair checking for arbitrary weakly acyclic sets of tuple-generating dependencies is a coNP-complete problem. We also study cardinality-based repairs and show that cardinality-repair checking is coNP-complete for various classes of integrity constraints encountered in database design and data exchange. <s> BIB002 </s> Time Series Data Cleaning: A Survey <s> B. PROBLEM CHALLENGE <s> The framework of database repairs provides a principled approach to managing inconsistencies in databases. Informally, a repair of an inconsistence database is a consistent database that differs from the inconsistent one in a "minimal way." A fundamental problem in this framework is the repair-checking problem: given two instances, is the second a repair of the first? Here, all repairs are taken into account, and they are treated on a par with each other. There are situations, however, in which it is natural and desired to prefer one repair over another; for example, one data source is regarded to be more reliable than another, or timestamp information implies that a more recent fact should be preferred over an earlier one. Motivated by these considerations, Staworko, Chomicki and Marcinkowski introduced the framework of preferred repairs. The main characteristic of this framework is that it uses a priority relation between conflicting facts of an inconsistent database to define notions of preferred repairs. In this paper we focus on the globally-optimal repairs, in the case where the constraints are functional dependencies. Intuitively, a globally-optimal repair is a repair that cannot be improved by exchanging facts with preferred facts. In this setting, it is known that there is a fixed schema (i.e., signature and functional dependencies) where globally-optimal repair-checking is coNP-complete. Our main result is a dichotomy in complexity: for each fixed relational signature and each fixed set of functional dependencies, the globally-optimal repair-checking problem either is solvable in polynomial time or is coNP-complete. Specifically, the problem is solvable in polynomial time if for each relation symbol in the signature, the functional dependencies are equivalent to either a single functional dependency or to a set of two key constraints; in all other cases, the globally-optimal repair-checking problem is coNP-complete. We also show that there is a polynomial-time algorithm for distinguishing between the tractable and the intractable cases. The setup of preferred repairs assumes that preferences are only between conflicting facts. In the last part of the paper, we investigate the effect of this assumption on the complexity of globally-optimal repair checking. With this assumption relaxed, we give another dichotomy theorem and another polynomial-time distinguishing algorithm. Interestingly, the two dichotomies turn out to have quite different conditions for distinguishing tractability from intractability. <s> BIB003
For the problem of time series data cleaning, the following four difficulties have been discovered through the survey: (1) The amount of data is large and the error rate is high. The main source of time series data is sensor acquisition. Especially in the industrial field, sensors distributed throughout the machine are constantly monitoring the operation of the machine in real-time. These sensors often collect data at a frequency of seconds, and the amount of data collected is quite large. For instance, the sensor collection interval of a wind power company equipment is 7 seconds, each machine has more than 2000 working status data, and more than 30 million pieces of data are collected every day, so the working status data of one day could exceed 60 billion. However, the data collected by the sensor are often not accurate enough, and some because of the physical quantity of the observation is difficult to measure accurately. For instance, in a steel mill, with affecting by environmental disturbances the surface temperature of the continuous casting slab cannot be accurately measured or may cause distortion due to the power of the sensor itself. (2) The reasons for generating time series data errors are complicated. People always try to avoid the generation of time series erroneous data, however, there are various time series errors. Besides the observed errors that we mentioned above for various reasons, Karkouch et al.  also explain in detail the IoT data errors generated by various complex environments. IoT data is a common time series of data, and its widespread existence is really in the world. The complex reasons of time series errors also are challenges we face in cleaning and analyzing data that is different from traditional relational data. (3) Time series data are continuously generated and stored. The biggest difference between time series data and relational data is that the time series is continuous. Thereby, for time series data, it is important that the cleaning algorithm supports online operations (real-time operations). The online anomaly detection or cleaning algorithm can monitor the physical quantity in real-time, detect the problem and then promptly alarm or perform a reasonable cleaning. Thereby, the time series cleaning algorithm is not only required to support online calculation or streaming calculation but also has good throughput. (4) Minimum modification principle BIB002 , BIB001 , BIB003 . Time series data often contain many errors. Most of the widely used time series cleaning methods utilize the principle of smooth filtering. Such methods may change the original data too much, and result in the loss of the information contained in the original data. Data cleaning needs to avoid changing the original correct data. It should be based on the principle of minimum modification, that is, the smaller the change, the better.