Database Reference
In-Depth Information
Chapter 2
Preliminaries
Abstract We here introduce the notions which are fundamental for dealing with the
problem of extracting reliable information from (inconsistent) data in the presence
of aggregate constraints. Specifically, we formalize the basic concepts of
aggregate
constraint
,
repair
,
repair minimality
, and
consistent answer
, which will be exploited
in the following chapters to define a general framework for repairing and querying
inconsistent numerical data. We also provide a brief overview of the complexity
classes which will be referred to when addressing the complexity characterization
of several problems related to the above-mentioned framework.
2.1 Basic Notations
We assume classical notions of database scheme, relation scheme, and relation in-
stances. In the following we will also use a logical formalism to represent relational
databases, and relation schemes will be represented by means of sorted predicates of
the form
R
(
A
1
:
Δ
1
,...,
A
n
:
Δ
n
)
, where
R
is said to be the name of the relation scheme,
A
1
,...,
A
n
are attribute names (composing the set denoted as
A
R
),
Δ
1
,...,Δ
n
are the
corresponding domains, and
n
is said to be the arity of
R
. Each
Δ
i
can be either
Z
(infinite domain of integers),
(strings). For the sake of brevity, re-
lation schemes will be often identified by their names (thus omitting their signature
consisting of attribute names and domains).
A tuple over a relation scheme
R
of arity
n
is a member of
Q
(rationals), or
S
n
1
.A
(Z
∪
Q
∪
S)
relation instance of
R
is a set
r
of tuples over
R
. A database scheme
is a set of
relation schemes, whereas a database instance
D
is a set of relation instances of the
relation schemes in
D
D
. Given a tuple
t
, the value of attribute
A
of
t
will be denoted
as
t
.
Given a boolean formula
[
A
]
β
consisting of comparison atoms of the form
X
Y
,
where
X
,
Y
are either attributes of relation scheme
R
or constants and
is a compar-
1
This definition of tuple over a relation scheme admits tuples inconsistent w.r.t. attribute domains.
Search WWH ::
Custom Search