JPH07234879A - Information processing apparatus and database search method - Google Patents

Abstract

(57) [Summary] [Purpose] To improve the search speed for the directory information base. [Structure] The logical data structure is a tree structure, and a unique relative distinguished name (RDN) consisting of a combination of attribute type and attribute value
And a directory information base (DIB) 17a in which an entry in which a hash value is added to an attribute value is stored,
A hash calculator 12 that calculates a hash value from the attribute value of the relative distinguished name for the distinguished name (DN) of the target entry, which is a sequence of relative distinguished names from the DIB 17a, and a candidate based on the distinguished name of the target entry. The driver 16 that reads out the following entry compares the hash value added to the read entry with the hash value obtained by the hash calculator 12 to compare only the matching attribute values, and further match the matching entry. The DSA process 11 for comparing the attribute types of the relative identifiers with each other and searching for the target entry from the DIB 17a based on the comparison result.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION The present invention is disclosed in CCITT Recommendation X. The present invention relates to an information processing apparatus and a database search method for realizing a directory system defined by 500.

[0002]

2. Description of the Related Art For example, CCITT Recommendation X. The directory system specified by 500 has a database that stores information (address, name, telephone number, network address, etc.) related to objects such as people and machines as an entry, and provides the user with a function to search the information of the object. It is a system provided.

The database used in this system is called a directory information base (hereinafter abbreviated as DIB), and its logical data structure is a tree structure, and a tree node is an entry. Information such as an address, a name, a telephone number, and a network address regarding the object is stored in the entry as attributes.

The DIB entries have a high-order and low-order relationship. For example, in FIG. 9, the top entry for company X is Japan. Each entry has a relative identification name (RDN).

The relative distinguished name (RDN) is composed of a combination of {attribute type, attribute value}. For example, the entry of company X has a relative distinguished name (RDN) of {"organization name", "company X"}. ing. In addition, the sequence of relative distinguished names (RDN) from the root to an arbitrary entry is distinguished name (D
N).

For example, the entry for "Koichi Hashimoto" shown in FIG. 9 is {{"country name", "Japan"}, {"organization name", company X "}, {" general name ", Koichi Hashimoto"}}. Has a distinguished name (DN). When the user searches for information about "Koichi Hashimoto", this identification name (DN) is designated.

[0007] The directory system traces "Japan" and "company X" from the root of the directory information base (DIB) based on the specified identification name (DN) as described above, and the user is trying to search. Acquires the entry of "Koichi Hashimoto".

[0008]

[Subject to be Solved by the Invention] There are "Company A", "Company X", and "Company B" in the lower entries of "Japan", and they are {"organization name", "company A"} {"organization name", respectively. , “Company X”} {“Organization name”, “Company B”}.

The directory system traces to the entry "Japan", and the identification name (D
N) has a relative distinguished name (RDN) of {“organization name”, “company X”}, the relative distinguished name (RD)
N) is compared with the above three relative distinguished names (RDN), and an entry having a relative distinguished name (RDN) in which both the attribute type and the attribute value match is found.

Normally, entries having the same upper entry have the same attribute type of the relative identification name (RDN) (in the above case, "organization name"). Therefore, when comparing relative distinguished names (RDN), there are very few cases where the attribute types do not match, and in many cases attribute values do not match, resulting in a need for more than necessary comparisons. However, it has been an obstacle to improving the search speed.

Since the attribute value is a character string, it is often a data of 2 bytes or more, and its length varies depending on the entry. Therefore, if the attribute values made up of long character strings are compared as they are, the time required for the comparison will increase in proportion to the length.

The present invention has been made in consideration of the above circumstances, and an object thereof is to provide an information processing apparatus and a database search method for realizing a directory system with an improved search speed.

[0013]

SUMMARY OF THE INVENTION According to the present invention, a logical information data structure is a tree structure, and a directory information base in which an entry having a unique relative identification name (RDN) consisting of a combination of an attribute type and an attribute value is stored. (DIB) and the relative identifier from the root of the directory information base, and the identifier (D) of the target entry to be searched.
N), the driver means for reading out a candidate entry from the directory information base, and the candidate entry read by the driver means, for the candidate entry, the attribute value of the relative identification name of the entry and the target entry. The attribute value of the relative distinguished name in the distinguished name is compared, the attribute type of the relative distinguished name is compared only for the matching entries, and the target entry is searched from the directory information base based on the comparison result. And a search means.

