Algebraic approach to logical inference implementation

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.

---