intro.tex
\section{Introduction}

The enormous growth of information available in database systems
has pushed a significant development of techniques for knowledge
discovery in databases. At the heart of the knowledge discovery
process there is the application of data mining algorithms that
are in charge of extracting hidden relationships holding among
pieces of information stored in a given database \cite{KDDBook}.
Most used data mining algorithms include classification
techniques, clustering analysis and association rule induction
\cite{agraw93}. In this paper, we focus on this latter data mining
technique. Informally speaking, an association rule tells that a
conjunction of conditions implies a consequence. For instance, the
rule {\em hamburger, fries} $\Rightarrow$ {\em soft$-$drink}
induced from a purchase database, tells that a customer purchasing
hamburgers and fries also purchases a soft-drink.

An association rule induced from a database is interesting if it describes a
relationship that is, in a sense, \quo{valid} as far as the information stored
in the database is concerned. To state such validity, {\em indices} are used,
that are functions with values usually in $[0,1]$, that tell to what extent an
extracted association rule describe knowledge valid in the database at hand.
For instance a {\em confidence} value of 0.7 associated to the rule above tells
that 70 percent of purchases including hamburgers and fries also include a
soft-drink. In the literature, several index definitions have been provided
(see e.g. \cite{BayAgr99}, where many interestingness criteria are proposed).
Clear enough, information patterns expressed in the form of association rules
and associated indices indeed denote knowledge that can be useful in several
application contexts, e.g., market basket analysis.

In some application contexts, however, {\em Boolean} association
rules, like the one above are not expressive enough for the
purposes of the given knowledge discovery task.
%, since, in such rules, conditions are simply attributes that can evaluate
%either true or false.
%only true.
In order to obtain more expressive association rules, one can
allow more general forms of conditions to occur therein. {\em
Quantitative association rules} \cite{DBLP:conf/sigmod/SrikantA96}
are ones where both the premise and the consequent use conditions
of one of the following forms: $(i)$ $A = u$; $(ii)$ $A \neq u$;
$(iii)$ $A' \in [l',u']$; $(iv)$ $A' \notin [l',u']$, where $A$ is
a {\em categorical} attribute, i.e., an attribute that has
associated a discrete, unordered domain and $u$ is a value in this
domain, and $A'$ is a {\em numeric} attribute, that is, one
associated with an ordered domain of numbers, and $l'$ and $u'$
($l' \le u'$) are two, not necessarily distinct, values. For
instance, the quantitative rule
\\
$~~~~(hamburger \in [2,4]), (ice$-$cream$-$taste = chocolate)
\Rightarrow (soft$-$drink \in [1,3])$
\\
\noindent induced from a purchase database, tells that a customer
purchasing from 2 to 4 hamburgers and a chocolate ice-cream also
purchases from 1 to 3 soft-drinks.

In either of their forms, inducing association rules is a quite widely used
data mining technique, several systems have been developed based on them
\cite{DBLP:conf/vldb/AgrawalS94,DBLP:conf/icde/BayardoAG99}, and several
successful applications in various contexts have been described
\cite{DBLP:conf/kdd/BrijsSVW99}. Despite the wide-spread utilization of
association rule induction in practical applications, a thorough analysis of
the complexity of the associated computational tasks have not been developed.
However, such an analysis appears to be important since, as in other contexts,
an appropriate understanding of the computational characteristics of the
problem at hand makes it possible to single out tractable cases of generally
untractable problems, isolate hard complexity sources and, overall, to devise
more effective approaches to algorithm development.

As far as we know, some computational complexity analysis pertaining
association rules are performed in
\cite{DBLP:conf/icdt/GunopoulosMS97,DBLP:conf/dis/Morishita98,DBLP:conf/pods/MorishitaS00,WijMee98,
zaki98theoretical}. In \cite{DBLP:conf/dis/Morishita98} and
\cite{DBLP:conf/pods/MorishitaS00}, a NP-hardness result is stated regarding
the induction of association rules (or, in general, of {\em conditions}) having
an optimal {\em entropy} (resp. {\em chi-square}); in \cite{WijMee98}, under
some restrictive assumptions, the NP-completeness of inducing quantitative
association rules with a {\em confidence} and a {\em support}\footnote{Entropy,
confidence and support are indices (see below).} greater than two given
thresholds is proved along with a result stating a polynomial bound on the
complexity of mining quantitative rules over databases where the number of
possible items is constant. In \cite{DBLP:conf/icdt/GunopoulosMS97}, it is
stated the $\#P$-hardness of counting the number of mined association rules
(under support measure), and moreover, a specialization of the result stated in
Theorem \ref{th:large} below regarding boolean association rules. Furthermore,
\cite{zaki98theoretical} gives some results about the computational complexity
of mining frequent itemsets under combined constraints on the number of items
and on the frequency threshold.