Further, according to the present invention, the logical data structure is a tree structure, an entry having a unique relative identification name (RDN) consisting of a combination of an attribute type and an attribute value, and a hash value added to the attribute value is provided. Hash from the attribute value of the relative distinguished name to the distinguished name (DN) of the target entry to be searched, which consists of the stored directory information base (DIB) and the relative distinguished name from the root of the directory information base. Hash operation means for calculating a value; driver means for reading out a candidate entry from the directory information base based on the identification name of the target entry;
For a candidate entry read by the driver means, the hash value added to the same entry is compared with the hash value obtained by the hash operation means, and only those that match are the attributes of the relative identifier of the same entry. The value is compared with the attribute value of the corresponding relative distinguished name in the distinguished name of the target entry, and the attribute type of the relative distinguished name is compared only for the matching entries, and the directory information base is based on the comparison result. From the target entry to a search means.

Further, a lower entry list table storing the hash value added to the attribute value of the relative identification name of the entry read by the driver means and the address indicating the corresponding entry is created, and the lower means list table is created by the searching means. An entry is searched for in accordance with the lower hash entry list table when performing comparison.

[0016]

According to such a configuration, when the information processing apparatus that realizes the directory system compares the relative distinguished names (RDN) to search for an entry, the attribute value is compared in the relative distinguished name (RDN) comparison. Paying attention to the fact that there are many cases where there is a mismatch in comparing attribute values, by comparing the attribute type only to those that match in the attribute value comparison, it is possible to reduce the total number of comparisons compared to the method of comparing from the attribute type. Can be improved.

Further, by giving a fixed-length hash value to the attribute value, performing a search by that value, and then comparing the attribute values among the matching ones, the attribute values to be compared are narrowed down, and the hash value is hashed. It is possible to improve the search speed as a whole as compared with the case where no value is given.

Further, by using the lower entry list table to retrieve the relative distinguished name (RDN) which is a candidate for the lower entry, the lower entry can be accessed at high speed and the search speed as a whole is improved. be able to.

[0019]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing the schematic arrangement of an information processing apparatus according to this embodiment. As shown in FIG. 1, the information processing apparatus 10 according to the present exemplary embodiment includes a DSA (directory service agent) process 11, a hash calculator 12,
It comprises a memory 13, a driver 16, and a file 17. Information processing device 10 (DSA process 11)
Is the DUA process 20 connected by the communication line 19.
From the directory information base (hereinafter abbreviated as DIB).

The DSA process 11 can directly read / write data from / in the memory 13, and sends the identification name (DN) of the target entry that the user wants to retrieve, which is transmitted via the DUA process 20 connected by the communication line 19. The data is written in the memory 13 and the driver 16 is made to read the lower-order entry candidates for searching the target entry. DSA
Process 11 uses the relative distinguished name (RD) of the distinguished name (DN).
The comparison process is sequentially performed according to N), and the target process is searched by following the entries.

The hash calculator 12 is the DSA process 1
The hash value is calculated from the attribute value of the relative identification name (RDN) of the identification name (DN) of the entry that the user wants to retrieve, which is received by 1.

The memory 13 is for storing the identification name (DN) of the target entry that the user wants to search, the entry read by the driver 16 from the DIB stored in the file 17, and the like.

The driver 16 controls the DIB 17a stored in the file 17 under the control of the DSA process 11.
Then, based on the identification name (DN) stored in the memory 13, the reading of the entry or the like is executed.

The file 17 stores the DIB 17a managed by the information processing apparatus 10, and some entries of the DIB 17a are read by the driver 16 and stored in the memory 13.

Next, the operation of this embodiment will be described.
First, the operation when the hash calculator 12 is not used will be described. First, the identification name (DN) of the target entry that the user wants to search is transmitted to the DSA process 11 via the DUA process 20 and the communication line 19. DSA
The process 11 stores the received identification name (DN) in the memory 13
Write in.

FIG. 2 shows an example of the identification name (DN) corresponding to the target entry written in the memory 13 by the DSA process 11. The distinguished name (DN) is
It is a sequence of relative distinguished names (RDN), {{"country name",
It is assumed that “Japan”}, {“organization name”, “company X”}, {“general name”, “Koichi Hashimoto”}} are stored.
The DIB 17a stored in the file 17 has the configuration shown in FIG.

