Time Series Data Cleaning: A Survey <s> B. SEQUENTIAL DEPENDENCIES <s> An Armstrong relation for a set of functional dependencies (FDs) is a relation that satisfies each FD implied by the set but no FD that is not implied by it. The structure and size (number of tuples) of Armstrong relatsons are investigated. Upper and lower bounds on the size of minimal-sized Armstrong relations are derived, and upper and lower bounds on the number of distinct entries that must appear m an Armstrong relation are given. It is shown that the time complexity of finding an Armstrong relation, gwen a set of functional dependencies, is precisely exponential in the number of attributes. Also shown ,s the falsity of a natural conjecture which says that almost all relations obeying a given set of FDs are Armstrong relations for that set of FDs. Finally, Armstrong relations are used to generahze a result, obtained by Demetrovics using quite complicated methods, about the possible sets of keys for a relauon. <s> BIB001 </s> Time Series Data Cleaning: A Survey <s> B. SEQUENTIAL DEPENDENCIES <s> We propose a class of integrity constraints for relational databases, referred to as conditional functional dependencies (CFDs), and study their applications in data cleaning. In contrast to traditional functional dependencies (FDs) that were developed mainly for schema design, CFDs aim at capturing the consistency of data by enforcing bindings of semantically related values. For static analysis of CFDs we investigate the consistency problem, which is to determine whether or not there exists a nonempty database satisfying a given set of CFDs, and the implication problem, which is to decide whether or not a set of CFDs entails another CFD. We show that while any set of transitional FDs is trivially consistent, the consistency problem is NP-complete for CFDs, but it is in PTIME when either the database schema is predefined or no attributes involved in the CFDs have a finite domain. For the implication analysis of CFDs, we provide an inference system analogous to Armstrong's axioms for FDs, and show that the implication problem is coNP-complete for CFDs in contrast to the linear-time complexity for their traditional counterpart. We also present an algorithm for computing a minimal cover of a set of CFDs. Since CFDs allow data bindings, in some cases CFDs may be physically large, complicating the detection of constraint violations. We develop techniques for detecting CFD violations in SQL as well as novel techniques for checking multiple constraints by a single query. We also provide incremental methods for checking CFDs in response to changes to the database. We experimentally verify the effectiveness of our CFD-based methods for inconsistency detection. This work not only yields a constraint theory for CFDs but is also a step toward a practical constraint-based method for improving data quality. <s> BIB002 </s> Time Series Data Cleaning: A Survey <s> B. SEQUENTIAL DEPENDENCIES <s> We study sequential dependencies that express the semantics of data with ordered domains and help identify quality problems with such data. Given an interval g, we write X →g Y to denote that the difference between the Y -attribute values of any two consecutive records, when sorted on X, must be in g. For example, time →(0,∞) sequence_number indicates that sequence numbers are strictly increasing over time, whereas sequence_number →[4, 5] time means that the time "gaps" between consecutive sequence numbers are between 4 and 5. Sequential dependencies express relationships between ordered attributes, and identify missing (gaps too large), extraneous (gaps too small) and out-of-order data. ::: ::: To make sequential dependencies applicable to real-world data, we relax their requirements and allow them to hold approximately (with some exceptions) and conditionally (on various subsets of the data). This paper proposes the notion of conditional approximate sequential dependencies and provides an efficient framework for discovering pattern tableaux, which are compact representations of the subsets of the data (i.e., ranges of values of the ordered attributes) that satisfy the underlying dependency. We present analyses of our proposed algorithms, and experiments on real data demonstrating the efficiency and utility of our framework. <s> BIB003 </s> Time Series Data Cleaning: A Survey <s> B. SEQUENTIAL DEPENDENCIES <s> This paper investigates the discovery of conditional functional dependencies (CFDs). CFDs are a recent extension of functional dependencies (FDs) by supporting patterns of semantically related constants, and can be used as rules for cleaning relational data. However, finding quality CFDs is an expensive process that involves intensive manual effort. To effectively identify data cleaning rules, we develop techniques for discovering CFDs from relations. Already hard for traditional FDs, the discovery problem is more difficult for CFDs. Indeed, mining patterns in CFDs introduces new challenges. We provide three methods for CFD discovery. The first, referred to as CFDMiner, is based on techniques for mining closed item sets, and is used to discover constant CFDs, namely, CFDs with constant patterns only. Constant CFDs are particularly important for object identification, which is essential to data cleaning and data integration. The other two algorithms are developed for discovering general CFDs. One algorithm, referred to as CTANE, is a levelwise algorithm that extends TANE, a well-known algorithm for mining FDs. The other, referred to as FastCFD, is based on the depth-first approach used in FastFD, a method for discovering FDs. It leverages closed-item-set mining to reduce the search space. As verified by our experimental study, CFDMiner can be multiple orders of magnitude faster than CTANE and FastCFD for constant CFD discovery. CTANE works well when a given relation is large, but it does not scale well with the arity of the relation. FastCFD is far more efficient than CTANE when the arity of the relation is large; better still, leveraging optimization based on closed-item-set mining, FastCFD also scales well with the size of the relation. These algorithms provide a set of cleaning-rule discovery tools for users to choose for different applications. <s> BIB004 </s> Time Series Data Cleaning: A Survey <s> B. SEQUENTIAL DEPENDENCIES <s> Smart home presents a challenge in control and monitoring of its wireless sensors networks (WSN) and the internet of things (IoT) devices which form it. The current IoT architectures are centralized, complex, with poor security in its communications and with upstream communication channels mainly. As a result, there are problems with data reliability. These problems include data missing, malicious data inserted, communications network overload, and overload of computing power at the central node. In this paper a new architecture is presented. This architecture based in blockchain introduce the edge computing layer and a new algorithm to improve data quality and false data detection. <s> BIB005
The sequential dependency algorithm proposed by Golab et al. BIB003 focuses on the difference in values between two consecutive data points in a time series. Golab et al. BIB003 define the CSD Tableau Discovery Problem as given a relation instance and an embedded SD M → g N , to find a tableau t r of minimum size such that the CSD (M → g N , t r ) has confidence at least a given threshold. A CSD can be (hour→ (0,∞) height,[1961.01.01 00:00-2016.01.01 00:00]). It states that for any two consecutive hours in [1961.01.01 00:00-2016.01.01 00:00], their distance should always be > 0. Generally, a sequential dependency (SD) is in the form of In equation (11), M ⊆ R are ordered attributes, N ⊆ R can be measured by certain distance metrics, and g is an interval. It states that when tuples are sorted on M , the distance between the N -values of any two consecutive tuples are within interval g. Casado-Vara et al. BIB005 propose the concept of streaming mode to represent the structure and semantic constraints of data streams. The concept contains a variety of semantic information, including not only numeric values, but also attributes between order. The sequential dependency algorithm can be used not only for traditional relational database cleaning, but also for time series cleaning. In fact, there are many dependency-based cleaning algorithms designed for relational databases that are not suitable for time series data cleaning, such as: Functional Dependencies BIB001 (FDs) and Conditional Functional Dependencies BIB002 , BIB004 (CFDs). The sequential dependency is one of the few algorithms based on dependency that can be used for time series cleaning.