Abstract :
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 {<,=,>,⩽,⩾,≠}. 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
Keywords :
computability; computational complexity; data mining; database theory; temporal databases; temporal reasoning; TDMINE; computational complexity; confidence measures; data evolution; data mining; knowledge discovery; logical implication problem; reasoning; satisfiability; temporal database; temporal dependency; threshold values; trend dependency; Calculus; Computational complexity; Data mining; Databases; EMP radiation effects; Logic; Remuneration; Security;
