A KDD framework to support database audit.
Understanding data semantics from real-life databases is  considered following an audit perspective: it must help experts to  analyse what properties actually hold in the data and support the comparison  with desired properties. This is a typical problem of knowledge discovery in  databases (KDD) and it is specified within the framework of Mannila  and Toivonen where data mining consists in querying theories e.g., the theories  of approximate inclusion dependencies. This formalization enables us to  identify an important subtask to support database audit as well as a generic  algorithm. Next, we consider the DREAM relational database reverse engineering  method and DREAM heuristics are revisited within this new setting.
Introduction
We are interested in understanding data semantics from real-life databases.
This process is considered following an audit perspective in the following sense:
it must help experts to analyse what properties actually hold in the data and
support the comparison with desired properties. This research paper takes examples
from relational database audit, assuming that inclusion and functional
dependencies that (almost) hold in the data capture the so-called data seman-
tics. This will be called hereafter the basic problem. However, our framework can
be applied to other kinds of databases and/or properties.
This work has been done while the author was on sabbatical year in the Department of
Computer Science at the University of Helsinki (Finland). It is partly supported by AFFRST,
Association Franco-Finlandaise pour la Recherche Scientifique et Technique.
Auditing databases is an important topic. Integrity constraints that have been
more or less explicited at the design time of a database may not always hold in
a given instance. Indeed, only recent Data Base Management Systems enable
to enforce important integrity constraints such as foreign keys. In most of the
cases, it is assumed that application programs enforce desired integrity constraints
and, obviously, it is not always done in real-life databases. Understanding data
semantics in databases is of a crucial interest to support their maintenance and
evolution. The fact that some property holds or not in an instance can be used
by experts to fix some integrity violation in the data. It can also lead to an
explicit definition of an integrity constraint for further use of built-in checking
mechanisms. Improving our knowledge of encoded data semantics is also useful
for semantic query optimization (see e.g., [2]). Last but not least, audit is an
important preliminary step for a database reverse engineering process [5] or the
design of federated databases. Indeed, solving the basic problem provides the
raw knowledge that is needed to start a restructuring phase on a denormalized
relational schema [13].
Auditing as querying multiple theories. Auditing databases is a typical problem
of Knowledge Discovery in Databases (KDD). Discovering knowledge from
databases can be seen as a process containing several steps: understanding the
domain, preparing the data set, discovering patterns (e.g., dependencies), post-processing
of discovered patterns (e.g., selecting dependencies that should become
integrity constraints), and putting the results into use [8]. This is a semi-automatic
and iterative process that is often described using ad-hoc formalisms
and/or notations. However, a general KDD framework has been proposed by
Mannila and Toivonen [11]. Data mining consists in querying the so-called theory
of the database w.r.t. a class of patterns and a selection predicate that
defines their interestingness. Audit can then be supported by queries over relevant
theories. This approach emphasizes a human-centered process: expert users
can precisely specify the theories they are interested in and formulate queries to
learn about the properties that really hold in the data.
Contribution. First, we specify auditing tasks within this general KDD frame-
work. The basic problem is formalized as mining theories of approximate inclusion
and functional dependencies (see Section 2). This enables us to identify an important
subtask to support database audit i.e., querying an intensionally defined
collection of dependencies. A generic algorithm, the "guess-and-correct" scheme
introduced in [11], is a good starting point for the evaluation of such queries (Sec-
tion 3). Finally, in Section 4, we revisit the heuristics that constitute the core of
the DREAM reverse engineering method [16,17]. In this project, equi-joins that
are performed in the application programs are used to support the discovery of
"relevant" dependencies.
2. A formal framework for database audit
Notations The reader is supposed to be familiar with relational database con-
cepts. Suppose r is a relational database instance over the schema R. A relation
belongs to R and is defined by a relation name R i and a set of attributes
Each relation R i associated with a table r i which is a set of tuples.
The database extension r represents the set of tables r i . r i [Y ] is the projection of
the table r i on Y ' X i and t[Y ] is the projection of the tuple t following Y. Let
Y and Z be two subsets of X i , a functional dependency denoted by R
on R i
[Z]. It can be
be two relations associated with
tables r i and r j respectively. Let Y (resp. Z) be a subset of attributes of X i
dependency denoted by R i [Y ] ' R j [Z] is true in r i and
It can be written r
2.1. Computing theories
First, we introduce the KDD framework of Mannila and Toivonen [11].
Given a database instance r, assume the definition of a language L for expressing
properties of the data and a selection predicate q. The predicate q is used for
evaluating whether a sentence ' 2 L defines a potentially interesting property of
r. Therefore, a mining task is to compute the theory of r with respect to L and
q, i.e., the set Th(L; is trueg: It is possible to consider
generic algorithms to compute such theories following the popular "learning as
search" paradigm. A reasonnable collection of data mining tasks (association
rules, sequential patterns, data dependencies, etc) have already been carried out
using this approach (see [12] for a survey).
Example 2.1. Consider the discovery of dependencies that hold in a database.
Assume L 1 is the language of inclusion dependencies and consider q 1 as the
satisfaction predicate: let r and s be the instances of R and S, and
be the language of functional
dependencies. Here again, the predicate q 2 is the satisfaction predicate.
For instance, assume and the two following
instances:
Looking for a generic data mining technique, a key issue is to organize the search
through the space of L sentences and get some safe pruning strategies. Here,
to be safe means that we do not want to miss any interesting sentence w.r.t.
the selection predicate. A simple idea is to define a specialization relation on L
and then use a levelwise algorithm to compute Th(L; specialization
relation - is a partial order: ' is more general than `, if ' - ' (' is more specific
than '). It is a monotone specialization relation w.r.t. q if for all r and ', if
In other words, if a sentence ' satisfies q, then
also all more general sentences fl satisfy q. A simple but powerful "generate-
and-test" algorithm can now be derived: start from the most general sentences
and then try to generate and to evaluate more and more specific sentences, but
do not evaluate those sentences that can not be interesting given the available
information.
Example 2.2. A monotone specialization relation w.r.t. inclusion dependencies
is defined as follows: for
have
i: For instance, given
i]. The most general
sentences are all the potential unary inclusion dependencies and at each itera-
tion, one consider "longer attribute sequences". Now, assuming the restriction to
functional dependencies with a fixed right-hand side denoted as B, a monotone
specialization relation w.r.t. functional dependencies is the reverse of set inclu-
5sion: for X , Y ' R and B 2 R we have . For
instance, D. The most general sentences have the whole set R
as the left-hand side. At each iteration, one consider shorter left-hand sides. The
selection predicate q 1 (resp. It means that
if R[hA; Bi] ' S[hE; F i] holds then R[hAi] ' S[hEi] holds. A safe pruning criteria
is now obvious: if R[hAi] ' S[hEi] does not hold then R[hA; Bi] ' S[hE; F i]
does not hold either and should be discarded at the candidate generation step.
The same idea applies for functional dependencies: if AB ! D does not hold
then A ! D doe not hold either and might be pruned.
By alternating candidate generation and candidate evaluation, a levelwise algorithm
moves gradually to the more specific interesting sentences. This has been
already implemented for inclusion and functional dependency computation (see
[11] for a complexity analysis and pointers to related work). It provides the
best known algorithm for the discovery of all the inclusion dependencies. For
functional dependencies, better algorithms are available (e.g., [9]). However, it
is clear that functional dependency discovery is a very hard problem due to its
inherent exponential complexity and the fact that functional dependencies with
long left-hand sides are less likely to hold than functional dependencies with
shorter ones.
A problem with such a scheme is that the computation of the most interesting
sentences in a theory can be quite slow if there are interesting statements
that are far from the most general sentences (the typical case for functional de-
pendencies). Furthermore, a framework designed to support (basic) audit task
might consider some important specificities of this kind of application. First,
one should not consider only exact dependencies: we want to study dependencies
even in the case where some tuples violate these constraints. Next, the expert
user is quite often interested in tightly specified subsets of the dependencies that
hold. For instance, he/she just want dependencies that involve a given collection
of attributes. Finally, quite often, dependencies do not have to be computed from
scratch i.e., either the expert user has already a good knowledge of constraints
that should hold and/or the computation of constraints has been already done
on a previous state of the database.
This motivates the definition of the theories of approximate dependencies, a
querying approach over intensionally defined theories, and the use of a variation
of the levelwise algorithm, the so-called "guess-and-correct" scheme.
2.2. Solving the basic problem
Computing approximate dependencies Inconsistencies in the database can be
allowed by defining q 0
ffi) to be true iff some error measure of the dependency
is lower or equal to a user-defined threshold. Let us define an error measure g
for the inclusion dependency
where r is the instance of R. Using g enables to consider dependencies that almost
hold since it gives the proportion of tuples that must be removed from r to get
a true dependency. Among the several ways of defining approximate functional
dependencies in an instance r of R, one can also consider the minimum number
of rows that need to be removed from r for the dependency
hold (the so-called g 3 error measure in [9]):
Example 2.3. Assuming the instances of Example 2.1 for
approximate inclusion and functional dependencies are
given.
Inclusion dependencies Error Functional dependencies Error
The selection predicate q 1 (resp. q 2 ) can be modified to denote that all the
approximate inclusion (resp. functional) dependencies whose error is lower or
equal to a user-supplied threshold are desired. These selection predicates remain
monotone w.r.t. their respective specialization relations.
Now, one naive approach to solve the basic problem might be to compute
theories of approximate dependencies for some error thresholds, store them in a
"SQL3" table and then query such tables using available query languages. This is
a typical approach in many KDD applications where interestingness of patterns
is considered in a postprocessing phase while pattern discovery is mainly guided
by simple criteria like statistical significance or error thresholds. This gives rise
to several problems. The size of such theories can be huge while the expert user
is interested in only a few dependencies. Not only it might be untractable to
compute the whole theories but also it gives rise to tedious postprocessing phases
(e.g., a posteriori elimination of redundancies). It motivates a flexible querying
framework that support the analysis of tightly specified theories.
Querying tightly specified theories It happens that, a priori, only small subsets of
the languages of dependencies L 1 or L 2 are interesting. Restrictions of practical
interest concern non trivial inclusion or functional dependencies, unary inclusion
dependencies but also various selection criteria over attributes. Attribute data
types and application domain semantics guide the definition of such restrictions.
Example 2.4. Continuing Example 2.1, an inclusion dependency like S[hEi] '
R[hBi] can be considered as irrelevant if the corresponding domains for E and B
are respectively, a collection of transaction identifiers and f1,2g to denote male
or female. Also, in an application domain like relational schema restructuring, it
is clear that not all the functional dependencies are interesting (see Section 4).
In fact, only expert users can define such restrictions. It is possible to define
them either as context-sensitive restrictions to the definition of L 1 and L 2 or by
means of new selection predicates. These different views influence the computation
process and its efficiency: it is more or less a "generate-and-test" scheme
when the generation of candidate dependencies can make an active use of given
restrictions. Notice that refining the language (re)definition is the basic technique
for dependency discovery with inductive logic programming systems, the
so-called declarative linguistic bias definition (see e.g., [7]).
A typical audit process requires the computation of many related theories.
Not only, several theories for the same dependency class are needed, depending
of the dynamically evolving user's interest, but also different theories for different
kind of dependencies might be useful. An obvious example is the audit of referential
integrity constraints for which one must consider inclusion dependencies
whose right-hand side sets of attributes are a key i.e., a special case of functional
dependency.
To cope with such a querying approach, the conceptual framework of inductive
databases has recently emerged. It suggests an elegant approach to support
audit or more generally data mining over multiple theories.
2.3. Towards inductive databases
An inductive database, is a database that contains inductive generalizations
about the data, in addition to the usual data [3]. The idea is that the user can
then query the data, the properties in the data as well as the "behavior" of the
data w.r.t. some properties.
Theories are here defined intensionally. Indeed, it is not realistic to consider
that querying properties can be carried out by means of queries over some
materializations of every properties (e.g., data dependencies). The idea is that
properties are computed only at query evaluation time, when the user is asking
for some specific ones. However, during the formulation of the query, he can
think that every property is just there.
Formally, the schema of an inductive database is a
where R is a database schema, QR is a collection of patterns, V is a set of result
values, and e is the evaluation function that defines how patterns occur in the
data. The function e maps each pair (r; ' i ) to an element of V , where r is a
database over R and ' i is a pattern from QR . An instance (r; s) of an inductive
database over the schema R consists of a database r over the schema R and a
subset s ' QR .
For our basic problem, we need two inductive databases that associate to
a database all the inclusion dependencies and functional dependencies that can
be built from its schema. We can choose that evaluation functions respectively
return the g and g 3 error measures as previously defined.
At each stage of manipulating an inductive database (r; s), the user can
think that the value of e(r; ') is available for each pattern ' which is present in
the set s i.e., that every dependency is actually in s. He/she send queries over the
intensionally defined collections of all dependencies to select only dependencies
fulfilling some constraints.
Example 2.5. Continuing Example 2.1, a user might be interested in "select-
ing" only inclusion dependencies between instances r and s that do not involve
attribute R:A in their left-hand side and have a g error value lower than 0:3. One
expects that a sentence like R[hC; Di] ' S[hE; F i] belongs to the answer.
The definition of a concrete query language for inductive databases is out of the
scope of this paper. However, let us take ideas from the SQL-like operator MINE
RULE [15] and propose two queries.
Example 2.6. The first part of a query specifies the kind of dependency one
want to mine while the second one, that begins with the keyword FROM, defines
the data in which mining is performed. The intuition is that all the power of
SQL can be used for that selection of the data part. The query introduced in
Example 2.5 can be written as follows:
MINE INCLUSION DEPENDENCIES as IND
SELECT 1.3 as LHS-IND
1.3 as RHS-IND
FROM R,S
The schema of the output table IND has three attributes LHS-IND, RHS-IND and
ERROR that correspond respectively to the left-hand side, the right-hand side and
the error measure of inclusion dependencies. Given the instances in Example 2.1,
we expect that the tuple (hC; that denotes the approximate
inclusion dependency R[hC; Di] ' S[hE; F i] belongs to IND.
One can now search for functional dependencies in s whose left-hand sides are
a right-hand side of a previously discovered inclusion dependency. Such a query
might look like:
MINE FUNCTIONAL DEPENDENCIES as FD
SELECT 1.3 as LHS-FD
1.1 as RHS-FD
The schema of the output table FD has also three attributes LHS-FD, RHS-FD and
ERROR with the obvious meaning. Given the instances in Example 2.1, we expect
that the tuple (hE; that denotes EF ! G belongs to FD.
Evaluating this kind of query provides information about potential foreign keys
Gg.
Actual object-relational query languages can be used as a basis for inductive
database query languages. However, non classical optimization schemes are
needed since selections of properties lead to complex data mining phases. In-
deed, implementing such query languages is difficult because selections of properties
are not performed over previously materialized collections. Optimizing this
kind of query remains an open problem for properties like functional dependen-
cies. However, many inspiring ideas emerge from current research on association
rule mining [3].
3. The "guess-and-correct" generic algorithm
[11] provides a generic algorithm that start the process of finding Th(L;
from an initial guess S ' L. It appears as an interesting basis for query evalua-
tion. Consider a set S ' L closed downwards under -, i.e., if ' 2 S and fl - ',
then (by definition, this is true for Th(L; q)). The border Bd(S) of S
consists of those sentences ' such that all generalizations of ' are in S, the so-called
positive border Bd + (S), and none of the specializations of ' is in S, the so
called negative border Bd \Gamma (S)). Bd consists of the most specific sentences in
S, and Bd \Gamma (S) consists of the most general sentences that are not in S. Roughly
speaking, the positive border is the collection of the sentences that are "just in"
the theory while the negative border is the set of sentences that are "just off ".
Example 3.1. Assume that the collection of maximal nontrivial inclusion dependencies
i.e., the positive border
of the theory is fR[hA; B; Di] ' S[hG; F; Ei]; R[hCi] ' S[hEi]; S[hEi] '
g. Its negative border contains many non-dependencies
like R[hAi] ' S[hEi], or R[hBi] ' S[hEi].
Computing borders is not a simple task in general but it is tractable for sets of
data dependencies in real-life business databases.
Algorithm 3.1. The "guess-and-correct" algorithm [11]. Given, a database r, a
language L with specialization relation -, a selection predicate q, and an initial
guess S closed under generalizations, this algorithm outputs Th(L;
1. E := ;; // correct S downward
2. C := Bd
3. while C 6= ; do
4.
5. S := S n f' 2 C j q(r; ') is falseg;
7. od;
8. C
9. while C 6= ; do
// evaluation: find which sentences of C i satisfy q:
using S:
12. C := Bd \Gamma (S);
13. od;
14. output
The algorithm first evaluates the sentences in the positive border Bd
removes from S those that are not interesting. These steps are repeated until
the positive border only contains sentences satisfying q, and thus S ' Th(L;
Then the algorithm expands S upwards, it evaluates such sentences in the negative
border that have not been evaluated yet, and adds those that satisfy
q to S. Again, these steps are repeated until there are no sentences to evaluate.
Finally, the output is q). Notice that, from the complexity point of
view, the selection predicate has to be evaluated on every sentence that belongs
to the border of a theory. If the initial guess and the
first part of the algorithm is just skipped while the second part starts with the
candidate set C containing the most general sentences of L. We get the simple
levelwise algorithm that has been sketched in Section 2.1.
The discovery of (approximate) functional and inclusion dependencies in a
database can be solved by algorithm 3.1 given the specialization relations we
introduced.
Results about the complexity of such a scheme can be found in [11] and are
not discussed here. However, it is clear that the better the guess is, the better the
algorithm is efficient. How to obtain good original guesses S? One fairly widely
applicable method is sampling: take a small sample s from r, compute Th(L; s; q)
and use it as S. Another obvious situation where a guess is available is when a
new audit is performed on the same database: most of the dependencies should
have been preserved. Definitions at the schema level and application programs
can also be used to produce a guess.
4. Revisiting DREAM heuristics
This section revisits heuristics about dependency discovery for relational
database reverse engineering. Given an operational database, the aim of a
Database Reverse Engineering (DBRE) process is to improve the understanding
of the data semantics and to support the (re)definition of a validated conceptual
model. A DBRE process is naturally split into two major steps [17]:
ffl Eliciting the data semantics from the existing system
Various sources of information can be relevant for tackling this task, e.g.,
the physical schema or the dictionary, the data, the application programs,
but especially expert users. Among other things, application programs might
encode integrity constraints that have not been encoded at the schema level.
ffl Expressing the extracted semantics with a high level data model
This task consists in a schema translation activity and gives rise to several
difficulties since the concepts of the original model (e.g., a relational schema)
do not overlap those of the target model (e.g., an Entity-Relationship model).
Many works have been done where a conceptual schema is more or less automatically
derived from a hierarchical database, a network database or a relational
database [1,4,16]. For relational databases, it is not realistic to assume that functional
dependencies or foreign keys are available at the beginning of a DBRE
process. Furthermore, the less we make assumptions on the knowledge a priori
(normalization, attribute naming discipline, etc), the more we can cope with real-life
databases. Several works [18,16,19] have proposed independently to fetch the
needed information from the data manipulation statements embedded in application
programs.
In the DREAM project [16], we began to study the use of equi-joins to
support 3NF schema reverse engineering. This work has been extended to cope
with denormalized schema in [17]. In the spirit of [14], the DREAM approach
consider the relational schemas that can be translated into conceptual schemas, by
looking into the method which has been used to design them. The key problems
can be resumed as follows: identifying the relevant objects of the application
domain, recovering the structure of each of these objects and eliciting the links
(or relationships) between these objects. This process is inherently iterative and
interactive: only a part of dependency discovery can be done automatically.
To cope with denormalized schemas, [17] propose a restructuring phase that
leads to 3NF schemas where, according to the experts in charge of the validation,
each relation maps exactly one object of the application domain. For that pur-
pose, one has to find the functional dependencies which are meaningful for the
application domain while they are not conceptualized as relations. Assuming that
primary keys are known, the difficulty is to find out the non-key attributes that
correspond to identifiers of objects of the application domain. These attributes
constitute the left hand side of relevant functional dependencies and are involved
in some (approximate) inclusion dependencies (foreign keys). As a matter of fact,
one must support the discovery of hidden objects [10] that can even be encoded
in 3NF schemas.
The main contribution in the DREAM proposal has been to explore how
the attributes on which equi-joins are performed help the discovery of interesting
inclusion and functional dependencies for these restructuring purposes. The main
result has been the following heuristics.
ffl equi-joins between sets of attributes that are embedded in application programs
can be used to discover "relevant" inclusion dependencies.
ffl non key attributes of inclusion dependencies are good candidates for the left-hand
side of "relevant" functional dependencies.
These heuristics obviously reduce the number of dependencies to be considered
and "relevancy" refers to the interestingness of discovered dependencies for the
restructuring process. A complete scenario is considered in [17] though the following
example carries out the intuition.
Example 4.1. Given emp=fcode,name,tel,addg, dept=fdep,director,addg
and the dependencies (1) dept[director] ' emp[code] (2) emp[add] '
dept[add] (3) code ! name, tel, add and (4) tel ! add. Dependencies
(1) and (3) seem relevant for a restructuring phase while (2) and (4) are
just integrity constraints. The DREAM heuristics rely on the assumption that
dept.director ./ emp.code is probably performed in application programs
(pointing out the potentially interesting dependency (1) and that code is a candidate
for a left-hand side of a potentially interesting functional dependencies)
while dept.add ./ emp.add probably do not occur.
It is now clear that analyzing the set of equi-joins in application programs,
enables to focus on interesting inclusion dependencies. Furthermore, it helps to
fix integrity problems when we find that, e.g., R:C ./ S:E is performed while
neither R[hCi] ' S[hEi] or S[hEi] ' R[hCi] hold.
The collection of equi-joins can be considered as a theory Th(L;
is the language of all the equi-joins between sets of attributes from r and q is the
predicate that says if a given equi-join is performed on r. Computing such theories
requires non trivial compilation techniques. Indeed, even if we consider only
SQL queries, equi-joins can be performed in many ways, with nested or unnested
queries, with a where clause or with an intersect operator, etc. Such a collection
is a valuable source of information to support maintenance of application code
as well as data semantics elicitation.
DREAM heuristics can be encoded in queries over the inductive databases of
inclusion and functional dependencies, using selection criteria derived from equi-join
occurrences. The DREAM method does not claim any completness about
discovered dependencies. However, it appears that by combining the different
sources of information, we can compute guesses and speed up the discovery of
the complete collections.
5. Conclusions
We presented a framework for the audit of databases based on a KDD per-
spective. It emphasizes that high-level querying tools are needed to support
expert analysis of operational databases. It provides a nice application domain
for an ongoing research on generic data mining tools (inductive database management
systems) though it brings a solution to concrete problems of practical
interest (e.g., mining approximate dependencies). We must now study typical
audit tasks. For instance, supporting the elicitation of referencial integrity constraints
can be useful when migrating from an old DBMS to a recent one. It
needs not only to mine inclusion and functional dependencies but also to support
the efficient search for erroneous data. Finally, it seems interesting to study
the relationship between approximate inclusion dependency discovery and other
measures of similarity between sets of attributes e.g., [6].



--R

Conceptual database design: an Entity-Relationship ap- proach
Discovering rules in relational databases for semantic query optimisation
Querying inductive databases: a case study on the MINE RULE operator
Reverse engineering of relational databases: extraction of an EER model from a relational database
A Framework for the Design and Evaluation of Reverse Engineering Methods for Relational Databases

Machine Learning 26 (2)
Advances in Knowledge Discovery and Data Mining

A method for translating relational schemas into conceptual structures
Levelwise search and borders of theories in knowledge discovery
Methods and problems in data mining

extended entity-relationship object structures in relational schemas
A new SQL-like operator for mining association rules
Usign queries to improve database reverse engineering
Towards the reverse engineering of denormalized relational databases
An approach for reverse engineering of relational databases
Reconstruction of ER schema from database applications: a cognitive approach
--TR
reverse engineering;data mining;integrity constraint