Time Series Data Cleaning: A Survey <s> A. ORDER DEPENDENCIES <s> The recently introduced notion of order dependency in the relational model is generalized to include situations where order dependency is satisfied in an approximate way. Two fundamental types of approximate satisfaction are distinguished and analyzed. It is shown for both types that such approximate satisfaction of order dependencies can be applied to substantially reduce indexing space without significantly increasing access time. <s> BIB001 </s> Time Series Data Cleaning: A Survey <s> A. ORDER DEPENDENCIES <s> Abstract The relational model is formally extended to include fixed orderings on attribute domains. A new constraint, called order dependency, is then introduced to incorporate semantic information involving these orderings. It is shown that this constraint can be applied to enhance the efficiency of an implemented database. The thrust of the paper is to study logical implication for order dependency. The main theoretical results consist in (i) introducing a formalism analogous to propositional calculus for analyzing order dependency, (ii) exhibiting a sound and complete set of inference rules for order dependency, and (iii) demonstrating that determining logical implication for order dependency is co-NP-complete. It is also shown that there are sets of order dependencies for which no Armstrong relations exist. <s> BIB002 </s> Time Series Data Cleaning: A Survey <s> A. ORDER DEPENDENCIES <s> The notion of sort set is introduced here to formalize the fact that certain database relations can be sorted so that two or more columns are simultaneously listed in order. This notion is shown to be applicable in several ways to enhance the efficiency of an implemented database. A characterization of when order dependency implies the existence of sort sets in a database is presented, along with several corollaries concerning complexity, Armstrong relations, and cliques of certain graphs. Sort-set dependencies are then introduced. A (finite) sound and complete set of inference rules for sort-set dependencies is presented, as well as a proof that there is no such set for functional and sort-set dependencies taken together. Deciding logical implication for sort-set dependencies is proved to be polynomial, but if functional dependencies are included the problem is co-NP-complete. Each set of sort-set and functional dependencies is shown to have an Armstrong relation. A natural generalization of Armstrong relation, here called separator , is given and then used to study the relationship between order and sort-set dependencies. <s> BIB003 </s> Time Series Data Cleaning: A Survey <s> A. ORDER DEPENDENCIES <s> Abstract We propose a temporal constraint, called trend dependency (TD), which captures a significant family of qualitative trends in databases. An important extension in comparison with existing temporal dependencies is that TDs allow attributes with linearly ordered domains to be compared over time by any operator of { ,⪯,≥,≠ n0 –} sound and complete axiomatization for logical implication of TDs is provided. The complexity of the logical implication problem for TDs is investigated. A comparison with related work is provided at the end of the paper. We show that TDs can express most temporal dependencies that have so far been proposed in the literature. <s> BIB004 </s> Time Series Data Cleaning: A Survey <s> A. ORDER DEPENDENCIES <s> We propose a temporal dependency, called trend dependency (TD), which captures a significant family of data evolution regularities. An example of such regularity is "Salaries of employees generally do not decrease." TDs compare attributes over time using operators of { ,/spl les/,/spl ges/,/spl ne/}. We define a satisfiability problem that is the dual of the logical implication problem for TDs and we investigate the computational complexity of both problems. As TDs allow expressing meaningful trends, "mining" them from existing databases is interesting. For the purpose of TD mining, TD satisfaction is characterized by support and confidence measures. We study the problem TDMINE: given a temporal database, mine the TDs that conform to a given template and whose support and confidence exceed certain threshold values. The complexity of TDMINE is studied, as well as algorithms to solve the problem. <s> BIB005 </s> Time Series Data Cleaning: A Survey <s> A. ORDER DEPENDENCIES <s> We consider the problem of repairing a database that is inconsistent wrt a set of integrity constraints by updating numerical values. In particular, we concentrate on denial integrity constraints with numerical built-in predicates. So far research in this context has concentrated in computational complexity analysis. In this paper we focus on efficient approximation algorithms to obtain a database repair and we present an algorithm that runs in O(n log n) wrt the size of the database. Our experimental evaluations show that even for large databases an approximate repair of the database can be computed efficiently despite the fact that the exact problem is computationally intractable. Finally, we show that our results can also be applied to database repairs obtained by a minimal number of tuple deletions. <s> BIB006 </s> Time Series Data Cleaning: A Survey <s> A. ORDER DEPENDENCIES <s> Consistent query answering is the problem of characterizing and computing the semantically correct answers to queries from a database that may not satisfy certain integrity constraints. Consistent answers are characterized as those answers that are invariant under all minimally repaired versions of the original database. We study the problem of repairing databases with respect to denial constraints by fixing integer numerical values taken by attributes. We introduce a quantitative definition of database repair, and investigate the complexity of several decision and optimization problems. Among them, Database Repair Problem (DRP): deciding the existence of repairs within a given distance to the original instance, and CQA: deciding consistency of answers to simple and aggregate conjunctive queries under different semantics. We provide sharp complexity bounds, identifying relevant tractable and intractable cases. We also develop approximation algorithms for the latter. Among other results, we establish: (a) The @D"2^P-hardness of CQA. (b) That DRP is MAXSNP-hard, but has a good approximation. (c) The intractability of CQA for aggregate queries for one database atom denials (plus built-ins), and also that it has a good approximation. <s> BIB007
In relational databases, Order Dependencies (ODs) are simple and effective methods, which have been widely studied BIB001 , BIB002 - BIB003 . We find that ODs are also suitable for solving some time series data cleaning problems. The specific explanation is as follows: Let . . x t be a time series, ODs can be expressed by <, ≤, >, ≥. For the number of miles traveled by the car x(t), the mileage should increase over time. Formal representation is as follows: is mileage, t is timestamp. For instance, consider an example relation instance in Table 3 . The tuples are sorted on attribute sequence number, which identifies sea level that rapidly increase from hour to hour. Generally, ODs in the form of equation BIB007 states that N is strictly increasing with M . Such as equation (10). ODs and DCs can also be used as an integrity constraint for error detection and data repairing in databases. Wijsen BIB004 , BIB005 extends ODs with a time dimension for temporal databases. Let I = {I 1 , I 2 , I 3 , . . . } be a temporal relation, which can be viewed as a time series of conventional ''snapshot'' relations, all over the same set of attributes. A trend dependency (TD) allows attributes with linearly ordered domains to be compared over time by using any operator of {<, =, >, ≤, ≥, =}. Consider the constraint is specified over (I i , I i+1 ) in I . For each time point i, it requires comparing employee records at time i with records at the next time i + 1, such that salaries of employees should never decrease. Lopatenko and Bravo BIB006 propose a numerical type data cleaning method based on Denial Constraints (DCs) as constraints, whose principle is similar to this one.