Learning Meta Knowledge for Database Checking

Jeffrey C. SchlimmerAAAI 1991

Introduction

As expert systems evolve, their underlying knowledge bases often grow to massive proportions, making manual maintenance nearly impossible. A prime example is XCON, a configuration system that expanded from 750 rules to over 10,000 rules and 31,000 component descriptions over a decade. In such environments, human error is inevitable. While simple typos are easily caught, "legal but incorrect" values—entries that are technically valid but contextually nonsensical—pose a significant challenge. This paper introduces CARPER, a system designed to automate the detection of these subtle inconsistencies by learning "meta-knowledge" about the data.

The CARPER System Architecture

CARPER operates on a "describe-prescribe" paradigm: it first describes the existing data patterns using machine learning and then uses these descriptions as prescriptive rules to validate new entries. The system integrates three distinct layers of models to ensure comprehensive checking.

The CARPER system architecture, illustrating the flow from database dictionary and raw data to violation detection.
  1. Definitional Models: These are derived from parsing official documentation (the Database Dictionary) to establish fundamental types and valid ranges.
  2. Simple Range Models: These record the historical distribution of values for each attribute.
  3. Learned Models: The core innovation of CARPER, these models use a modified C4 algorithm to generate decision trees that predict an attribute's value based on the values of other related attributes.

Learning Meta-Knowledge from Complex Data

The effectiveness of CARPER lies in its ability to uncover hidden dependencies between database attributes. In the XCON "processors" class, for instance, there are 85 distinct attributes ranging from physical dimensions to electrical specifications. By identifying which attributes correlate, the system can flag an entry where, for example, the power consumption does not match the expected value for a processor of a certain size.

A dependency matrix showing the learned relationships between various database attributes in the XCON component database.

To make the learning process robust, the authors implemented several technical enhancements:

  • Lazy Tree Building: Subtrees are built dynamically for the specific entry being checked, reducing learning time by 40%.
  • Binarization: Nominal values are grouped into binary tests to avoid the bias toward high-cardinality attributes inherent in standard ID3/C4 algorithms.
  • Redundant Rule Sets: Instead of selecting a single "best" attribute for splitting, CARPER retains the top 5% of candidates. This redundancy ensures that if multiple attributes are equally predictive, the system remains robust against minor variations.

Experimental Results and Evaluation

The system was evaluated on 87 processor entries from the XCON database. Developers reviewed the flagged violations to assess the system's utility.

  • Error Detection: CARPER identified 37 definitional and 93 range violations, all of which were deemed "useful" by XCON experts.
  • The Impact of Redundancy: Standard C4 models produced a high volume of false alarms, with a hit rate of approximately 49-57%. By implementing redundant models, the system reduced the total number of alarms while increasing the hit rate to 63-76%. This improvement makes the system significantly more trustworthy for human maintainers.

Conclusion and Future Work

CARPER demonstrates that inductive machine learning can effectively turn descriptive data observations into prescriptive sanity checks. While the system currently struggles with complex relational data and hierarchical subclass knowledge, its success in the XCON environment highlights the potential for automated "meta-knowledge" acquisition in large-scale database maintenance.

Summary updated

BibTeX
@inproceedings{schlimmer1991learning,
  author = {Jeffrey C. Schlimmer},
  title = {{Learning Meta Knowledge for Database Checking}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}

Loading related content...

Figure