1314
B. Kulik, A. Fridman, A. Zuenko
Having substituted the values of attributes from the P [XY Z] into predicates
(x > y) and (y > z), we get sets of points that comprise C-systems MORE [XY ]
and MORE [Y Z] (these points are shown in dark grey in Figure 5):
x > y
y > z
X
Z
2
=
2
4
3
4
2
=
Y
7
7
5
2
=
Y
7
7
7
6
5
7
2
3
7
6
Fig. 5. Cartesian products of intervals
Obviously, these two areas have no common elements (quanta) in the attribu-
te Y . Therefore, MORE [Y Z]⊕MORE [XY ] = Ø, and µ(MORE [Y Z]⊕MORE [XY ])
= 0.
Thus, the IQM allows to determine unsatisfiability of logical formulae which
contain measurable attributes as well as implement logical inference based on struc-
ture analysis of logical formulae, including formulas that contain elementary unitary
and binary predicates with no quantifiers [21].
4.4 Relational Database Management Systems
Relations using the primary key concept are a particular case of NTA objects, since
any NTA object can be split into a set of elementary n-tuples. However, elementary
n-tuples do not use specific properties of NTA structures, thus it is rational to use
NTA only for relations whose n-tuple components are sets, not elements. Such rela-
tions can be used for representing graphs and networks, as well as some projections
of regular DB tables. If required, associative search can be an efficient alternative
to primary key search method in such structures.
Let us consider the way DBMS queries are expressed in NTA. Let a BD use
a relation expressed as an NTA object P [XY Z]. In the relation P , we need to
find all possible values for attributes X and Y , attribute Z being within the given
range D. In SQL, this query looks as follows:
SELECT X, Y FROM P WHERE Z ⊆ D.
In NTA, this query is expressed through an NTA object called a selector, in this
case, a C-n-tuple Q
1
[Z] = [D]. We can get the answer to the query by calculating
P [XY Z] ∩
G
Q
1
[Z].
Algebraic Approach to Logical Inference Implementation
1315
Let us consider an example in which a relation join is required. Suppose that, be-
side the relation P [XY Z], our DB contains a relation R[Y V W ], and we need to find
the values X and V , if Z = a. In SQL, this is written as SELECT X, V FROM P, R
WHERE Z = a AND P.Y = R.Y .
Obviously, in NTA the relation diagram of the query corresponds to the relation
diagram of the NTA object derived by joining P and R. Then the query can be
written as a C-n-tuple Q
2
[Z] = [{a}], and the answer to the query are attributes X
and V , as calculated by this formula:
(P [XY Z] ⊕ R[Y V W ]) ∩
G
Q
2
[Z].
NTA allows implementing queries that are impossible in DBMS, such as queries
addressed to relation complements. This can be implemented not only through
C-n-tuples and C-systems, but also through more complex NTA objects.
In NTA structures, recursive queries can be implemented through calculating
transitive closures of the corresponding relations, followed by selecting and elimi-
nating attributes. This subject is discussed in detail in the section below.
4.5 Deductive Databases
Deductive DBMS widely use functional systems theory and proof-theoretic ap-
proach. In such DBMS, query execution involves proving a certain theorem through
special deductive axioms and inference rules. Here, the basic axioms correspond-
ing to domain elements and n-tuples of basic relations constitute the extensional
database (EDB) of the DBMS, and the auxiliary axioms and consistency constraints
comprise its intensional database (IDB). A language of any calculus used in formu-
lating query and in logical inference for answering it, is commonly called a Datalog,
and a description in this language is called a Datalog program. The term “Datalog
rules” refers to the part of the Datalog program that contains no facts. One of the
features of deductive DBMS is recursive query support. Let us consider an example
of a Datalog program in which the facts are arranged in the Points table (see Tab-
le 1), and the rules allow finding all pairs of values of A (departure point) and B
(destination point), where A and B are, respectively, the beginning and the end of
a valid route from A to B.
Departure point
Destination point
Washington
Los Angeles
Los Angeles
New York
New York
Washington
New York
Chicago
Table 1. Points
1316
B. Kulik, A. Fridman, A. Zuenko
Datalog rules:
points(departure point ; destination point )
⊃ route(departure point , destination point ),
route(departure point , intermediate point )
∧ route(intermediate point , destination point )
∧ departure point = destination point ⊃ route(departure point , destination point ).
In NTA language, the predicate (relation) Points can be represented as follows:
T =
{Washington}
{LosAngeles}
{LosAngeles}
{NewYork}
{NewYork}
{Washington, Chicago}
.
The given Datalog program is implemented in NTA through a transitive closure
T
+
= T ∪ T
2
∪ T
3
∪ . . . ∪ T
k
, where k ≤ n. This can be obtained in several steps.
Step 1.
T
2
= T ◦ T =
{Washington}
{NewYork}
{LosAngeles}
{Washington, Chicago}
{NewYork}
{LosAngeles}
,
T ∪ T
2
=
{Washington}
{LosAngeles, NewYork}
{LosAngeles}
{NewYork, Washington, Chicago}
{NewYork}
{Washington, Chicago, LosAngeles}
.
Evidently, at the first step, the C-system derived from union of T and T
2
contains
new elementary n-tuples, as compared to the C-system T . Now let us go on to
the second step.
Step 2.
T
3
=
{Washington}
{Washington, Chicago}
{LosAngeles}
{LosAngeles}
{NewYork}
{NewYork}
,
Since the departure point is not equal to the destination point, the final line is
T
3
=
{Washington}
{Chicago} .
T ∪ T
2
∪ T
3
=
{Washington}
{LosAngeles, NewYork, Chicago}
{LosAngeles}
{NewYork, Washington, Chicago}
{NewYork}
{Chicago, Washington, LosAngeles}
,
Executing the rest of the steps yields no changes in the final table; therefore, we
have obtained the transitive closure T
+
of the relation T . The relation T
+
can be
matched to the Route predicate in the Datalog rules.
Dostları ilə paylaş: |