An inductive database prototype based on virtual mining views

Hendrik Blockeel, Toon Calders, Élisa Fromont, Bart Goethals, Adriana Prado, Céline RobardetKDD 2008 · DOI

TL;DR

This paper introduces an "inductive database" that allows users to query not just raw data but also patterns and models derived from that data, using standard SQL. Their novel approach uses "virtual mining views" to represent the output of data mining algorithms, enabling interactive exploration and iterative discovery without needing to materialize massive datasets of patterns.

What Problem Does This Paper Address?

Traditional data mining is often a multi-step, iterative process. Researchers typically extract data, run algorithms in separate tools, and then try to combine or analyze the results. This workflow is cumbersome, especially when trying to explore complex relationships or use the output of one mining task as input for another. The authors highlight the need to integrate data mining directly into database management systems, allowing for more flexible and interactive knowledge discovery. They aim to bridge the gap between data storage and data mining, enabling users to ask ad-hoc queries about patterns and models, not just the raw data itself.

Methods

The core innovation is the concept of virtual mining views. Instead of storing the potentially massive output of data mining algorithms (like association rules or decision trees) directly in tables, these views act as placeholders. When a query is made against a virtual mining view, the database system triggers the corresponding data mining algorithm on the fly to compute the requested patterns or models. This is analogous to how standard database views work – they are computed only when queried.

The system is implemented as an extension to PostgreSQL. It allows users to define virtual mining views for various data mining tasks, including frequent itemset mining, association rule discovery, and decision tree learning. A key feature is the ability to push constraints from the SQL query directly into the data mining algorithms, significantly pruning the search space and improving efficiency. This means users can specify what kind of patterns they're looking for (e.g., rules with a minimum confidence) directly in their SQL query.

Datasets

The paper uses the mushroom dataset for its illustrative scenario. This dataset is described as containing 8,124 tuples and 23 categorical attributes, with the 'class' attribute distinguishing poisonous from edible mushrooms. They also create a pre-processed version of this dataset called SIMPLE_MUSHROOM by selecting a subset of attributes.

Key Insights and Ideas

  • Data mining where the data lives: The system brings data mining capabilities directly to the database, eliminating the need for data extraction and transfer to external tools.
  • SQL for knowledge discovery: Users can leverage their existing SQL knowledge to query complex patterns and models, making data mining more accessible and interactive.
  • Virtualization is key: Using virtual views for mining results avoids materializing huge datasets, making the system scalable and efficient.
  • Iterative discovery: The ability to use the output of one query (e.g., misclassified examples) as input for another (e.g., mining association rules about those misclassifications) enables powerful iterative exploration.
  • Constraint pushing: Integrating query constraints directly into data mining algorithms significantly optimizes the discovery process.

Key Results

The paper demonstrates the system's capabilities through an extended scenario involving the mushroom dataset. They show how to:

  • Pre-process data by selecting specific attributes.
  • Mine for decision trees with specific constraints (e.g., maximum size and minimum accuracy).
  • Identify misclassified examples based on a learned decision tree.
  • Mine association rules from the set of misclassified examples to understand the discriminative features.

While specific quantitative performance metrics (like speedup percentages) are not the primary focus, the paper states that experiments have shown "rather low execution times," supporting their claim of efficiency. The qualitative results highlight the system's ability to facilitate complex, multi-step data mining workflows interactively.

Limitations and Future Work

The authors acknowledge that their system can cover any mining technique whose output can be stored in relational tables. They suggest that the flexibility of ad-hoc querying allows the output of some queries to be used as input for subsequent queries, hinting at future work in building more complex discovery pipelines. The paper focuses on the conceptual framework and a prototype implementation, implying that further optimization and broader adoption of mining algorithms could be future directions.

Summary updated

BibTeX
@inproceedings{blockeel2008inductive,
  author = {Hendrik Blockeel and Toon Calders and Élisa Fromont and Bart Goethals and Adriana Prado and Céline Robardet},
  title = {{An inductive database prototype based on virtual mining views}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2008},
  doi = {10.1145/1401890.1402019},
}
Figure