In this paper we define a generalized form of association rules embracing both
the quantitative and the categorical and the boolean types, in which null
values (in the following indicated by $\NULL$) denoting the absence of
information, are used.

Nulls are often useful in practice. As an example, consider a
market database in which attributes correspond to available
products and values represent quantities sold.
%stored on three tables \verb+transactions+, \verb+products+ and \verb+products_sold+,
%where each row of \verb+products_sold+, is a tuple in which
%attributes correspond to the transactions code, the product code,
%and the sold quantity, respectively.
Null values can be used to denote the absence of a product in a particular
transaction (this is quite different than specifying the value $0$ instead). As
a further example, consider unavailable values in medical records representing
clinical cases in analysis of patient data. We call a database allowing null
values, a {\em database with nulls}.

When we induce association rules from databases with nulls, we require that
conditions on attributes assuming the null value are always unsatisfied, i.e.
that it is not possible to specify conditions on null values. A boolean
association rule can be thus regarded as a special case of quantitative or
categorical association rule mined on a database with nulls.

In this paper, we analyze the computational complexity implied by
inducing
%quantitative
association rules using four of the mostly used rule quality indices, namely,
confidence, support, $\theta$-gain and $h$-laplace \cite{BayAgr99,agraw93}. In
particular, we shall show that, in the standard case, and depending on the
chosen index of reference, the complexity of the problem is either P or
NP-complete. When databases with nulls are considered, independently of the
reference index, the rule induction task is NP-complete.

Despite these negative results, there are many cases where the problem turns
out to be very easy to compute: whenever the instance database is sparse (i.e.
each transaction/tuple is very small with respect to the set of possible
attributes), or when the attribute set at hand has constant size, for any
index, we are able to show that the computational complexity of the rule
induction problem is L; furthermore introducing some constraint on the input
instance leads to problems with very low complexity such as $T\!C^0$ or
$A\!C^0_2$. Problems with this kind of complexity are very efficiently
parallelizable (recall that $A\!C^0_2 \subseteq T\!C^0 \subseteq N\!C^1$,
whereas $L \subseteq N\!C^2$).
\\
The plan of the paper is as follows. In the following section we give
preliminary definitions. In Section \ref{complexity} we state general
complexity results about inducing association rules. Sparse databases and
Fixed-schema complexity of rule induction are dealt with in Section
\ref{sparse} and \ref{fixed-schema} respectively. Finally, Section
\ref{further} collects an interesting set of special tractable cases.

main.bbl
\begin{thebibliography}{10}

\bibitem{agraw97}
M.~Agrawal, E.~Allender, and S.~Datta.
\newblock On {$\mbox{TC}^0$}, $\mbox{AC}^0$ and arithmetic circuits.
\newblock {\em In Proceedings of the 12th Annual IEEE Conference on
  Computational Complexity}, pages 134--148, 1997.

\bibitem{agraw93}
R.~Agrawal, Tomasz Imielinski, and Arun~N. Swami.
\newblock Mining association rules between sets of items in large databases.
\newblock In {\em Proceedings of the 1993 ACM SIGMOD International Conference
  on Management of Data, Washington, D.C., May 26-28, 1993}, pages 207--216.

\bibitem{DBLP:conf/vldb/AgrawalS94}
R.~Agrawal and Ramakrishnan Srikant.
\newblock Fast algorithms for mining association rules in large databases.
\newblock In {\em VLDB'94, Proceedings of 20th International Conference on Very
  Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile}, pages
  487--499.

\bibitem{DBLP:conf/icde/AgrawalS95}
R.~Agrawal and Ramakrishnan Srikant.
\newblock Mining sequential patterns.
\newblock In {\em Proceedings of the Eleventh International Conference on Data
  Engineering, March 6-10, 1995, Taipei, Taiwan}, pages 3--14.

\bibitem{ambainis98}
A.~Ambainis, D.~M Barrington, and H.~L\^eThanh.
\newblock On counting {$\mbox{AC}^0$} circuits with negative constants.
\newblock {\em In Proceedings of the 23rd International Symposium on
  Mathematical Foundations of Computer Science (MFCS)}, pages 409--417, 1998.

\bibitem{imm90}
D.~A.~Mix Barrington, N.~Immerman, and H.~Straubing.
\newblock On uniformity within {$\mbox{NC}_1$}.
\newblock {\em Journal of Computer and System Sciences}, 41(3):274--306, 1990.

