From: John.Roddick@levels.unisa.edu.au
Newsgroups: comp.databases.theory,comp.ai,aus.ai
Subject: Inductive Learning and Relational Databases
Date: 30 Sep 92 17:32:38 +0930
Organization: University of South Australia

              INDUCTIVE LEARNING ALGORITHMS AND RELATIONAL DATA

I'm currently looking at some aspects of incorporating Inductive Learning into
Relational Database Systems and I'm after any references on previous work in
the area.  I already have a number of references but will post a (more)
complete list given sufficient demand.

In order to set the scene, here are some of the parameters I consider
necessary to place on any inductive learning algorithm using relaional
database data.

i.    There is no negative training data available.  Machine learning
      algorithms use negative training examples to illustrate conditions
      that are not true in order to test that generated rules are not
      unnecessarily simplistic.  Algorithms that rely on negative training
      data are therefore of little use.  The use of the closed world
      assumption to infer negative examples by simply generating tuples
      that do not exist in the database is of limited value due to the
      nature of these missing tuples.  With the generation of rules about
      data from a database the algorithm can be considered to have found a
      solution as long as it is consistent with the positive data.  It is
      not possible to assume that data not held in the database cannot
      occur.  The situation just has not yet occurred.

ii.   The algorithms used must run without operator interaction.  In
      machine learning terms there is no teacher to indicate correct
      concept classifications.  The concept of developing an oracle which
      learns, over time from data retrieval activity, which types of
      induced dependency are the most useful could replace the teacher in
      some cases.

iii.  The algorithms do not necessarily need to find all solutions.  The
      design of my system is such as to allow a graceful degradation of
      performance as less inductive data is available until, at its bottom
      limit, the model degenerates to a normal relational database system. 
      Although there is a 'loss of induced information problem' which leads
      to a reduction in the number of rules over time, the algorithms can
      assume that rules left over from previous runs are still valid and
      should not aim to regenerate all rules from scratch.

iv.   Allied to points ii. and iii. above is the need for the algorithm to
      report their inductive findings as they find them rather than waiting
      until the algorithm runs to completion.  Often, especially with large
      database systems, running to completion may be impractical.

v.    If possible, temporal support should be accommodated but I have found
      no learning algorithms able to do this.  In particular, knowledge of
      temporal relationships, ala Allen (1981, 1983, 1984) should be
      handled.

vi.   The database data, at least for my purposes, may be considered
      accurate.  Many algorithms do not make this assumption and employ
      probabilistic methods of concept formation.

vii.  My method of storage and the nature of the relational data itself is
      such that disjunctive classification rules are required. 

viii. All information is available to the algorithm at all times but there
      will be more data than can be reasonably held in storage.  Both
      incremental and non-incremental learners can thus be employed
      although breadth-first searching through the entire search space, as
      employed in some non-incremental learners, may be infeasible.

Thanks in advance,

John.

-------------------------------------------+----------------------------
John Roddick                               | Phone: (08) 302 3463
School of Computer and Information Science | Int.:  +61 8 302 3463
Faculty of Applied Science and Technology  | Fax:   (08) 302 3381
University of South Australia              | Email: Roddick@UniSA.Edu.AU
THE LEVELS      SA  5095                   | 
SOUTH AUSTRALIA                            |
#! rnews 539