Next, with reference to the flow chart shown in FIG. 3, the process of extracting the target entry from the DIB 17a will be described. At this time, by comparing the relative distinguished name (RDN), that is, by comparing the relative distinguished name (RDN) in the distinguished name of the target entry with the relative distinguished name (RDN) of each entry stored in the file, the target entry Take out.

Here, the information processing apparatus 10 receives the identification name (DN) of the target entry from the DUA process 20 and stores it in the memory 13, and the information is stored in the DIB 17a based on the identification name (DN). Consider a state where an entry is traced from the root to the entry indicating "Japan".

Now, the DSA process 11 uses the driver 1
6 from DIB17a of file 17 to "Japan"
All the lower-order entry candidates of the entry indicating the are read from the file 17 to the memory 13 (step A1).

FIG. 4 shows candidates for the lower-order entries 21, 22, 23 stored in the memory 13, and shows a state in which the lower-order entry of the entry indicating "Japan" is being read from the file 17 by the driver 16. There is.

As shown in FIG. 4, the lower entries 21, 2
2 and 23 have a relative identification name (RDN), and are {“organization name”, “company A”}, {“organization name”, “company X”}, {“organization name”, “company B”, respectively. "}. Also,
The lower entries 21, 22, 23 are "company A" and "company X".
It has information about “company B” as “other information”.

The DSA process 11 uses the attribute value "company A" of the lower-rank entry 21 which is the first candidate and the attribute value "company X" of the second relative identification name (RDN) of the identification name (DN) of the target entry. Is compared (step A2). Since the results do not match, the next lower entry 22 is taken out (step A4).

Next, the attribute value "company X" of the lower entry 22 is compared with the attribute value "company X" of the second relative distinguished name (RDN) of the distinguished name of the target entry (step A).
2). Since the results match, the attribute type "organization name" of the lower entry 22 is compared with the attribute type "organization name" of the second relative identification name (RDN) of the identification name of the target entry (step A3).

Since the results also match, it is judged that the target entry is under the lower entry 22. With this, the identification name {{"country name", "Japan"}, {"organization name",
From "Company X"}, {"General name", "Koichi Hashimoto"}}, it is possible to trace to {{"Country name", "Japan"}, {"Organization name", "Company X"}}.

In comparison with the attribute type as in the prior art, in the above-mentioned situation, it is necessary to make a total of four comparisons, that is, two attribute type comparisons and two attribute value comparisons. According to the procedure shown, the required result can be obtained by performing the comparison of the attribute type once and the comparison of the attribute value twice, only a total of three comparisons.

In the same manner, as for the lower order entry candidates, the relative identification name (RDN) comparison processing and the number of relative identification names (RDN) in the identification name (DN) are performed in accordance with the flowchart shown in FIG. By repeating
Follow {{"Country name", "Japan"}, {"Organization name", "Company X"}, {"General name", "Koichi Hashimoto"}},
The target entry can be retrieved.

By performing the above processing, the search speed is improved by reducing the total number of comparisons. Next, the operation when the hash calculator 12 is used will be described.

First, the identification name (DN) of the target entry that the user wants to retrieve is the DUA process 20 and the communication line 19
To the DSA process 11 via. The DSA process 11 uses the identification name (D
When N) is received, the attribute value of the relative identification name (RDN) is output to the hash calculator 12, and the identification name is written in the memory 13 together with the hash value obtained there.

FIG. 5 shows an example of the identification name (DN) corresponding to the target entry, which is written in the memory 13 by the DSA process 11. The distinguished name (DN) is
A hash value is added to each of the relative identification names (RDN) shown in FIG.

Next, with reference to the flow chart shown in FIG. 6, the process of extracting the target entry from the DIB 17a will be described. At this time, the comparison process of the hash value of the attribute value is added to the comparison process described with reference to the flowchart in FIG.

The DSA process 11 uses the driver 16 to find all the lower-order entry candidates of the entry indicating "Japan" from the DIB 17a of the file 17 in the file 17.
To the memory 13 (step B1).

FIG. 7 shows candidates for the lower-order entries 31, 32, 33 stored in the memory 13, and shows a state in which the lower-order entry of the entry indicating “Japan” is read from the file 17 by the driver 16. There is.