\bibitem{BayAgr99}
Roberto~J. Bayardo, Jr and R.~Agrawal.
\newblock Mining the most interesting rules.
\newblock {\em Proceedings of the Fifth ACM SIGKDD International Conference on
  Knowledge Discovery and Data Mining, August 15-18, 1999, San Diego, CA, USA.
  ACM}, pages 145--154, 1999.

\bibitem{DBLP:conf/kdd/BrijsSVW99}
Tom Brijs, Gilbert Swinnen, Koen Vanhoof, and Geert Wets.
\newblock Using association rules for product assortment decisions: A case
  study.
\newblock {\em Proceedings of the Fifth ACM SIGKDD International Conference on
  Knowledge Discovery and Data Mining}, pages 254--260, 1999.

\bibitem{KDDBook}
U.~Fayyad, G.~Piatetsky-Shapiro, P.~Smyth, and R.~Uthurusamy.
\newblock {\em {A}dvances in {K}nowledge {D}iscovery and {D}ata {M}ining}.
\newblock AAAI Press/MIT Press, 1996.

\bibitem{gj}
M.R. Garey and D.S. Johnson.
\newblock {\em Computers and Intractability, {A} Guide to the Theory of
  {NP}-Completeness}.
\newblock W.H. Freeman and Company, San Francisco, Ca, 1979.

\bibitem{DBLP:conf/icdt/GunopoulosMS97}
Dimitrios Gunopulos, Heikki Mannila, and Sanjeev Saluja.
\newblock Discovering all most specific sentences by randomized algorithms.
\newblock In {\em ICDT '97, 6th International Conference, Delphi, Greece,
  January 8-10, 1997, Proceedings}, pages 215--229.

\bibitem{haj1987}
A.~Hajnal, W.~Maass, P.~Pudl�k, M.~Szegedy, and G.~Turan.
\newblock Threshold circuits of bounded depth.
\newblock {\em Proceedings of the 28th Annual IEEE Symposium on Foundations of
  Computer Science}, pages 99--110, 1987.

\bibitem{DBLP:conf/icde/BayardoAG99}
Roberto J.~Bayardo Jr., R.~Agrawal, and Dimitrios Gunopulos.
\newblock Constraint-based rule mining in large, dense databases.
\newblock In {\em Proceedings of the 15th International Conference on Data
  Engineering, 23-26 March 1999, Sydney, Austrialia}, pages 188--197. IEEE
  Computer Society, 1999.

\bibitem{DBLP:conf/dis/Morishita98}
Shinichi Morishita.
\newblock On classification and regression.
\newblock {\em Discovery Science}, pages 40--57, 1998.

\bibitem{DBLP:conf/pods/MorishitaS00}
Shinichi Morishita and Jun Sese.
\newblock Traversing itemset lattice with statistical metric pruning.
\newblock In {\em Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART
  Symposium on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,
  USA}, pages 226--236. ACM, 2000.

\bibitem{ruzzo81}
W.~L. Ruzzo.
\newblock On uniform circuit complexity.
\newblock {\em Journal of Computer and System Sciences}, 22(3):365--383, 1981.

\bibitem{DBLP:conf/sigmod/SrikantA96}
Ramakrishnan Srikant and R.~Agrawal.
\newblock Mining quantitative association rules in large relational tables.
\newblock In H.~V. Jagadish and Inderpal~Singh Mumick, editors, {\em
  Proceedings of the 1996 ACM SIGMOD International Conference on Management of
  Data, Montreal, Quebec, Canada, June 4-6, 1996}, pages 1--12. ACM Press,
  1996.

\bibitem{DBLP:conf/vldb/Toivonen96}
Hannu Toivonen.
\newblock Sampling large databases for association rules.
\newblock In T.~M. Vijayaraman, Alejandro~P. Buchmann, C.~Mohan, and Nandlal~L.
  Sarda, editors, {\em VLDB'96, Proceedings of 22th International Conference on
  Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India}, pages
  134--145. Morgan Kaufmann, 1996.

\bibitem{WijMee98}
Jef Wijsen and Robert Meersman.
\newblock On the complexity of mining quantitative association rules.
\newblock {\em Data Mining and Knowledge Discovery}, 2(3):263--281, 1998.

\bibitem{zaki98theoretical}
M.~Zaki and M.~Ogihara.
\newblock Theoretical foundations of association rules.
\newblock {\em In Proceedings of 3rd SIGMOD'98 Workshop on Research Issues in
  Data Mining and Knowledge Discovery (DMKD'98), Seattle, Washington, USA},
  1998.

\end{thebibliography}
