JP2008198236A - Structured document management system - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To maintain the strictness of retrieval while maintaining satisfactory update retrieval performance by constructing an index of a category suitable to each element. <P>SOLUTION: A retrieval expression processing part in a data retrieving part 16 analyzes a retrieval expression given from the outside, extracts a retrieval condition and acquires a set of candidates for retrieval results satisfying the retrieval condition. A value extracting part in an index managing part 15 acquires a history of retrieval conditions applied to the corresponding element of the elements included in a structured document stored in a structured document DB 21. An index category determining part in the index managing part 15 determines an index category on the basis of the largest retrieval category in the history of the retrieval conditions applied to the corresponding element of the elements included in the structured document to which an index should be attached. An index constructing part in the index managing part 15 constructs indexes of the index category determined by the index category determining part and stores them in an N-gram index DB 22, a word index DB 23 or a B-tree index DB 24. <P>COPYRIGHT: (C)2008,JPO&INPIT

Description

  The present invention provides a structured document management system suitable for constructing an index of a structured document and storing it in the index storage means in order to speed up the search of the structured document stored in the structured document storage means. About.

  In recent years, structured documents having a logical structure represented by XML (Extensible Markup Language) have become widespread. Structured documents are generally stored and used in a database arranged on a disk (disk drive).

  Further, with the spread of structured documents, an information retrieval system that retrieves information such as documents or elements, attributes, values, etc. that match a search condition specified by a user from a database in which one or more structured documents are accumulated Have been developed. In this type of information search system, an index is generally assigned to a document to be searched, and further to elements and values in the document (see, for example, Patent Document 1).

  In the retrieval of structured documents in the information retrieval system, retrieval is performed by structure, value, or a combination thereof. As an index technique applied to this search, for example, an index technique using N-gram (N-gram) (N-gram index technique) and an index technique using morphological analysis (morpheme index technique) are known.

N-gram index technology:
In this technique, the character string is sequentially separated into N characters (N-grams) while being shifted one character at a time from the beginning of the character string (value), and an index ( Index record) is created. Thus, for example, if N = 2 and the value is “Aiueo”, six types of indexes “Ah” / “Ai” / “Nay” / “Up” / “Eo” / “O” ( Index record) is created. For example, when searching for a value including a partial character string “Ueo” for this index, first, based on the index, the positions of “Ue” and “Eo” are searched, and A document including “Eo” and a position in the document are specified, and a common set of values including these is set as a search result candidate.

Morphological analysis index technology:
In this technique, a word is extracted from a value (character string). As a method of dividing a character string into words, “morpheme analysis” is known. An index (index record) is created for each extracted word. Thus, for example, for the value “Today is sunny”, two words “Today” / “Sunny” are extracted and created as indexes. For example, when searching for a partial character string of “sunny sky” with respect to this index, the position of “sunny sky” is first searched based on the index, and the document including the “sunny sky” and the position in the document are specified. Search result candidates.
JP 2003-30235 (paragraphs 0030 to 0053, especially paragraph 0044, FIG. 5)

  In the index technology applied in the above-described conventional information retrieval system, for example, an index technology using N-grams, the index amount increases, and the total index size is a huge size exceeding 10 times the original text size depending on the implementation. It can be a thing. In this case, the disk update amount of the index update accompanying the document update increases, and the update performance deteriorates. Also in the search, depending on the search contents, the disk reference amount required for the index search increases, and the reference performance (search performance) also deteriorates. Furthermore, since the index size is huge, it is necessary to prepare a large disk capacity to accommodate it.

  On the other hand, in an index technique using morphological analysis, a character string that cannot be extracted by morphological analysis cannot be used as a search condition, so that a strict search cannot be performed. In the above example, when a search such as “acquire a value including“ nari ”” is requested, a correct result cannot be obtained.

  Searches used in normal applications require a strict search (the former), a slight strictness of the search, or a search other than a meaningful word (the latter) There are two main types. An index technique based on N-grams is required for the former search, but an index technique based on morphological analysis is sufficient for the latter search.

  In addition, when the present inventor considers the search in general, the object of the strict search is data that is classified into content attributes and bibliographic information such as title, keyword, person name, and place name, and is generally a character string. I came to realize that the length is often short. Such data generally has a rule in the way of description. On the other hand, for example, data classified into a content body such as a bibliographic text generally has a long character string length. As described above, in the case of long data such as a bibliographic text that is not detailed with tags, a strict search or a search with a character string that does not become a word often has no meaning.

  The present invention has been made in consideration of the above circumstances, and its purpose is to maintain the strictness of search while maintaining good update search performance by constructing an index of a type suitable for each element for each element. It is to provide a structured document management system that can do this.

  According to one aspect of the present invention, in order to speed up retrieval of a structured document stored in a structured document storage unit, a structured document index is constructed and stored in the index storage unit. A system is provided. This system analyzes a search expression given from the outside, extracts a search condition, acquires a set of search result candidates that match the search condition, and is stored in the structured document storage means. For each element included in the structured document, search history acquisition means for acquiring a history of search conditions extracted by the search expression processing means applied to the element, and a structure to be indexed For each element included in the document, an index type determining unit that determines an index type based on the most frequently searched type in the history of search conditions applied to the element acquired by the search history acquiring unit; Based on the index type determined for each element by the index type determination unit, an index of the determined index type corresponding to the element is constructed and stored in the index storage unit. And a pull construction means.

  As described above, an index type suitable for processing the search condition is selected for each element from the history of search conditions applied to individual elements in the past, and an index of the index type is constructed. With the configuration, the search performance can be improved. Here, for example, when exact match type search conditions are frequently applied, a B-tree index suitable for processing of complete match type search conditions is selectively constructed, and when partial match type search conditions are frequently applied. Is preferably constructed by selectively constructing an N-gram index suitable for partially matching type search condition processing or a full-text search index such as a word index by morphological analysis.

  Also, focusing on the fact that it is possible to estimate search conditions that are highly likely to be applied to the element from the name of the element, an index type suitable for processing the estimated search condition is determined for each element. Search performance can also be improved by selecting and configuring an index of that index type. For example, a B-tree index is selectively constructed with an element name of “body” because the specification of a search condition of an exact match type or a size comparison type is predicted for an element value having an element name of “date”. Since partial match type search conditions are expected to be specified for element values, it is preferable to selectively construct an index for full text search such as an N-gram index or a word index based on morphological analysis.