As shown in FIG. 7, the DIB is stored in the file 17.
When storing the entry of 17a, the relative identification name (RD
The hash value of the attribute value of N) is also stored. That is, the hash values of the attribute values of the relative identification name (RDN) are added to the lower-order entries 31, 32, and 33, and {“organization name”, “company A”, “53”}, and {“organization name”, respectively. , "Company X", "77"}, {"Organization name", "Company B", "4"
9 ″}.

The DSA process 11 compares the hash value of each attribute value before comparing the attribute value of the lower entry and the attribute value of the relative distinguished name (RDN) of the distinguished name of the target entry (step B2). .

The DSA process 11 uses the hash value “53” of the lower entry 31 as the first candidate and the hash value “77” of the second relative identification name (RDN) of the identification name (DN) of the target entry. Are compared (step B2). Since the results do not match, the next lower entry 32 is taken out (step B5).

Next, the hash value "7" of the lower entry 32
7 "is compared with the hash value" 77 "of the second relative distinguished name (RDN) of the distinguished name of the target entry (step B2). Since the results match, the flowchart shown in FIG. 3 is shown below. Similar to steps A2 and A3,
Attribute value comparison (step B3) and attribute type comparison (step B4) are performed, and the required result is obtained based on the comparison result.

According to the procedure of the flow chart shown in FIG. 6, the comparison of the attribute values has two steps, but since the length of a normal attribute value is several tens of bytes, the length of the hash value is, for example, about 1 byte. With this, candidates can be narrowed down with a short comparison processing time. Therefore, as a result, the processing time required for comparing the attribute values can be shortened and the search speed can be improved.

Next, in order to improve the search speed in the processing according to the flowchart shown in FIG.
Functions provided in the above will be described. The driver 16
When reading the lower-order entries 31, 32, 33 from the file 17 into the memory 13, a lower-order entry list table 41 as shown in FIG. 8A is created and stored in the memory 13.

The lower entry list table 31 has a hash value of the attribute value of the relative identification name (RDN) of each lower entry 31, 32, 33 and an address indicating the corresponding lower entry 31, 32, 33.

The driver 16 refers to the lower entry list table 41 when comparing the relative identification name (RDN) according to the flowchart of FIG.
It is possible to extract the lower entry shown in (b) at high speed.

In this way, when the information processing apparatus that implements the directory system compares the relative identification names (RDN) to search for an entry, the attribute values are compared before the attribute types are compared. As a result, by comparing the attribute types only for the matching entries in the attribute value comparison, the total number of comparisons can be reduced and the search speed can be improved.

Further, the hash calculator 12 gives a fixed-length hash value to the attribute value of the identification name (DN) of the target entry, a search is performed using this hash value, and then the attribute values are compared among the matching ones. By doing
Normally, it is possible to reduce the comparison of attribute values that requires a long processing time because the length is several tens of bytes. Therefore, even if the attribute values are compared in two stages, the search speed as a whole is improved. You can

Further, company A, which is a candidate for a lower entry,
By using the lower entry list table 41 to retrieve the relative distinguished names (RDN) of the company X and the company B at high speed, the lower entries can be accessed at high speed, and the search speed as a whole can be improved. it can.

[0054]

As described above, according to the present invention, when a relative distinguished name (RDN) is compared to search for an entry, the attribute type is compared only with those that match in the attribute value comparison. In addition, by giving a fixed-length hash value to the attribute value, performing a search by that value, and then comparing the attribute values among the matching ones, and further speeding up the relative identification name (RDN) that is a candidate for the lower entry. It is possible to improve the search speed for the directory information base by using the lower entry list table for retrieving to the directory.

[Brief description of drawings]

FIG. 1 is a block diagram showing the configuration of an information processing apparatus according to an embodiment of the present invention.

FIG. 2 is a diagram showing an example of an identification name of a target entry to be searched, which is stored in a memory 13 according to the present embodiment.

FIG. 3 is a flowchart for explaining a process of extracting a target entry from the DIB 17a in this embodiment.

FIG. 4 is a diagram showing an example of lower-order entry candidates stored in a memory 13 according to the present embodiment.

FIG. 5 is a diagram showing an example in which a hash value is added to the identification name of a target entry to be searched, which is stored in the memory 13 in the present embodiment.

FIG. 6 is a flowchart for explaining a process of extracting a target entry from the DIB 17a to which hash value comparison of attribute values is added in the present embodiment.

