Efficient SQL-Querying Method for Data M in ing in Large Data Bases

Data mining can be understood as a process of extraction of knowledge hidden in very large data sets. Often data mining techniques (e.g. discretization or decision tree) are based on searching for an optimal part i t ion of data wi th respect to some optimization criterion. In this paper, we investigate the problem of optimal bi-nary part i t ion of continuous attr ibute domain for large data sets stored in relational data bases (RDB). The critical for t ime complexity of al-gorithms solving this problem is the number of simple SQL queries like SELECT COUNT FROM... WHERE attribute BETWEEN... (related to some interval of attr ibute values) necessary to construct such partitions. We as-sume that the answer t ime for such queries does not depend on the interval length. Using straightforward approach to optimal partit ion selection (with respect to a given measure), the number of necessary queries is of order O(N), where N is the number of preassumed part i-tions of the searching space. We show some properties of considered optimization measures, that allow to reduce the size of searching space. Moreover, we prove that using only O(logiV) simple queries, one can construct the parti t ion very close to optimal. 1 I n t r oduc t i on The problem of searching for optimal partitions of real value attributes (features), defined by so called cuts, has been studied by many authors (see e.g. {Catlett, 1991