In addition, if a data type is given as part of the structure (schema) specification of a structured document, an index of an index type suitable for processing the data type according to the data type of the element value Even with the configuration of constructing, the search performance can be improved. Here, for example, a numerical type B-tree index is selectively constructed for a numeric type, an index is not constructed for a binary type, and a full-text search index is selectively constructed for a character string type. It is good to build.
According to another aspect of the present invention, in order to speed up retrieval of a structured document stored in the structured document storage unit, a structured document index is constructed and stored in the index storage unit. A document management system is provided. This system analyzes a search expression given from the outside, extracts a search condition, obtains a set of search result candidates that match the search condition, and is stored in the structured document storage means. Among the elements included in the structured document to be indexed, the schema specifying means for specifying the structure including the data type of the value of the element included in the structured document. For the element specified by the schema specifying means, the index type determining means for determining the index type based on the data type specified by the schema specifying means, and the element determined by the index type determining means for each element. An index construction unit configured to construct an index of the determined index type corresponding to the element based on the index type and store the index in the index storage unit.

  According to the present invention, attention is paid to the fact that the strictness required for the search depends on the element, and by building an index of a type suitable for the element for each element, while maintaining good update search performance The strictness of search can be maintained.

Hereinafter, an embodiment of the present invention will be described with reference to the drawings.
FIG. 1 is a block diagram showing a configuration of an information search system according to an embodiment of the present invention. This information retrieval system mainly includes a database management system (DBMS) 10, a structured document database (structured document DB) 21, an N-gram index database (N-gram index DB) 22, and a word index. A database (word index DB) 23, a B-tree (B * Tree) index database (B-tree index DB) 24, a setting file 25, an index type dictionary 26, and a log file 27 are provided. The structured document DB 21, the N-gram index DB 22, the word index DB 23, and the B-tree index DB 24, the setting file 25, the index type dictionary 26, and the log file 27 are data storage means accessible from the DBMS 10. Is placed in a disk drive (disk) (not shown).

  The structured document DB 21 is used to store document data of at least one structured document (for example, a plurality of structured documents). The N-gram index DB 22 is used to store index records (N-gram index) created by the N-gram index technique (N-gram index system), and the word index DB 23 is a morpheme analysis index technique (morpheme analysis index system). Used to store the index record (word index) created in The B-tree index DB 24 configures and stores a B-tree by adding hierarchical index record information for efficiently searching the index record to the index record that holds the relationship between the key value and the data itself. Used to do.

  The setting file 25 is used to set in advance a character string length threshold necessary for determining an index type suitable for searching for a value from the length (value length) of each element. The index type dictionary 26 is used to set an index type (that is, an index method) suitable for searching the value of each element included in the structured document. Here, for each element name, the index type dictionary 26 is used to hold the name (element name) and an index type suitable for searching the element value of the element name as a set. It is done. In other words, the index type dictionary 26 is used to hold an index type suitable for searching for the value of an element of the element name in association with the element name of each element. The log file 27 is used to accumulate each element value included in the structured document stored in the structured document DB 21 as log information. The log file 27 may be configured such that the length of the value of each element (value length) is accumulated as log information.

  The DBMS 10 is a structured document management system that manages each of the structured document DB 21, the N-gram index DB 22, the word index DB 23, and the B-tree index DB 24 (database). The DBMS 10 includes an access processing unit 11, a structured document management unit 12, and a search engine 13. The DBMS 10 is realized by reading and executing a software program (database management program) for database management installed in the computer system by the computer system (CPU in the computer system). This program is stored in advance in a computer-readable storage medium (a magnetic disk typified by a floppy (registered trademark) disk, a CD-ROM, an optical disk typified by a DVD, a semiconductor memory typified by a flash memory, etc.). Can be distributed. Further, this program may be downloaded (distributed) via a network.

  The access processing unit 11 processes various DB access requests from clients (client terminals) that use the information search system of FIG. This client may be either a computer terminal that implements the information search system of FIG. 1 or a terminal connected to the computer via a network. The access processing unit 11 receives an update request from the application 30 and causes the structured document management unit 12 to perform update processing (data update and index update) indicated by the update request. The data update and index update here include storage of new data and construction (creation) of an index, respectively. In the following description, index update (reconstruction) may be represented by index construction. The access processing unit 11 also receives a search request from the application 30 and causes the search engine 13 to perform information search indicated by the search request.

  The structured document management unit 12 includes a data update unit 14 and an index management unit 15. In response to an update request from the application 30, the data update unit 14 performs an update process for the structured document DB 21. The index management unit 15 manages the construction of an index to be stored in the N-gram index DB 22, the word index DB 23, or the B-tree index DB 24 in response to an update request from the application 30. The construction of this index includes the concept of updating (rebuilding) the index stored in the N-gram index DB 22, the word index DB 23, or the B-tree index DB 24 in order to avoid complicated explanation. . The index management unit 15 determines which of the N-gram index DB 22, the word index DB 23, or the B-tree index DB 24 is to be constructed based on the contents of the setting file 25, index type dictionary 26, or log file 27. decide.

  The search engine 13 includes a data search unit 16 and an index reference unit 17. In response to a search request from the application 30, the data search unit 16 searches the structured document DB 21 for a structured document that matches the search request or the value of an element in the structured document. At this time, the data search unit 16 passes the search condition to the index reference unit 17, thereby obtaining a structured document that matches the search condition or a set of element positions in the structured document (a set of search result candidates). Received from the index reference unit 17.

  FIG. 2 is a block diagram showing the structure of the structured document management unit 12 in FIG. 1 in association with the DBs 21 to 24 and the like. As described above, the structured document management unit 12 includes the data update unit 14 and the index management unit 15. The index management unit 15 includes a character string length threshold value determination unit 151, a value extraction unit 152, an index construction control unit 153, and an index construction unit 154.

  The character string length threshold value determination unit 151 selects an index type suitable for the search of the value from the length (value length) of the element in the document (partial document) to be updated by the data update unit 14. A character string length threshold necessary for the determination is determined. In the first threshold value determination mode, the character string length threshold value determination unit 151 determines the character string length threshold value set in the setting file 25 as a target character string length threshold value as it is. In the second threshold value determination mode, the character string length threshold determination unit 151 determines the character string length from the statistical information (distribution) of the value length of each element included in each structured document stored in the structured document DB 21. Determine the threshold. Information on the value length of each element is accumulated in the log file 27.

  The value extraction unit 152 extracts the value of the element in the document (partial document) that is the target of data update by the data update unit 14 and the position in the document. In the first index type determination mode, the index construction control unit 153 determines the value of the element value extracted by the value extraction unit 152 and the character string length threshold value determined by the character string length threshold value determination unit 151. Determine the index type (index method) suitable for value retrieval. In the first index type determination mode, at the time of building an index, each element of the structure (schema) of the structured document to be stored will be determined based on the statistics and threshold values of the value length of each element accumulated in the log information in the past. The type of index to be constructed may be determined in advance. Further, in the second index type determination mode, the index construction control unit 153 is suitable for the element of the name (element name) based on the name of the element extracted by the value extraction unit 152 and the index type dictionary 26. The index type (index method) is determined. The index construction control unit 153 controls the index construction unit 154 to construct an index of a type suitable for searching for the extracted element value. The index construction control unit 153 accumulates corresponding element values in the log file 27 as log information when constructing the index.

  Index construction unit 154 includes a gram division unit 155, an N-gram index update unit 156, a morpheme analysis unit 157, a word index update unit 158, and a B-tree index update unit 159. The gram dividing unit 155 receives element value and position information from the index construction control unit 153 and divides the value into N gram to create a gram string. The N-gram index update unit 156 constructs an N-gram index for the N-gram index DB 22 from the created gram string and position information. The morpheme analysis unit 157 receives element value and position information from the index construction control unit 153, and morphologically analyzes the value (character string) to extract words. The word index update unit 158 constructs a word index for the word index DB 23 from the extracted words and position information. The B-tree index update unit 159 receives element value and position information from the index construction control unit 153 and constructs a B-tree index for the B-tree index DB 24.

  FIG. 3 is a block diagram showing the configuration of the search engine 13 in FIG. 1 in association with the DBs 21 to 24 and the like. As described above, the search engine 13 includes the data search unit 16 and the index reference unit 17.

  The data search unit 16 includes a search formula processing unit 161 and a data reference unit 162. The search expression processing unit 161 analyzes the search expression indicated by the search request from the application 30, extracts a condition (that is, search condition) necessary for the search, and sets a search result candidate (structure) that matches the search condition. A set of element positions in the structured document or structured document). The search expression processing unit 161 also causes the data reference unit 162 to refer to search result candidates from the structured document DB 21.

  The index reference unit 17 includes a character string length threshold value determination unit 171 similar to the character string length threshold value determination unit 151 in the index management unit 15, an index reference control unit 172, a gram division unit 173, and an N-gram index search unit 174. A morpheme analysis unit 175, a word index search unit 176, and a B-tree index search unit 177. The index reference control unit 172 uses the character string length included in the search condition given from the search expression processing unit 161 and the character string length threshold value determined by the character string length threshold value determination unit 171 to determine the index to be referred to. Determine the type. The index reference control unit 172 passes the search condition to the gram division unit 173, the morpheme analysis unit 175, or the B-tree index search unit 177 corresponding to the determined index type, and refers to the corresponding index. The gram dividing unit 173 divides a character string included in the search condition into N gram to create a gram string. The N-gram index search unit 174 searches the N-gram index DB 22 for an N-gram index record corresponding to the created gram string, and returns the position information to the index reference control unit 172. The morphological analysis unit 175 extracts words by performing morphological analysis on the character string included in the search condition. The word index search unit 176 searches the word index DB 23 for a word index record corresponding to the extracted word, and returns information on the position to the index reference control unit 172. The B-tree index search unit 177 searches the B-tree index DB 24 for a B-tree index record corresponding to the character string included in the search condition, and returns the position information to the index reference control unit 172.

  FIG. 4 is a block diagram showing the configuration of the index construction control unit 153 in FIG. The index construction control unit 153 includes a value length calculation unit 153a, a comparison unit 153b, and an index type determination unit 153c. The value length calculation unit 153 a calculates the length (value length) of the value of the element extracted by the value extraction unit 152. The comparison unit 153b compares the value length calculated by the comparison unit 153b with the character string length threshold value determined by the character string length threshold value determination unit 151. The index type determination unit 153c performs an index type determination process specific to the index type determination mode. In the present embodiment, two types, a first index type determination mode and a second index type determination mode, are prepared. In the first index type determination mode, the index type determination unit 153c determines the index type to be applied to the corresponding element value according to the comparison result of the comparison unit 153b. In the case of the second index type determination mode, the index type determination unit 153c refers to the index type dictionary 26 by the name of the corresponding element (element name), and applies it to the element value of the element name. The index type to be determined is determined.

  Next, index update processing in the information search system of FIG. 1 will be described with reference to the flowchart of FIG. First, it is assumed that an update request for adding data or overwriting data is sent from the application 30 on the client terminal to the information search system of FIG. This update request is accepted by the access processing unit 11 in the DBMS 10. Then, the access processing unit 11 notifies the update request from the application 30 to the data update unit 14 in the structured document management unit 12.

  In accordance with the notified update request, the data update unit 14 newly stores data (document data) specified by the update request in the structured document DB 21 or data (document data) specified by the update request. Alternatively, the corresponding data in the structured document DB 21 is updated with the partial document data). At the same time, the data update unit 14 passes the data (document data or partial document data) to the value extraction unit 152 in the index management unit 15 together with the storage position information in the structured document DB 21.

  The value extraction unit 152 extracts all element values of the structured document to be indexed from the data passed from the data update unit 14. For extracting the element value, if the structured document is XML, for example, an XML parser can be used. The value extraction unit 152 passes all the element values extracted from the data passed from the data update unit 14 to the index construction control unit 153 together with the storage position information in the structured document DB 21.

  The index construction control unit 153 determines the index type mode (step S1). If the first index type mode is designated as the index type mode, the index construction control unit 153 requests the character string length threshold value determining unit 151 to determine the character string length threshold value. Then, the character string length threshold value determination unit 151 determines the threshold value determination mode (step S2).

  If the first threshold value determination mode is designated as the threshold value determination mode, the character string length threshold value determination unit 151 reads the character string length threshold value set in the setting file 25 and builds the threshold value as an index. It determines as a character string length threshold value which the control part 153 uses (step S3). On the other hand, if the second threshold determination mode is designated as the threshold determination mode, the character string length threshold determination unit 151 stores the log information stored in the log file 27 in the structured document DB 21. The distribution (statistical information) of the value length of each element included in the structured document is calculated (step S4). Then, the character string length threshold determining unit 151 determines the character string length threshold used by the index construction control unit 153 from the distribution of the value lengths of the elements (step S5). Thus, in the second threshold value determination mode, the character string length threshold value suitable for each element included in the structured document stored in the structured document DB 21 is dynamically determined. In the present embodiment, in the above distribution, a value length that bisects the number of elements is determined as a character string length threshold. However, the method of determining the character string length threshold is not limited to this.

  The threshold value determination mode can be designated from the application 30 in accordance with a user operation in accordance with an inquiry from the access processing unit 11. The index type mode can also be specified from the application 30 according to the user's operation. Furthermore, the threshold determination mode or the index type mode can be held in advance as a database attribute. In the present embodiment, when the first index type mode is designated as the index type mode, the threshold value determination mode is valid.

  The character string length threshold value determined by the character string length threshold value determination unit 151 is passed to the index construction control unit 153. The value length calculation unit 153a in the index construction control unit 153 calculates the length of the value, that is, the value length, for each element value extracted by the value extraction unit 152. The comparison unit 153b in the index construction control unit 153 compares the value length of each element calculated by the value length calculation unit 153a with the character string length threshold value determined by the character string length threshold value determination unit 171. To do. Then, the comparison unit 153b passes the comparison result for each value length of each element to the index type determination unit 153c in the index construction control unit 153. The value length calculation unit 153a and the comparison unit 153b may be configured to operate only when the first index type mode is designated.

  When the first index type mode is designated, the index type determination unit 153c is optimal for the value of each element extracted by the value extraction unit 152 according to the comparison result of the comparison unit 153b. Determine the index type. Here, if the length of the element value exceeds the character string length threshold (step S6), the index type determination unit 153c determines the word index as the optimal index type for the value (step S7). In this case, the index type determination unit 153c passes the set of the value of the corresponding element and the storage position information in the structured document DB 21 to the morpheme analysis unit 157 (step S8). On the other hand, if the length of the element value is equal to or smaller than the character string length threshold (step S6), the index type determination unit 153c determines the N-gram index as the optimal index type for the value (step S9). . In this case, the index type determination unit 153c passes the set of the value of the corresponding element and the storage position information in the structured document DB 21 to the gram dividing unit 155 (step S10).

  The gram dividing unit 155 divides the element value (character string) into N gram (length N vocabulary) when the element value (character string) and the storage position information are passed from the index type determination unit 153c. Thus, a gram sequence (a set of N-grams) is created. The gram dividing unit 155 passes the created gram string and storage location information to the N-gram index updating unit 156. The N-gram index update unit 156 registers each gram constituting the gram string together with the storage location information, and registers the gram as an N-gram index (N-gram index record) in the N-gram index DB 22 or the N-gram index DB 22 Add the corresponding index record in That is, the N-gram index update unit 156 builds an N-gram index for the N-gram index DB 22.

  On the other hand, when the element value (character string) and the storage position information are passed from the index type determination unit 153c, the morpheme analysis unit 157 extracts words by performing morphological analysis on the value (character string) of the element. The morpheme analysis unit 157 passes the extracted word set (word set) and storage location information to the word index update unit 158. The word index update unit 158 registers each word in the word set together with the storage location information, and registers each word as a word index (word index record) in the word index DB 23 or a corresponding index in the word index DB 23. Add a record. In other words, the word index update unit 158 constructs a word index for the word index DB 23.

  As described above, in the present embodiment, when the first index type mode is designated as the index type mode of the information search system of FIG. 1 (step SS1), the value of each element extracted by the value extraction unit 152 Each time, the index type most suitable for the length is determined according to the length of the value (steps S6, S7, S9). Here, if the length of the value is equal to or less than the character string length threshold, that is, if the value length is short, a set of N-gram indexes is generated from the value (character string), and the N-gram index DB 22 is targeted. An N-gram index is constructed. On the other hand, if the value length exceeds the character string length threshold value, that is, if the value length is long, a set of word indexes is generated from the value (character string), and the word index DB 23 is The target word index is constructed.

  As described above, in the present embodiment, when the first index type mode is designated, only an element value having a short value length is set as an N-gram index construction target. Therefore, it is possible to cope with a strict search that is an advantage of the N-gram index while preventing an enormous amount of data, which is a disadvantage of the N-gram index. Further, when the first index type mode is designated, the element value having a long value length is set as a word index construction target. For this reason, it is possible to prevent the amount of data from becoming enormous as compared with the case where an element value having a long value length is set as an N-gram index construction target. Moreover, in general, element values having a long value length are often not meaningful for a strict search or a search using a character string that does not become a word. For this reason, even if an element value having a long value length is set as a word index construction target, it is possible to prevent the occurrence of problems due to the disadvantage of the word index, which is not suitable for strict search.

  On the other hand, when the second index type mode is designated (step S1), the index type determining unit 153c uses the element name, that is, the element name for each element extracted by the value extracting unit 152 as a key. By referring to the index type dictionary 26 (step S11), a predetermined index type corresponding to the element name is determined (step S12). Here, for example, for the value of an element having an element name of “date”, designation of a search condition of complete match type or size comparison type is predicted (estimated). It is known that the B-tree index is suitable for processing this complete match type or large / small comparison type search condition. When the element name “text” is included, the partial match type search condition is predicted to be specified. It is known that a full-text search index, for example, an N-gram index or a word index (that is, an index based on morphological analysis) is suitable for the processing of this partial match type search condition. Therefore, in the index type dictionary 26 of the present embodiment, the B-tree index is used as an index type that forms a pair with the “date” element name, and a full-text search index as an index type that forms a pair with the “body” element name. For example, an N-gram index is used. A word index can be used instead of the N-gram index. In addition, as in the case where the first index type mode is specified using the N-gram index and the word index as the index type paired with the element name of “text”, the value length of the corresponding element Accordingly, it is possible to adopt a configuration in which one of the N-gram index and the word index is determined as an index type to be actually applied.

  When the index type determined in step S12 is a B-tree index (step S13), the index type determination unit 153c determines a set of a corresponding element value and storage location information in the structured document DB 21 as a B-tree index. It passes to the update part 159 (step S14). The B-tree index update unit 159 receives information on the value and position of this element, and builds a B-tree index for the B-tree index DB 24 as a target. Also, the index type determination unit 153c passes the set of the corresponding element value and the information on the storage position to the morpheme analysis unit 157 if the index type determined in step S12 is a word index (step S8). If it is a gram index, it is passed to the gram dividing unit 155 (step S10).

  By the way, the result of the morphological analysis of the element value (character string) by the morpheme analysis unit 157 includes notations having two (multiple) interpretations such as “Tokyo”, “East”, and “Kyoto”. May be. In this case, the index construction unit 154 may construct an N-gram index instead of the word index in order to prevent omission of search and prevent deterioration of search accuracy. On the other hand, if the morphological analysis result includes only a notation having one interpretation, a word index using morphological analysis may be constructed as it is.

  In addition, when there are notations having two (multiple) interpretations such as “Tokyo”, “East”, and “Kyoto” described above, these notations “Tokyo”, “East”, “Kyoto” All of these may be used as a word index.

  Also, if the result of morphological analysis of the element value (character string) includes words that have the same meaning but different notation (for example, “call” and “call”), either The word index should be unified. In this case, it is only necessary to search after unifying the notation of the words to be searched during the search process.

  Next, search processing in the information search system of FIG. 1 will be described. First, it is assumed that a data search request is sent from the application 30 on the client terminal to the information search system of FIG. This search request is accepted by the access processing unit 11 in the DBMS 10. Then, the access processing unit 11 notifies the search request from the application 30 to the data search unit 16 in the search engine 13.

  The search expression processing unit 161 in the data search unit 16 analyzes the search expression specified by the notified search request, extracts a search condition (element value search condition) regarding the element value, and the character that becomes the element value search condition The column is passed to the index reference control unit 172 in the index reference unit 17. The search formula processing unit 161 also extracts search conditions other than element values, for example, structure search conditions, from the search formula.

  On the other hand, the character string length threshold value determination unit 171 in the index reference unit 17 is the same as the character string length threshold value determination unit 151 in the index management unit 15 when the first index type mode is designated as the index type mode. The procedure determines the character string length threshold value and passes the character string length threshold value to the index reference control unit 172.

  When the first index type mode is designated as the index type mode, the index reference control unit 172 selects the index type that matches the character string that is passed from the search expression processing unit 161 and serves as the element value search condition. This is determined based on the length of the character string and the character string length threshold value passed from the character string length threshold value determination unit 171. That is, the index reference control unit 172 gives the character string to the morpheme analysis unit 175 when the length of the character string serving as the element value search condition exceeds the threshold. On the other hand, if the length of the character string that is the element value search condition does not exceed the threshold value, the value length of the element that includes the character string may or may not exceed the threshold value. Therefore, the index reference control unit 172 gives the character string to both the gram dividing unit 173 and the morpheme analyzing unit 175.

  The gram dividing unit 173 generates a gram string by dividing the character string serving as the element value search condition into N-grams by the same operation as the gram dividing unit 155 at the time of updating the index, and the N-gram index searching unit To 174. The morpheme analysis unit 175 also extracts words from the character string serving as the element value search condition by the same operation as the morpheme analysis unit 157 at the time of index update, and passes the extracted word set to the word index search unit 176.

  The N-gram index search unit 174 searches the N-gram index DB 22 with each gram (vocabulary) passed from the gram dividing unit 173, and obtains the storage position in the structured document DB 21 of the document having all the gram (vocabulary). That is, the N-gram index search unit 174 selects the storage position in the structured document DB 21 from all the sets for the set of storage positions in the structured document DB 21 obtained by searching each gram (vocabulary), and adjoins the input gram string. When the relationship is inspected and the adjacency relationship is satisfied, the storage position in the structured document DB 21 of the head gram is held as a set of search results. Then, the N-gram index search unit 174 returns the obtained set of storage positions in the structured document DB 21 to the index reference control unit 172 as an N-gram index search result.

  On the other hand, the word index search unit 176 searches the word index DB 23 with each word passed from the morpheme analysis unit 175, and obtains the storage position in the structured document DB 21 of the document having all the words. That is, the word index search unit 176 returns a set of storage positions in the structured document DB 21 obtained by searching for each word to the index reference control unit 172 as a word index search result.

  Next, when the second index type mode is designated as the index type mode, the index reference control unit 172 matches the character string that matches the character string that is passed from the search expression processing unit 161 and serves as the element value search condition. Is determined according to the index type dictionary 26 by the same operation as that of the index construction control unit 153 (the index type determination unit 153c in the index update). When the B-tree index is determined as the index type, the index reference control unit 172 passes a character string serving as an element value search condition to the B-tree index search unit 177. The B-tree index search unit 177 searches the B-tree index DB 24 with the character string passed from the index reference control unit 172, and determines the magnitude relationship of the search target keys from the root node of the B-tree tree structure to the leaf nodes. The nodes are sequentially traced, and when the leaf node is reached, all the storage positions in the structured document DB 21 corresponding to the search target key included in the leaf node are obtained. The operation when the N-gram index or the word index is determined as the index type is the same as that when the first index type mode is specified.

  The index reference control unit 172 includes a plurality of index search results obtained from the N-gram index search unit 174, the word index search unit 176, and the B-tree index search unit 177 used for the search. If there is, an OR operation is performed to delete the duplication, and a set of storage positions in the structured document DB 21 is returned to the search expression processing unit 161 as a candidate set of index search results. The search expression processing unit 161 passes information on each storage position in the structured document DB 21 to the data reference unit 162 based on the candidate set returned from the index reference control unit 172. The data reference unit 162 identifies the corresponding structured document based on the information of each storage position in the structured document DB 21 delivered from the search formula processing unit 161 and returns the specified structured document to the search formula processing unit 161. . The search formula processing unit 161 targets, for each structured document returned from the data reference unit 162, whether or not it matches a search condition (structure search condition) other than the element value extracted from the search formula. Check if the element value of is correctly included. Then, the search formula processing unit 161 returns a set of structured documents matching the search formula as a result set to the application 30 via the access processing unit 11.

  In the above embodiment, several modes and an index type determination function or a character string length threshold determination function corresponding to the mode are prepared. However, a configuration in which only a specific index type determination function or a character string length threshold determination function is prepared without preparing this type of mode may be used.

  In the above embodiment, the value of each element included in the structured document stored in the structured document DB 21 is accumulated in the log file 27 by the index construction control unit 153 when the index is constructed. However, only a value of an element included in a structured document that matches a specific type of search condition, for example, a perfect match type search condition may be stored in the log file 27. In this case, the character string length threshold value is determined based on the length of the element value included in the structured document that matches the search condition of the exact match type stored in the log file 27, and the above-described implementation is performed. A character string length threshold more suitable for determining the index type than the form can be determined. Note that a structured document that matches the exact match type search condition is confirmed by the search expression processing unit 161. Therefore, the process of accumulating the element values included in the structured document in the log file 27 The search expression processing unit 161 may be performed.

  Further, the search condition applied to each element may be associated with the element, and the search formula processing unit 161 may accumulate in the log file 27, for example. In this case, the index type determination unit 153c in the index construction control unit 153 matches the element extracted by the value extraction unit 152 with the history of the search formula stored in the log file 27, that is, the past for the element. Based on the history of search conditions applied to the index type, it is possible to determine an index type suitable for the value of the element. For example, when there are most exact match type search conditions as a search condition applied to a certain element, a B-tree index suitable for processing the complete match type search condition is used as an index type to be applied to the element. It is good to decide. In addition, for an element to which a partial match type search condition is applied most, it is preferable to apply a full text search index represented by an N-gram index or a word index suitable for processing a partial match type search condition. . Thereby, search performance can be improved.

  Now, the type of index suitable for an element varies depending on the data type of the element value. Therefore, if a data type is given as part of the structure (schema) specification of a structured document, the index type suitable for processing that data type is determined according to the data type of the element value. For example, the search performance can also be improved by adopting a configuration determined by the index type determination unit 153c. Here, for example, a numeric type B-tree index may be applied to the corresponding element if it is a numeric type, and a full-text search index if it is a character string type. In the binary type, the corresponding element is preferably excluded from the index construction target.

  A plurality of different search conditions may be applied as search conditions for a specific element. Therefore, the index type determination unit 153c determines an index type suitable for each of a plurality of different search conditions, and an index of that type is constructed by the index construction unit 154 for the same element value, respectively. In some cases, when a search condition is given, the index reference control unit 172 selects an index suitable for processing the search condition. For example, when partial match type search conditions and large / small comparison type search conditions are mixed in the search conditions applied to the value of the same element, size comparison should be performed using the full-text search index alone. It is not possible to perform a partial match search with the B-tree index. In such a case, both a full-text search index and a B-tree index are built for the above elements, and a full-text search index is used for partial match search, and a B-tree index is used for large and small comparisons. If each is selected and used, both search conditions can be processed at high speed.

  Note that the present invention is not limited to the above-described embodiment as it is, and can be embodied by modifying the constituent elements without departing from the scope of the invention in the implementation stage. Further, various inventions can be formed by appropriately combining a plurality of constituent elements disclosed in the embodiment. For example, some components may be deleted from all the components shown in the embodiment.