FIG. 7 is a diagram showing an example of a lower-order entry candidate to which a hash value of an attribute value stored in the memory 13 according to the present embodiment is added.

FIG. 8 is a diagram showing an example of a lower entry list table 41 stored in the memory 13 according to the present embodiment.

FIG. 9 is a diagram showing an example of entries of a directory information base (DIB).

[Explanation of symbols]

10 ... Information processing device, 11 ... DSA (directory service agent) process, 12 ... Hash calculator,
13 ... Memory, 16 ... Driver, 17 ... File, 17
a ... Directory information base (DIB), 19 ... Communication line, 20 ... DUA process, 21, 22, 23, 31,
32, 33 ... Lower entry information, 41 ... Lower entry list table.

Claims (5)

[Claims] 1. A logical data structure is a tree structure, and a unique relative identifier (R) consisting of a combination of an attribute type and an attribute value.
Based on the identification name (DN) of the target entry to be searched, which is composed of a directory information base (DIB) in which an entry having DN) is stored and a sequence of the relative identification names from the root of the directory information base. , The driver means for reading out a candidate entry from the directory information base, and the candidate entry read by the driver means, which corresponds to the attribute value of the relative identification name of the same entry and the identification name of the target entry A search unit that compares the attribute value of the relative distinguished name, compares the attribute type of the relative distinguished name only for the matching entries, and searches the target entry from the directory information base based on the comparison result. An information processing apparatus for realizing a directory system characterized by the above. 2. The logical data structure is a tree structure, and a unique relative identification name (R
Directory information base (DIB) in which an entry having a hash value is added to the attribute value is stored.
And a hash calculation means for calculating a hash value from the attribute value of the relative identification name for the identification name (DN) of the target entry to be searched, which consists of a sequence of relative identification names from the root of the directory information base, Driver means for reading out a candidate entry from the directory information base based on the identification name of the target entry, and for the candidate entry read by the driver means, a hash value added to the same entry and the hash The hash value obtained by the calculation means is compared, and only the matched one is compared with the attribute value of the relative identifier of the same entry and the attribute value of the corresponding relative identifier in the identifier of the target entry. Only the matching entries are compared with the attribute type of the relative distinguished name, and the directory information is based on the comparison result. The information processing apparatus for realizing the directory system characterized by the over scan equipped with, search means for searching for the target entry. 3. A lower entry list table storing a hash value added to the attribute value of the relative identification name of the entry read by the driver means and an address indicating the corresponding entry is created, and the lower entry list table is created by the search means. The information processing apparatus according to claim 2, wherein an entry is searched for in accordance with the lower-order hash entry list table when the comparison is performed. 4. The logical data structure is a tree structure, and a unique relative identifier (R) consisting of a combination of an attribute type and an attribute value.
Based on the distinguished name (DN) of the target entry to be searched, which is composed of a sequence of the relative distinguished names from the root of the directory information base from the directory information base (DIB) in which the entry having DN) is stored. A database search method for searching a target entry, wherein a candidate for a lower entry is read from the directory information base according to the identifier of the target entry, and the attribute value of the relative identifier of the read entry and the identifier of the target entry. The attribute type of the relative identifier is compared only with the attribute value of the corresponding relative identifier in the result, and the attribute type of the relative identifier is compared only for the entries whose attribute values match. A database search method characterized by searching a target entry. 5. The logical data structure is a tree structure, and a unique relative identifier (R) consisting of a combination of an attribute type and an attribute value.
Directory information base (DIB) in which an entry having a hash value is added to the attribute value is stored.
From the root of the directory information base, a database search method for searching for a target entry based on the distinguished name (DN) of the target entry to be searched, the directory information comprising: A hash value is calculated from the attribute value of the relative distinguished name for the distinguished name (DN) of the target entry to be searched, which consists of a sequence of relative distinguished names from the root of the base, and the directory is created according to the distinguished name of the target entry. The candidate of the lower entry is read from the information base, the hash value added to the entry is compared with the hash value calculated for the identification name for the read candidate entry, and as a result of this comparison, The attribute value of the relative distinguished name of the entry read out only for the entry with the matching hash value and the target entry The attribute value of the relative distinguished name in the corresponding distinguished name is compared, and as a result of this comparison, the attribute type of the relative distinguished name is compared only for the entries whose attribute values match, and based on this comparison result, the directory information A database search method comprising searching the target entry from a base.