The increasing complexity of DBMSs and their workloads has made it a difficult and time-consuming task to manage their performance manually. Autonomic computing has emerged as a promising approach to deal with this complexity by making DBMSs self-managed. Automatic statistics management, as an important part of autonomic computing, is especially necessary in decision-support systems. In this paper, we introduce a novel technique for automatic statistics management called Self-Learning Histograms (SLH), which can adapt to workload and data distribution changes by automatically building and maintaining itself using query feedback information. Query feedback is encoded as deducible rules and the histogram can be viewed as a set of these rules. Through deducing among rules, more accurate statistics can be inferred and damages to results of former tunings are avoided. Selectivity estimation based on validity of rules greatly lowered estimation errors. Extensive experiments showed the effectiveness of SLH.