Information Technology Reference
In-Depth Information
4.9.2 Representation of Negative Databases
as Satisfi ability Problems
Esponda et al. (2004, 2007a) show that there is a natural mapping from NDBs
to the
satisfi ability (SAT) problems. For example, an instance of 3-SAT can
be represented as the instance of NDB, and this can be done in the following
manner:
1. h e Boolean formula can be written in conjunctive normal form (CNF) and
can be defi ned over some variables or literals (e.g.,
x
i
).
2. h is Boolean formula can be mapped to NDB, where each clause corresponds
to a negative record in NDB. Each variable or literal in the clause can be
represented as
a. 1 if the literal or variable is appeared as negated
b. 0 if the literal or variable is appeared as unnegated (
x
i
)
c. * if the literal is not appeared in the clause
3. h e resulting expression returns true for every assignment that is not in the
PDB, and false for each truth assignment.
In the preceding example (Table 4.4), there are fi ve literals or variables:
x
1
,
x
2
,
x
3
,
x
4
,
x
5
. If any literal is present in the clause or Boolean formula, then 0 or 1 is assigned in
the NDB depending on the negation of variable or unnegated variable. In particular,
if the variable is unnegated then there will be 0 in the NDB; in contrast, if the vari-
able is negated, then there is 1 for that variable in NDB. But if the variable is not
present in the formula, then an asterisk “*” is assigned for that variable. h erefore,
the total number of bits in each of the NDB record depends on the number of
literals. In the fi rst formula (Table 4.4),
x
3
and
x
4
are not present; therefore, in the
NDB, “*” is assigned in their positions. Also,
x
1
and
x
2
are not negated, therefore
0 is assigned, whereas
x
5
is in the negated form, therefore 1 assigned for it.
4.9.3
Approaches to Generate Negative Databases
Esponda et al. (2004) proposed two algorithms for the creation of NDBs: (1) a
deterministic algorithm and (2) a randomized algorithm. In particular, the fi rst
Table 4.4
Representation of NDB as CNF
Boolean Formula
NDB
(
x
1
or
x
2
or ¯
5
) and
00**1
(¯
2
or
x
3
or
x
5
) and
*10*0
(
x
2
or ¯
4
or ¯
5
) and
*0*11
(¯
1
or ¯
3
or
x
4
)
1*10*
Search WWH ::
Custom Search