1 is a block diagram showing a configuration of an information search system according to an embodiment of the present invention. The block diagram which shows the structure of the structured document management part 12 in FIG. 1 linked | related with each DB21-24 etc. FIG. The block diagram which shows the structure of the search engine 13 in FIG. 1 in association with each DB21-24 etc. FIG. The block diagram which shows the structure of the index construction control part 153 in FIG. The flowchart which shows the procedure of the index update process in the information search system of FIG.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 10 ... Database management system (DBMS, structured document management system), 12 ... Structured document management part, 13 ... Search engine, 14 ... Data update part, 15 ... Index management part, 16 ... Data search part, 17 ... Index reference , 21 ... structured document database (structured document storage means), 22 ... N-gram index database (index storage means), 23 ... word index database (index storage means), 24 ... B-tree index database (index storage means) 25 ... Setting file (setting means), 26 ... Index type dictionary (index type storage means), 27 ... Log file, 151, 171 ... Character string length threshold value determination unit, 152 ... Value extraction unit, 153 ... Index construction control unit , 153a: Value length calculation unit, 153b ... Comparison unit, 153c ... Index type determination unit, 154 ... Index construction unit, 161 ... Search formula processing unit, 172 ... Index Irradiation control unit (index selection means).

Claims (1)

In a structured document management system that builds an index of a structured document and stores it in the index storage means in order to speed up retrieval of the structured document stored in the structured document storage means,
A search expression processing means for analyzing a search expression given from the outside, extracting a search condition, and acquiring a set of search result candidates that match the search condition;
Schema designating means for designating a structure of the structured document stored in the structured document storage means, including a data type of an element value included in the structured document;
Among the elements included in the structured document to be indexed, the index type for determining the index type based on the data type specified by the schema specifying unit for the element specified by the schema specifying unit A determination means;
An index construction unit configured to construct an index of the determined index type corresponding to the element based on the index type determined for each element by the index type determination unit and store the index in the index storage unit. A structured document management system characterized by:

Images