JPH01276237A - Selector for candidate term to be unified - Google Patents

Abstract

PURPOSE:To cause a term retrieval to be high-speed by detecting a term to be singled with a conditions term from the set of retrieval terms not to contain a variable. CONSTITUTION:Since a third characteristic value M is made into a mask pattern to mask the variable part of the conditions term, by executing the AND of a first characteristic value D and the third characteristic value M, a value, in which only a part corresponding to the variable part of the conditions term is replaced with O to the characteristic value D of the retrieval term, can be obtained. Consequently, the value of a constant part contained in the characteristic value D of the retrieval term remains as information as it is, and in comparison with a characteristic value Q of the conditions term, as to different constants, the difference can be detected. Thus, a probability that the term without a singling probability in fact is decided to have the singling probability by mistake can be widely reduced, and the term retrieval can be made high- speed.

Description

DETAILED DESCRIPTION OF THE INVENTION It relates to a technique for selecting unification candidate terms from a set, and in particular, a unification method that converts search terms and conditional terms into characteristic values of predetermined bits to verify unification possibility. The present invention relates to a selection device for candidate items.

(Conventional technology) In knowledge base systems, file systems, etc.
When performing a search that involves unification of term data including variables, in order to narrow down the search target and improve search efficiency, we first select a unit that can be unified with the search term data from a set of term data to be searched. Then, selection of candidate terms is performed. Since this type of selection processing requires high-speed execution, various methods have been used to convert search term data into forms suitable for high-speed arithmetic processing. One of them is F
E W (f'1eld encode word)
The law is known (Wlse, M. J., Powers
,D,MJ,,-Indexing PROLOGCl
auses via Superimposed Co
de word and Field Encode W
Ords', In Proceedings of th
eIEEE C0nrerenCe Orl Logi
c PrOgrao+Ing, AtlantiC Three terms, f (a) f (a, Suppose that Note that among the elements constituting each term here, f, a, and b written in lower case letters are constants, X and Y written in upper case letters are variables, and the elements in parentheses are as follows.
This is the argument of the element attached to the left of the left parenthesis.

First, these search terms and condition terms are each converted into characteristic values with an appropriate number of bits. For example, these characteristic values are 16
First, since the search term f(a) consists of a function f with one argument and a constant a, the third
As shown in Figure (a), a 16-bit field is divided into, for example, 10 bits and 6 bits, the ASCII code 66H (hexadecimal representation) of the function f is assigned to the upper 10 bits, and the lower 6 bits are As shown in Figure 3(b), the 16-bit field is divided into, for example, 8 bits, 4 bits, and 4 bits, and the ASCII code 66H of one function f is assigned to the upper 8 bits. , ASCII code 6 of the constant a and IH, which is the lower 4 bits of IH, are assigned to the middle 4 bits, and 1 is assigned to all the lower 4 bits corresponding to the variable X. Similarly, the search term f (a, g (b)) is a function f with two arguments
, constant a, and arguments are composed of one constant g1 and constant s, so we divide the 16-bit field into, for example, 8 bits, 4 bits, 2 bits, and 2 bits, as shown in Figure 3(C). , the ASCII code 66H of the function f is assigned to the upper 8 bits, IH, which is the lower 4 bits of the ASCII code 61H of the constant a, is assigned to the next 4 bits, and the following 2 bits are assigned the constant g, respectively. Lower 2 bits of ASCII code of b 3H, 2H
Assign each. As a result, the characteristic value 1 of each search term
Obtain ゜2.3.

On the other hand, the conditional term f (Y, b) is a function 66 with two arguments.
H is assigned, all 0s are assigned to the middle 4 bits corresponding to the variable Y, and code 2H corresponding to the constant b is assigned to the lower 4 bits. As a result, characteristic value 4 of the conditional term is obtained.

When characteristic values 1 to 4 of each search class and condition term are obtained in this way, the characteristic value of the search class is D1, the characteristic value of the condition term is Q, and the bitwise AND result of D and Q and Q are compare. As a result, if DAQ≠Q, it is determined that the search class and the conditional term cannot be unified. For example, f (a) and f (Y, b) are 00ku1100110100001 (D )A
0110011000000010 (Q)0
00(1000000(1000(10≠Q), so it is determined that there is no unification possibility. Also, the search class f (
a, X) and conditional term f (Y, b) are 0110011000011111 (D) public'b
') is 1, 0110011000011110 (D
)A (H100I100OOOO mouth 10
(Q) 11il 1・ 0110011000000
010-Q--1~1. .

Therefore, it is determined that there is a possibility of unification.

However, for the last example, the search class f (
a, g (b) ) and the conditional term f (Y, b) are
Since the second arguments of each are clearly different, in reality,
Even though unification is not possible, it is determined that unification is possible. In other words, in the FEW method, when calculating the characteristic value for each element of the conditional term, there are cases where the element is a variable and the corresponding bit is set to 0, and cases where the element is not a variable and the bit happens to be 0 when calculating the characteristic value. is treated in exactly the same way as the case where is set, so there is a high probability that it will be determined that unification is possible in the determination based on the characteristic value even though in reality it is not possible to unify.

For this reason, there is a problem in that the effect of narrowing down unification candidates is low and it is not possible to sufficiently speed up the term search.

(Problem to be solved by the invention) Although this method is excellent in that it can determine unification possibility, in reality it judges things that cannot be unified as unification possible. There was a problem in that the probability was high and term retrieval could not be made sufficiently fast. On the other hand, there are actually many cases in which variables are not included in the search class that is the object of the search.

Therefore, an object of the present invention is to provide a selection device for unification candidate terms that can be expected to have a sufficient effect of narrowing down the unification candidate terms when such a search class does not include a variable.

[Structure of the Invention] (Means for Solving the Problems) The unification candidate term selection device of the present invention includes a first method for determining a first characteristic value of a predetermined bit from a search class consisting only of constants. a characteristic value calculation means, a second characteristic value calculation means for calculating a second characteristic value Q of the same bit as the first characteristic value from a condition term consisting of constants and/or variables; a third characteristic value calculation means for calculating a third characteristic value M of the same bit as the first characteristic value;
and determining means for determining that there is no gender.

:Here, the first characteristic value is the search type □
The bit field is divided according to the structure, and each divided field is associated with the numerical conversion value of each element of the search term, and the second characteristic value Q is divided according to the structure of the condition term. Divide the bit field, make the numeric conversion value of the constant element correspond to the divided field to which the constant element corresponds, and set all bits of the divided field to which the variable element corresponds to 0.
The third characteristic value M is a value in which the bit field is divided according to the structure of the search class, 1 is made to correspond to all bits of the divided field to which the constant element corresponds, and the variable element is This is a value in which O is associated with all bits of the corresponding division field.

Bitwise logical sum may be used instead of bitwise logical product.

By logically multiplying, only the part corresponding to the variable part of the conditional term is replaced with 0 for the characteristic value of the search class.1. The double value is obtained. Therefore, the value of the constant part included in the characteristic value of the search class remains as information, and the characteristic value Q of the conditional term
In comparison with , it is possible to detect the difference between different constants.

Therefore, according to the present invention, it is possible to significantly reduce the probability that a term that is actually not unifiable is erroneously determined to be unifiable, thereby speeding up the forward search. be able to.

Further, for the characteristic value Q, the same effect can be obtained when the logical sum for each bit is used instead of the logical product for each divided foot to which the variable element corresponds.

(Example) Hereinafter, an example of the present invention will be described with reference to the drawings.

and i, and input the conditional terms to obtain the second characteristic value Q and the third ′
1 Calculating means for calculating characteristic values Q for calculating respective characteristic values M, 1;
2 and characteristic value M calculation means 13, and these calculation means 11
The determination means 14 compares the characteristic values calculated in steps 13 to 13, Q, and (DAM) from M and outputs the possibility of unification for the search class as a determination result.

In the above configuration, it is assumed that f (a) f (a, g (b)) is given as a search class and f (Y, b) is given as a conditional term. When the characteristic values, Q, and M are set to 18 bits, the calculating means 11.12 converts the search class and condition term into characteristic values, Q, and Q, respectively, in exactly the same manner as in the conventional FEW method.

That is, since the search class f(a) consists of one argument, a constant f and a constant a, the calculation means 11 calculates
As shown in Fig. 2(a), the 16-bit pitch "=-1 is matched. As a result, the characteristic value D? of the search class f(a) becomes the value shown by 21 in Fig. 2(a). f
For (a, g (b)), the arguments are two functions f, a constant a, and the arguments are one constant g1 and a constant For example, convert a 16-bit field to 8-bit,
Divide into 4 bits, 2 bits, and 2 bits, assign the ASCII code 66H of the function f to the upper 8 bits, assign IH, which is the lower 4 bits of the ASCII code 61H of the constant a, to the next 4 bits, and proceed as follows. The lower two bits 3H and 2H of the ASCII code of constants g and b are assigned to bits 2 and 2, respectively. As a result, the characteristic value of the search class f (a, g (b)) becomes the value shown at 22 in FIG. 2(b).

Regarding the conditional term f (Y, b), since the arguments are composed of two functions f, a variable Y, and a constant S, the calculation means 11 calculates For example, you can convert a 16-bit field into 8-bit, 4-bit, and 4-bit fields.
Divide into bits and allocate the upper 8 bits 2H. As a result, the characteristic value Q of the conditional term becomes the value indicated by 23 in FIG. 2(C).

On the other hand, the calculation means 13 for the characteristic value M calculates the condition term f (
The 16-bit field of the characteristic value of Y, b) is shown in Figure 2 (
As shown at 24 in Figure C), it is divided into 8 bits, 4 bits, and 4 bits, and the constant part as shown at 24 in Figure (c) is divided into fields of upper 8 bits and lower 4 bits corresponding to constants f and b. This is a mask pattern that extracts only the

Next, the determining means 14 determines each of the above characteristic values and Q.

Input M to determine whether the search term and the condition term can be unified. That is, first, the search term f (a) and the condition term f (y, b)
For 0001100110100001 (D)A
1111111100001111 (M)≠01
Since there are 10011000000010 (Q), it is determined that there is no possibility of unification. Also, the search term f (
a, g (b) ) and the conditional term f (Y.

b) means 0110011000011110 (D) Δ 1
111111100001111 (Q)≠011
0011000000010 (Q), so
In this case as well, it is determined that there is no possibility of unification.

As can be seen from this example, in the conventional FEW method, if bit 0 exists in the characteristic value of the conditional term, regardless of whether the value of the corresponding bit in the characteristic value of the search term is O or 1,
As far as that bit is concerned, it could not be determined that unification is not possible, but in the unification candidate term selection device according to this embodiment, the masking effect of the variable part of the characteristic value Q on the conditional term is
Since the important information obtained by the third characteristic value M in the characteristic value of the search term is not lost, the accuracy of the determination can be dramatically improved. Moreover, conventional FE
Compared to the W method, it is possible to apply characteristic values to search terms.

The first method is to apply the method according to the above embodiment to search terms that do not include variables, and apply the FEW method to terms that include variables. This method provides a better search method than the FEW method alone.

- For example, increase the size of the characteristic value for the search term by one bit and set a flag there indicating whether the term contains a variable. When actually searching for a term, the flag bit is first referenced, and if it does not contain a variable, this method is applied, and if it does contain a variable, FEW is applied.
Apply the law.

The second method is to prepare two characteristic values for the search term as well as for the condition term. That is, the characteristic value Q is obtained in the same manner as the characteristic value Q of the conditional term. In addition, a new characteristic value is introduced, and it is obtained in the same manner as the characteristic value M of the conditional term. In this way, the following equation can be used to determine the possibility of unification based on characteristic values.

By doing this, we can compare the parts where both are not variables. This method also provides better determination results than the FEW method. However, since it is necessary to store two characteristic values for each search term, it requires more storage area than the FEW method.

In addition, the present invention prepares two characteristic values for the conditional term, a characteristic value Q corresponding to the constant and the functor, and a characteristic value M indicating the position of the variable, and the characteristic value for the constant and the functor of the search term. By masking the difference with the characteristic value M indicating the position of the variable in the conditional term, characteristic values corresponding to constants and function values can be accurately compared with each other, thereby improving the accuracy of judgment. Therefore, the characteristic value Q corresponds to 1 to the part that is a variable, the characteristic value M corresponds to O to the part that is not a variable, and 1 is set to the part that is a variable. Bitwise OR may be used instead of bitwise AND. Also, as another example, instead of using the characteristic value M, it is also possible to memorize the appearance position of the variable and separately perform an operation equivalent to the bitwise AND of the characteristic value M and the characteristic value M. Since conditional terms and terms that can be unified can be accurately detected from a set of search terms that do not exist, it is possible to greatly contribute to speeding up term searches.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of a unitization candidate term selection device according to an embodiment of the present invention, FIG. 2 is a diagram showing each characteristic value obtained by the same device, and FIG. 3 is a diagram of a conventional FEW method. FIG. 3 is a diagram showing each characteristic value used. 11... Means for calculating characteristic value, 12... Means for calculating characteristic value Q, 13... Means for calculating characteristic value M, 14...
Judgment means. Applicant Director of the Agency of Industrial Science and Technology Kozo Iizuka Figure 1 (a) (b) Figure 2 (a) (b) Figure 3
Ward

Claims (2)

[Claims] (1) A first characteristic value calculation means for calculating a first characteristic value of a predetermined bit from a search term consisting only of constants; a second characteristic value calculation means for calculating a second characteristic value of the same bit; a third characteristic value calculation means for calculating a third characteristic value of the same bit as the first characteristic value from the condition term; The result of the logical product of the first characteristic value and the third characteristic value is compared with the second characteristic value, and if the two are not the same, the search term can be unified with the condition term. and determining means for determining that the first characteristic value has no property, and the first characteristic value divides the bit field according to the structure of the search term, and assigns a numerical conversion value of each element of the search term to each divided field. The second characteristic value is a value that divides the bit field according to the structure of the conditional term, associates the numerical conversion value of the constant element with the divided field to which the constant element corresponds, and divides the bit field into a variable element. 1 for all bits of the corresponding split field
The third characteristic value is a value that divides the bit field according to the structure of the search term, and makes 1 correspond to all bits of the divided field to which the constant element corresponds,
1. A unification candidate term selection device, wherein a variable element has a value in which all bits of a corresponding divided field correspond to 0. (2) The second characteristic value is obtained by dividing the bit field according to the structure of the conditional term, making the numerical conversion value of the constant element correspond to the division field to which the constant element corresponds, and dividing the bit field to which the variable element corresponds. The third characteristic value is a value that corresponds to 0 to all bits of the field, and the third characteristic value divides the bit field according to the structure of the search term, and corresponds to 0 to all bits of the divided field to which the constant element corresponds. and the variable element is a value in which 1 corresponds to all bits of the corresponding divided field, and the determining means is configured to calculate the result of the logical sum of the first characteristic value and the third characteristic value and the second characteristic value. and a characteristic value of the unification candidate term according to claim 1, wherein if the two are not the same, it is determined that the search term has no possibility of unification with the conditional term. selection device.