JP2000348038A - Device and method for storing data for semi-structured database - Google Patents

Abstract

PROBLEM TO BE SOLVED: To efficiently retrieve large-scale data in a semi-structured database. SOLUTION: A designating means 1 designates the structure of a partial tree which can be a retrieving object by using the label, etc., of an edge in tree structure data. An extraction means 2 extracts information of at least one partial tree suited to the designated structure and a storing means 3 gathers information of a node, edge, etc., included in the extracted tree by each partial tree to store in a physical storing area.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to a data storage device and a method for constructing a semi-structured database.

[0002]

2. Description of the Related Art In a conventional relational database, object-oriented database, or the like, a schema defining a data structure and a group of data according to the schema are managed in advance.

For example, when creating a book catalog or the like using a relational database, attributes such as an author, a book name, and a publisher are defined when a book schema is created. However, since the number of authors cannot be determined in advance, the schema usually defines an upper limit for the number of authors, and the schema defines repetitions up to the upper limit. For this reason, if a book written by more authors than the upper limit appears, that information cannot be stored.

On the other hand, in an object-oriented database, an arbitrary number of repetitions can be described by a schema, so that such a problem can be solved. However, when it is necessary to store an attribute that is completely different from the attribute assumed in advance, it cannot be handled. For example, if the attribute of the organization to which the author belongs is not defined in the collection catalog schema, the name of the research institution of the research report cannot be stored.

As described above, fields in which a relational database or an object-oriented database can be used are as follows.
This is an area where the business can be analyzed in advance and the structure of the data to be handled can be limited. Therefore, these databases are not suitable for the purpose of collecting and storing data of a new structure from the outside. For example, in a schema of a collection catalog assuming a novel or the like, when a document such as a research report jumps in, it becomes difficult to store attributes such as the number of authors and the organization to which the author belongs.

On the other hand, semi-structured
2.) In a database, unlike a relational database or an object-oriented database, there is no schema for defining a data structure, and structural information is managed together in data. For this reason, the semi-structure database can collect and store unknown data having a new structure that is not assumed in advance from a communication network or an external source.

With the development of networks in recent years, a system for collecting and managing data of a new structure from outside in various business fields is required. In these areas, it is expected that semi-structured databases will be used to store new structured data.

More recently, semi-structured databases, in particular,
Attention has been drawn to its use as a database of structured documents described in extensible markup language (XML) or the like. XML is a data structure used in electronic commerce and the like, and its demand is rapidly increasing. A database that handles the XML and an infrastructure centered on the database are desired. A query language for XML data that is presumed to be stored in a semi-structured database is already W3C (The World Wide Web Constraint).
ortium).

Therefore, a data model and a storage format in the semi-structured database will be described. Semistructured databases do not have schemas, but have structural information in the data. Some systems have been proposed as semi-structured databases, but their data models are generally as shown in FIG.

The data model of FIG. 37 is represented by a tree structure composed of nodes and edges (links), and represents data on a plurality of papers. A label representing the attribute of the data is attached to the edge, and a value is stored in the terminal node. Labels “paper”, “id”, “titl
e "," author "," name "," post "
, “page”, “firstpage”, and “lastpage” are a dissertation and a dissertation I, respectively.
D (identifier), title, author, author name, author's organization, page information, first page, and last page.

In order to express such a tree structure model, in a semi-structure database, edge information and node information are separately stored in a storage device. The edge is stored in a table format including the node IDs of the nodes at both ends thereof and the label of the edge, and the node is stored in a table format including records in which the node IDs and the values of the nodes are stored. With such a data model and storage format, it is possible to freely add externally acquired data of a new structure in the semi-structured database.

[0012] In a semi-structured database, data retrieval is generally speeded up using the following indexes. (1) Value index Using a value index for obtaining a node ID from a value, a node ID that matches the value can be searched from the value or range of the search condition. (2) Structure (Path) Index The node ID can be searched from the path of the search condition using the structure index for obtaining the node ID from the path. The path is information that specifies the branch of the tree structure model.
Usually represented using one or more edge labels. In the case of the data model of FIG. 37, for example, “/ paper
The correspondence between the path "/ author / name" and the two node IDs "3" and "6" is registered in the structure index, and the node IDs "3" and "6" can be searched from this path. The edge adjacent to the node can be obtained from the node ID using the edge index for the node ID of the node at both ends of the edge, thereby speeding up the process of traversing the edge.

[0013]

However, when large-scale data is stored in the above-described conventional semi-structured database for data search, sufficient performance may not be obtained for the following reasons. (1) Data included in a subtree to be searched is distributed to physical storage areas.

In each of the node and edge tables, there is no particular limitation on the order of records.
Nodes and edges belonging to a single subtree such as a subtree below “per” may be distributed and stored in the physical storage area. Therefore, when searching for this subtree, It takes an enormous amount of time to access the file, which is disadvantageous compared to a relational database that can store a search target as one record. (2) A traversal in a subtree to be searched is required.

For example, in the case of a search such as “paper” with the author name “Yasuhiko Kinmasa” and the title “xxxx”, the tree structure model requires processing for tracing edges, ie, traversal in a subtree. Even if the speed of the traverse is increased by using the edge index, it is disadvantageous compared to a relational database that can store a search target as one record. (3) The structure index is not always effective.

The structure index is a technique effective when the data structure (path) is various but the number of data having the same structure is small. On the other hand, when there is a large amount of data having the same structure, it is difficult to narrow down and the effect is small.

It is an object of the present invention to provide a data storage device and a method for efficiently searching large-scale data in a semi-structured database.

[0018]

FIG. 1 is a diagram showing the principle of a data storage device according to the present invention. The data storage device of FIG. 1 includes a designation unit 1, an extraction unit 2, and a storage unit 3.

The specifying means 1 specifies a partial tree structure which may be a search target in the tree structure data, and the extracting means 2 extracts a partial tree conforming to the specified structure from the tree structure data. Extract. Then, the storage unit 3 collectively stores the information of the extracted partial trees.

The structure of a subtree that may be a search target is information that defines a subtree that is expected to be a data search target in tree structure data. For example, by inputting a specific label as specification information, the specifying unit 1 can specify a subtree connected below an edge having the label. Such designation information,
For example, the input is made by the user, or the system automatically generates and inputs.

The extracting means 2 scans the tree structure data,
The storage unit 3 extracts information of one or more subtrees conforming to the specified structure, and collectively stores information on nodes, edges, and the like included in the extracted subtree. At this time, the storage unit 3 collectively stores, for example, information of one partial tree in a physically adjacent continuous area. Therefore, when a plurality of subtrees are extracted, information is grouped and stored for each subtree.

According to such a data storage device, information on subtrees having a specified structure is stored together without being dispersed, so that when a data search is performed on the subtree as a search target, Information can be accessed efficiently. Therefore, even in a large-scale semi-structured database, data retrieval is made more efficient.

The specifying means 1 individually specifies one or more paths in a subtree which may be a search target,
It is also possible to specify a structure consisting of those paths. In this case, the extracting means 2 extracts the node at the end of the designated path from the tree structure data,
Collectively stores information on the extracted nodes.

According to such a data storage device, information stored on one or more paths is stored collectively without being dispersed, so that when such data is searched for, a data search is performed. , And necessary information can be efficiently accessed.

For example, the designation means 1 in FIG. 1 corresponds to the input device 23 in FIG. 35 described later, and the extraction means 2 in FIG. 1 corresponds to the CPU (central processing unit) 21 and the memory 22 in FIG. The storage unit 3 in FIG. 1 is, for example, the memory 22, the external storage device 25, or the portable recording medium 2 in FIG.
9 or the database 30 of FIG. 36 described later.

[0026]

Embodiments of the present invention will be described below in detail with reference to the drawings. In the data storage device of the present embodiment, a plurality of similar structures existing in the semi-structured database are designated to adopt a storage format that makes data access more efficient. As a result, an effect equivalent to the optimization based on the schema in the relational database or the object-oriented database can be obtained. In addition, by using an existing relational database or object-oriented database as an auxiliary, data retrieval in a semi-structured database is speeded up.

First, it is considered that the retrieval is speeded up by clustering a partial tree of the tree structure model, dividing the tree structure model for each node, and storing the divided nodes in a database. When storing data, a subtree that is expected to be a search target is specified in advance, and information in the subtree is collectively stored in a physically adjacent storage area (neighboring area), thereby performing a search. Can be speeded up.

For example, in the tree structure model of FIG.
Specify the subtree under “paper” as a search target,
When the database is updated, the information in the subtree is arranged in a continuous area as much as possible in each node and edge table. Thereby, the node table as shown in FIG.
Is obtained. In the case of a relational database, the node table and the edge table are implemented as different relations.

In FIG. 2, "ID" represents a node ID, and "VALUE" represents a value of the node. Here, nodes “1”, “2”, “3”, “4”, “6”,
For “7”, “8”, and “9”, the values “12”, “Research on XX”, “Yasuhiko Kanasa”, “Fujitsu Laboratories”, “Kazuki Kubota”, “Fujitsu Research” Place ",
“58” and “63” are stored.

In FIG. 3, "LABEL" indicates a label of an edge, and "ID" indicates a node ID of a node at both ends of the edge. Here, labels of 12 edges in the specified subtree and node IDs of nodes at both ends of each edge are stored. By using these tables, various attribute data belonging to one “paper” can be read from the storage device to the main storage by one access.

As described above, by storing nodes and edges of a partial tree which may be a search target in a physically neighboring area of the recording medium, the frequency of access to the recording medium is reduced, and the search speed is reduced. Is achieved.

Next, consider the case where the subtree is converted into a record to speed up the retrieval. By collecting information of a part of the subtree as one record, the traversal in the subtree can be reduced, and the search can be further speeded up. The recording of the partial tree is performed as follows.

First, a record is generated by applying a selection rule to a subtree. The selection rule is specification information for individually enumerating and specifying one or more paths in the subtree, and describes the path group in the subtree in an extensible manner. This selection rule is provided by the user or an external system, or is automatically generated by the system.

For example, the subtree T1 in FIG.
1, "n2", "n3", "n4", "n5", and "n6", and edges "e1", "e2", "e3",
It consists of “e4”, “e5”, and “e6”.

The path belonging to the subtree T1 is represented by {e1 / e
2, e1 / e2, e1 / e2, e3, e4 / e5, e
It is six of 6｝. Of these, the nodes “n1”, “n2”, “n3”, “n4”, and “n6” at the end of the five paths have values “abc”, “xyz”,
“Ijk”, “100”, and “300” are stored.

Here, the paths "e1 / e2" are set in the order of appearance by 2
And selecting the paths “e3” and “e6” one by one in the order of appearance, and selecting those four paths into one record, a selection rule {e1 / e2, e1 /
e2, e3, e6} are applied. In this case, the path “e4
/ E5 "is not selected.

Record r generated by this selection rule
1 is the four fields f corresponding to the selected path
1, f2, f3, and f4. The values “abc” and “xy” are stored in these fields, respectively.
"z", "100", and "300" are stored in each field as described above, and the value of the node specified by the corresponding path is stored in each field.

Further, the subtree T2 in FIG.
7, "n8", "n9", "n10", and "n1"
1 "and edges" e1 "," e2 "," e3 "," e
4 ”,“ e5 ”,“ e6 ”, and“ e7. ”The paths belonging to the subtree T2 are {e1 / e2, e
3, e4 / e5, e6, e7}. Of these, the nodes “n7”, “n8”, and “n10” at the terminal of the three paths have values “lmn”, “40”, respectively.
"0" and "500" are stored.

In the subtree T2, the above selection rule {e1 / e
2, e1 / e2, e3, e6}, a record r2 is generated. In this case, the fields f1, f2,
f3 and f4 have values “lmn” and “N”, respectively.
“NULL” in the field f2 indicates that a path corresponding to the second path “e1 / e2” of the selection rule does not exist in the subtree T2. ing.

Next, a pointer to the generated record is added to the subtree. At this time, a new edge “er” is added to the root of the subtree, a new node is generated ahead of the edge “er”, and a pointer to a record is stored in that node. As a result, the root of the subtree and the record are connected via the edge “er”. Then, edges and nodes included in the path group collected in the record are deleted from the subtree, and a pointer to the newly generated node is stored in the record.

When such operations are performed on the data shown in FIGS. 4 and 5, a data representation as shown in FIG. 6 is obtained. In FIG. 6, the data representation is optimized by the modified partial trees T1 'and T2', the selection rule {e1 / e2, e1 / e2, e3, e6}, and the records r1 and r2.

The root of the subtree T1 'has an edge "er"
, A node "n12" is added, and a pointer "p-r1" to the record r1 is stored in this node.
The field f0 of the record r1 contains the node “n”.
12 "is stored.

The root of the subtree T2 'has an edge "er"
, A node "n13" is added, and a pointer "pr-2" to the record r2 is stored in this node.
In the field f0 of the record r2, the node "n"
13 "is stored.

FIG. 7 shows a data representation of the whole tree obtained by joining the subtrees thus optimized. In general, various subtrees can be recorded by defining the structure of the subtree using a plurality of selection rules. Here, two selection rules S1 = ｛s1, s2,
s3}, S2 = {s4, s5, s6, s7},
Record groups R1 and R respectively corresponding to different subtree groups
2 has been generated.

Pointer p stored in the modified whole tree
-R1, p-r2,. . . , P-rn are records r1, r2,. . . , Rn, and pointers pr (n + 1), pr (n +
2),. . . , P-rm are respectively the record group R2
Records r (n + 1), r (n + 2),. . . , Rm
Pointing to.

In terms of analogy with a relational database, selection rules correspond to schemas, records correspond to relations, and records correspond to tuples. Further, the point that a pointer to a record exists in the corrected whole tree is different from the relational database.

When the nodes and edges of such a modified whole tree are stored in a table format, a database as shown in FIG. 8 is obtained. In FIG. 8, the node table and the edge table correspond to the information of the corrected whole tree, and correspond to the selection rules S1 and S2 and the record groups R1 and R2.
One record table corresponds to information deleted from the entire tree.

In the case of a relational database, these tables are implemented as different relations, and the selection rules are stored as path group designation information in the subtree. Even for the subtrees that have been recorded in this way, it is possible to speed up the search by using a record index or the like.

Next, a procedure for retrieving data stored in this manner will be described. For example, in a tree structure model as shown in FIG. 37, the selection rule is set to {/ paper /
id /, / paper / title /, / paper /
Record the subtree as author / name /｝.

As a result, information on the article ID, title, and first author of each article is deleted from the entire tree.
These values are the fields f1,
stored in f2 and f3. Organization of the first author,
The names of authors, affiliations, page information, etc. after the second author remain in the entire tree.

In the generated optimization database, the title is “xxxx” and the author is “yyy”.
The procedure when the data retrieval device retrieves the article "y" is as follows:
It looks like this: [P1] First, as shown in FIG.
In the record group of the subtree, the given search condition “f2: xxxx AND f3: yy” is sequentially used using the indexes of f2 (title) and f3 (name).
yy ”is retrieved, and the obtained record is stored as the result A1. Also, the search is performed using only the search condition“ f2: xxxx ”for the title, and the obtained record is used as the intermediate result B1. [P2] Next, as shown in Fig. 10, the entire tree is searched for the author names of the second and subsequent authors using the path "/ paper / author / name /", and the search condition "yyyy" for the author name is obtained. Then, an edge “er” included in the subtree is obtained by tracing an edge from the node, and a node “1” ahead of the edge is obtained.
4 ". The pointer" p-ri "to the record stored in the record No. 4 is taken out. By repeating such processing, the obtained set of pointers {p-ri, p-rj, ...} is set as the intermediate result B2. [P3] Next, the intermediate result B1 and the intermediate result B2 are joined, a record indicated by each pointer of the intermediate result B2 is extracted from the intermediate result B1, and the obtained record is stored as the result A2. P4] The result A1 corresponds to the record of the dissertation whose title is “xxxx” and whose first author is “yyyy”.
Reference numeral 2 corresponds to a record of a dissertation whose title is "xxxx" and whose second and subsequent author names are "yyyy". Therefore,
A union (union) of the result A1 and the result A2 is obtained and set as a search result.

By using the article ID in the field f1 of these records, information such as the text of the article and attached drawings can be obtained. When the attribute data remaining in the entire tree such as page information is obtained, the partial tree left in the entire tree may be traced using the pointer of the field f0 of the record.

The feature of this search method lies in the search for the record group of [P1]. Traversal in the subtree can be suppressed by using the recorded subtree.
Therefore, if the record conversion rate of the search target is increased, the search speed can be made closer to the relational database. If the processes of [P1] and [P2] are performed in parallel, the search speed is further improved.

Next, the processing of the above-described clustering of subtrees and selective recording will be described in more detail. First, in the clustering of the subtree in FIG.
Consider a case where the node table of FIG. 2 and the edge table of FIG. 3 are stored as tables of a relational database. In this case, to access the database, S
An interface such as QL (structured query language) is used. Here, in order to increase the speed, the edge table of FIG. 3 is divided into three tables shown in FIGS. 11, 12 and 13 and stored, and the path table of FIG. 14 is further added. Each of these tables is implemented as a different relation in a relational database.

The label table shown in FIG.
(LABELID) and a label (LABEL) are stored, and the parent node table of FIG.
(ID), the node ID of the parent node of the node (PAR
ENT) and a label ID (LABELID) of an edge label connecting these nodes is stored.

The child node table shown in FIG. 13 includes a node ID (ID) and a node ID of a child node of the node.
(CHILD) and a label ID (LABELID) of an edge label connecting those nodes are stored. The path table in FIG. 14 shows the node ID (ID) and the path from the root node to the node (PATH). Store the correspondence of

The node table can be used as a value index, the parent node table and the child node table can be used as edge indexes, and the path table can be used as a structure index.

The data types and lengths of the attribute data used in these tables are as shown in FIG. 15, for example. In FIG. 15, the data type “NUMBER” represents a number, and the data type “VARCHAR2” represents a variable-length character string. Further, the node table of FIG. 2 and the label table of FIG. 11 are respectively depth-first traversa.
l) Clustered by algorithm.

When clustering is performed without explicitly specifying a subtree to be searched, the subtree is hierarchically clustered by specifying a clustering algorithm for the entire tree. Therefore, the same clustering is performed on the subtrees of other papers not shown in FIG. 37, and the result is added to each table. According to such clustering, information on nodes and edges belonging to one subtree is collectively stored in a neighboring area in each hierarchy of the tree structure model, and the search is speeded up.

FIG. 16 is a flowchart of data storage processing based on such clustering. First, the data storage device sets the root node as the current node (step ST1), and stores the current node in the database (step ST2).

Next, it is checked whether or not the current node is a terminal node (step ST3). The terminating node is shown in FIG.
It means a node having no edge below it, such as node “3” of No. 7. If the current node is not the terminal node, one of the edges that have not been traversed is selected and set as the current edge (step ST
7). And traverse the current edge downward,
Set the child node as the current node (step ST8)
The processing after step ST2 is repeated. Step ST2
Now, the current node and the current edge are stored in the database.

In step ST3, if the current node is the terminal node, the current edge is traversed upward and the parent node is set as the current node (step ST3).
4). And for all edges of the current node,
It is checked whether or not the downward traverse has been completed (step ST5), and if there is an edge that has not been traversed, the processing from step ST2 is repeated.

In step ST5, if all edges have been traversed downward, it is checked whether the current node is the root node (step ST6). If the current node is not the root node, the process from step ST4 is repeated, and if the current node is the root node, the process ends.

FIG. 17 is a flowchart of the storing process of the current node and the current edge in step ST2 of FIG. The data storage device first adds the current node to the node table (step ST11). Next, if an edge is currently selected, it is checked whether the label is a new label (step ST12). here,
Labels that do not exist in the label table are considered as new labels.

If the label of the current edge is not a new label, information on the current node is added to the parent node table (step ST13), and the path of the current node is added to the path table (step ST14). Return to processing. In step ST12, if the label of the current edge is a new label, the label is added to the label table (step ST15), and the processes after step ST13 are performed.

FIG. 18 is a flowchart showing the operation of step ST8 in FIG.
5 is a flowchart of a downward traverse process in FIG. First, the data storage device adds information on the current edge to the child node table (step ST21).
Then, the child node ahead of the current edge is set as the current node (step ST22), and the process returns to the processing in FIG.

By such data storage processing, the tree structure model of the semi-structure database is stored in the relational database. The same applies when an edge table as shown in FIG. 3 is used instead of the label table, the parent node table, and the child node table. When an object-oriented database is used instead of a relational database, objects corresponding to records in each table may be generated and stored in the object-oriented database.

Further, a node table, a label table,
Instead of storing the parent node table, the child node table, and the path table in the relational database, they can be directly implemented on the page management mechanism. A page corresponds to information stored in a predetermined fixed-length storage area (block). When implemented on a page management mechanism, pages corresponding to each of the five tables are prepared.

The data storing process in this case is basically the same as that of FIG. 16, but the storing process of the current node and the current edge in step ST2 is as shown in FIG. The data storage device first adds the current node to the page of the node (step ST31). Check whether the label of the current edge is a new label (step ST
32).

If the label of the current edge is not a new label, information about the current node is added to the page of the parent node (step ST33), and the path of the current node is added to the page of the path (step ST34). It returns to the process of step 16. In step ST32, if the label of the current edge is a new label, the label is added to the page of the label (step ST35), and the processing after step ST33 is performed.

Steps ST31, ST33, ST34,
If the storage area is insufficient in ST35 and ST35,
The data storage device secures a new page. Also, every time information is added, the index for access is updated.

The downward traverse process in step ST8 of FIG. 16 is as shown in FIG. First, the data storage device adds information on the current edge to the page of the child node and updates the index (step ST41). At this time, if the storage area is insufficient, a new page is reserved. Then, the child node ahead of the current edge is set as the current node (step ST4).
2) Return to the process of FIG.

Incidentally, some relational databases have a function of clustering a plurality of tables with a common attribute. Using this clustering function, the node table, parent node table, and child node table can be clustered by node ID. The data storage process in this case is described in FIGS.
8 is the same as the processing in FIG. Such clustering can further reduce storage device access.

When clustering based on the common attribute is realized on the page management mechanism, a common page corresponding to the node table, the parent node table, and the child node table, and a page corresponding to the label table and the path table, respectively. Is prepared.

The data storing process in this case is basically the same as that of FIG. 16, but the storing process of the current node and the current edge in step ST2 is as shown in FIG. The processing in steps ST51 to ST55 in FIG. 21 is basically the same as the processing in steps ST31 to ST35 in FIG. However, steps ST51, ST53, and ST
At 54, a node table, a parent node table,
And information is added to a common page corresponding to the child node table.

The downward traversing process in step ST8 in FIG. 16 is as shown in FIG. The processing in steps ST61 and ST62 in FIG. 22 is basically the same as the processing in steps ST41 and ST42 in FIG. However, in step ST61, the node table,
A common page corresponding to the parent node table and the child node table is newly created, and information is added to the page.

Next, consider a case where selective recording of a subtree is performed using a selection rule that describes a path group in the subtree. For example, when a tree-structured data model as shown in FIG. 23 is given, a subtree under “paper” is specified as a search target, and a selection rule is applied to the subtree,
Optimize the whole tree.

In FIG. 23, the labels “pos.”,
“First.” And “last.” Are “position”, “firstpage”,
And "lastpage".
As a selection rule, s = ｓid, title, a
uthor / name, author / position
n, author / name, author / posi
｝ is used.

At this time, the entire tree and the record group optimized by the selection rule s are as shown in FIG. Here, two records r1 and r2 corresponding to the subtrees of the two papers are generated according to the selection rule s and stored in the record table. In the whole tree, the node of the edge having the label “s” stores the ID of the generated record as a pointer to the record. Node “29” is the ID of record r1
“1” is stored, and the node “30” stores the I
D “2” is stored.

In the record field, the first field fid of the records r1 and r2 has a record ID.
Is stored, and the node ID of the corresponding node in the entire tree is stored as a pointer in the second field f0. The third and subsequent fields f1 to f6 correspond to the selection rule s
, Respectively, and stores the value of the terminal node of the corresponding path.

For example, the field f1 of the record r1,
f2, f3, f4, f5, and f6 respectively
The values “id1”, “xxxx”, “name1”, “po”
"s1", "name2", and "pos2" are stored.

When the data structure of FIG. 24 is stored in the relational database, five tables as shown in FIGS. 25 to 29 are generated corresponding to the entire tree. FIG. 25 shows a node table, FIG. 26 shows a label table, FIG. 27 shows a parent node table, and FIG.
8 shows a child node table, and FIG. 29 shows a path table. A total of six tables are stored by combining these five tables and the record table of FIG.

As described above, even when a record is formed by applying a selection rule to a subtree to be searched, clustering can be performed using an appropriate algorithm such as a depth-first algorithm. The data storage process in this case is
Basically, it is the same as FIG. 16, but the process of storing the current node and the current edge in step ST2 is as shown in FIG.

The data storage device first checks whether the current node satisfies the selection rule (step ST7).
1). If the current node does not satisfy the selection rule, the current node is added to the node table (step ST7).
2). Next, if an edge is currently selected, it is checked whether the label is a new label (step ST).
73).

If the label of the current edge is not a new label, the current node is added to the parent node table, and the path of the current node is added to the path table (step ST7).
4) It is checked whether or not the current edge corresponds to the head of the specified subtree (step ST75). And
If the current edge does not correspond to the head of the subtree, the process returns to the processing in FIG.

If the current node satisfies the selection rule in step ST71, the value of the current node is stored in the corresponding field of the record (step ST76).
The processing after step ST73 is performed.

In step ST73, if the label of the current edge is a new label, the label is added to the label table (step ST77), and the processing after step ST74 is performed.

In step ST75, if the current edge corresponds to the head of the subtree, a record for storing the information of the subtree is generated, and “NU” is stored in each field.
LL ”is stored and the record is initialized (step S
T78). Next, an edge between the current node and the record is generated, and it is checked whether or not the label of the edge is a new label (step ST79).

If the label of the generated edge is not a new label, the edge is added to the parent node table and the child node table (step ST80), and the process returns to FIG. If the label of the generated edge is a new label, the label of the edge is added to the label table (step ST81), and the processing from step ST80 is performed.

For example, in FIG. 23, if the current node is node “12” and the current edge is “paper”, the current edge corresponds to the head of the specified subtree. Therefore, as shown in FIG. 24, a record r1 corresponding to this subtree is generated.
78). Further, an edge "s" between the node "12" and the record r1 is generated, and information on this edge is added to the parent node table of FIG. 27 and the child node table of FIG. 28 (step ST80).

In FIG. 24, two edges having the label "s" are generated. When the first edge "s" is generated, the label "s" is added to the label table (step ST81). When the second edge “s” is generated, no label is added.

In FIG. 23, when the current node is the node “1” and the current edge is “id”, the node “1” is the first path “i” included in the selection rule s.
24, the selection rule s is satisfied. Therefore, the value of this node "id1" is
Is stored in the field f1 of the record r1 (step ST76). Nodes “2”, “3”, “4”,
Similarly, for the values of “6” and “7”, the record r
1 is stored.

The downward traversal process in step ST8 of FIG. 16 is the same as that of FIG. 18, except that if the current edge is an edge to a record, the node storing the record ID of that record becomes the current node. Set.

For example, in FIG. 24, when the current edge is the edge “s” between the node “12” and the node “29”, the node “29” becomes a new current node. At this time, in step ST72 of FIG. 30, ID “1” of record r1 corresponding to node “29” is
Is stored in the node table. Similarly, when the current edge is the edge “s” between the nodes “27” and “30”, the ID “2” of the record r2 is stored in the node table.

Instead of storing these tables in a relational database, it is also possible to implement them directly on a page management mechanism. The data storage process in this case is basically the same as that in FIG.
The process of storing the current node and the current edge at T2 is as shown in FIG.

The data storage device first checks whether the current node satisfies the selection rule (step ST9).
1). If the current node does not satisfy the selection rule, the current node is added to the page of the node (step ST9).
2). Next, if an edge is currently selected, it is checked whether the label is a new label (step ST).
93).

If the label of the current edge is not a new label, the current node is added to the page of the parent node, and the path of the current node is added to the page of the path (step ST9).
4) It is checked whether or not the current edge corresponds to the head of the specified subtree (step ST95). And
If the current edge does not correspond to the head of the subtree, the process returns to the processing in FIG.

If the current node satisfies the selection rule in step ST91, the value of the current node is stored in the corresponding field of the record (step ST96).
The processing after step ST93 is performed.

In step ST93, if the label of the current edge is a new label, the label is added to the label page (step ST97), and the processing after step ST94 is performed.

If the current edge corresponds to the head of the subtree in step ST95, a record for storing the information of the subtree is generated, and the record is initialized (step ST98). Next, an edge between the current node and the record is generated, and it is checked whether or not the label of the edge is a new label (step ST99).

If the label of the generated edge is not a new label, the edge is added to the page of the parent node and the page of the child node (step ST100), and the process returns to FIG. If the generated edge label is a new label, the edge label is added to the label page (step ST101), and the processes from step ST100 are performed.

Steps ST92, ST94, ST97,
If the storage area is insufficient in ST100 and ST101, the data storage device secures a new page. Also, every time information is added, the index for access is updated.

The downward traversing process in step ST8 of FIG. 16 is the same as that of FIG. 20, but if the current edge is an edge to a record, the node storing the record ID of the record is set to the current node. Set.

As described above, in the relational database, the node table, the parent node table, and the child node table may be clustered by the node ID by using a function of clustering a plurality of tables with a common attribute. Further, it is also possible to realize clustering based on a common attribute on a page management mechanism.

Next, the data storage method of this embodiment is described as X
An example applied to a structured document described in ML will be described. FIG. 32 shows an example of data of an XML document. In FIG. 32, for example, the outermost tag <pap
er> and </ paper>, information on one paper is described. Also, the tag <id inside
> And </ id> describe the ID of the paper,
The title of the paper is described between the tags <title> and </ title>. Generally, since many articles are registered in the database, similar XML data is created for each article.

As described above, in the XML data, the inclusion relation of a plurality of tags represents a hierarchical data structure. If the data between two corresponding tags is regarded as a hierarchical subtree, the XML data is It can be replaced with tree structure data. For example, if the XML data of FIG. 32 is represented by a tree structure, the data shown in FIG. 37 is obtained. Here, the tag name is used as the label of the edge, and the root node “13” is also connected to a partial tree of a paper other than the paper shown in FIG.

As described above, by regarding the XML data as tree-structured data, it is possible to specify the structure of a subtree that may be a search target and to specify a path group in the subtree. , XML data can be stored in a relational database or stored on a page. The storage processing and the clustering method of the tree structure data in FIG. 37 are as described above.

When the XML data of FIG. 32 is stored in a relational database in a table format as shown in FIGS. 2, 11 to 14, access to the table is performed using SQL or the like. For example, an SQL sentence for making an inquiry of “select the title of a paper whose author name is“ ○ △ ◇ ☆ ”” is as shown in FIG.

Further, when the XML data is selectively recorded, the data storage device interactively generates a selection rule. At this time, the document type definition (document type defini
, DTD) and XML data, and a dialog screen as shown in FIG. 34 is displayed on the display. The document type definition corresponds to a schema that defines the tag structure of the XML document, and by analyzing this, a path in the tree structure data can be extracted.

Referring to FIG. 34, the user
When the name of the selection rule is input to the box and an appropriate edge label is input to the box 12, a subtree below the edge having the label is designated as a record target. Then, all the paths included in the subtree are automatically displayed in the box 13.

Next, when the user selects a desired path from the displayed paths, the selected path is registered as a selection rule. By repeating such processing interactively, a plurality of selection rules can be generated. Then, as illustrated in FIG. 7, the data storage device records each of the generated selection rules to generate a record table.

Further, the data storage device can store any SGML (standard generalized markup) in addition to the XML data.
language) can be stored in a similar manner. For example, HTML (hypertext ma
Similarly, in the case of rkup language) data, the tag structure is replaced with a tree structure.

Incidentally, the data storage device of this embodiment is an information processing device (computer) as shown in FIG.
Can be used. 35 includes a CPU (central processing unit) 21, a memory 22, an input device 23, an output device 24, an external storage device 25, a medium drive device 26, and a network connection device 27. Connected to each other.

The memory 22 is, for example, a ROM (read onl
y memory), RAM (random access memory), etc., and stores programs and data used for processing.
The CPU 21 performs necessary processing by executing a program using the memory 22.

The input device 23 is, for example, a keyboard, a pointing device, a touch panel or the like, and is used for inputting an instruction or information from a user. Output device 24
Is, for example, a display, a printer, a speaker, and the like, and is used for outputting a message or a processing result to a user.

The external storage device 25 is, for example, a magnetic disk device, an optical disk device, a magneto-optical disk (magneto-op).
tical disk) device, and is used as a database for storing the various tables described above. Further, the information processing apparatus can store the above-described program and data in the external storage device 25, and can load and use them in the memory 22 as needed.

The medium driving device 26 drives the portable recording medium 29 and accesses the recorded contents. Portable recording medium 2
9 is a memory card, floppy disk, CD
An arbitrary computer-readable recording medium such as a ROM (compact disk read only memory), an optical disk, and a magneto-optical disk is used. The user stores the above-described program and data in the portable recording medium 29,
If necessary, they can be loaded into the memory 22 and used.

The network connection device 27 communicates with an external device via an arbitrary network (line) and performs data conversion accompanying the communication. The information processing device can receive the above-described program and data from an external device via the network connection device 27 as needed, and can use them by loading them into the memory 22.

FIG. 36 shows a computer-readable recording medium capable of supplying a program and data to the information processing apparatus shown in FIG. The programs and data stored in the portable recording medium 29 and the external database 30 are loaded into the memory 22. And the CPU 21
Executes the program using the data and performs necessary processing.

[0120]

According to the present invention, when a data search is performed on a partial tree of tree structure data in a semi-structured database or the like, the data of the partial tree can be read out collectively, and the search can be performed. Speed up. Further, by converting a part of the data of the subtree into a record, the search is further speeded up.

[Brief description of the drawings]

FIG. 1 is a principle diagram of a data storage device of the present invention.

FIG. 2 is a diagram showing a first node table.

FIG. 3 is a diagram showing an edge table.

FIG. 4 is a diagram showing recording of a first partial tree.

FIG. 5 is a diagram showing recording of a second partial tree.

FIG. 6 is a diagram showing an optimized subtree.

FIG. 7 is a diagram showing a first optimized whole tree;

FIG. 8 is a diagram illustrating a storage format of an entire tree.

FIG. 9 is a diagram showing a first data search.

FIG. 10 is a diagram showing a second data search.

FIG. 11 is a diagram showing a first label table.

FIG. 12 is a diagram showing a first parent node table.

FIG. 13 is a diagram showing a first child node table.

FIG. 14 is a diagram showing a first path table.

FIG. 15 is a diagram showing the data type and length of each attribute.

FIG. 16 is a flowchart of a data storage process.

FIG. 17 is a flowchart of a first node / edge storage process.

FIG. 18 is a flowchart of a first downward traverse process.

FIG. 19 is a flowchart of a second node / edge storage process.

FIG. 20 is a flowchart of a second downward traverse process.

FIG. 21 is a flowchart of a third node / edge storing process.

FIG. 22 is a flowchart of a third downward traverse process.

FIG. 23 is a diagram showing tree structure data for two papers.

FIG. 24 is a diagram showing a second optimized whole tree.

FIG. 25 is a diagram showing a second node table.

FIG. 26 is a diagram showing a second label table.

FIG. 27 is a diagram showing a second parent node table.

FIG. 28 is a diagram showing a second child node table.

FIG. 29 is a diagram showing a second path table.

FIG. 30 is a flowchart of a fourth node / edge storage process.

FIG. 31 is a flowchart of a fifth node / edge storage process.

FIG. 32 is a diagram showing XML data.

FIG. 33 is a diagram showing an SQL sentence.

FIG. 34 is a diagram showing a dialog screen.

FIG. 35 is a configuration diagram of an information processing apparatus.

FIG. 36 is a diagram showing a recording medium.

FIG. 37 is a diagram showing tree structure data for a plurality of papers.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Designation means 2 Extraction means 3 Storage means 11, 12, 13 Box 21 CPU 22 Memory 23 Input device 24 Output device 25 External storage device 26 Medium drive device 27 Network connection device 28 Bus 29 Portable recording medium 30 Database

Continued on the front page (72) Inventor Kazumi Kubota 4-1-1, Kamidadanaka, Nakahara-ku, Kawasaki-shi, Kanagawa Prefecture Inside Fujitsu Limited (72) Inventor Yasuo Noguchi 4-1-1, Kamiodanaka, Nakahara-ku, Kawasaki-shi, Kanagawa F-term in Fujitsu Limited (Reference) 5B075 NK04 NK44 NK46 NR06 QT06 QT10 5B082 BA09 GA02

Claims (14)

[Claims] 1. A designating means for designating a subtree structure which may be a search target in tree structure data, and an extracting means for extracting a subtree conforming to a designated structure from the tree structure data. A data storage device, comprising: storage means for collectively storing information of the extracted partial trees. 2. The method according to claim 1, wherein the specifying unit individually specifies one or more paths in the subtree that may be the search target,
2. The method according to claim 1, wherein the extraction unit extracts a node at a terminal of a designated path from the tree structure data, and the storage unit collectively stores information of the extracted nodes. Data storage device. 3. A data storage device for storing tree-structured data separated into nodes and edges, wherein a designation unit that designates a structure of a subtree that may be a search target in the tree-structured data; Extraction means for extracting a subtree conforming to a specified structure from the tree structure data; node storage means for collectively storing node information of the extracted subtree; and information on edges of the extracted subtree. And an edge storage means for storing the data collectively. 4. The storage area of the node storage means is implemented as one relation of a relational database, and the storage area of the edge storage means is implemented as one or more relations of the relational database. 4. The data storage device according to claim 3, wherein: 5. The specifying means regards the document data structured by tags as the tree structure data, and regards information between two tags in the document data as a subtree and serves as the search target. 4. The data storage device according to claim 3, wherein a structure of a possible partial tree is specified. 6. A record storing means for storing, as a record, a part of information of a partial tree which may be a search target, wherein the specifying means comprises a sub-tree in the partial tree which may be a search target. One or more paths are designated as a path group, the extraction means extracts a node at the end of the specified path from the tree structure data, and the record storage means records information of the extracted nodes as a record. 4. The data storage device according to claim 3, wherein the edge storage unit omits storage of information on edges forming a path corresponding to a record in the record storage unit. 7. The data storage device according to claim 6, wherein a storage area of said record storage means is implemented as one relation of a relational database. 8. The storage area of the node storage means is implemented as one relation of a relational database. The storage area of the edge storage means is implemented as one or more relations of the relational database. 7. The data storage device according to claim 6, wherein the storage area is mounted as one relation of the relational database. 9. When the specifying unit specifies a plurality of path groups, the information processing apparatus further includes designation information storage means for storing designation information of the plurality of path groups. 7. The data storage device according to claim 6, wherein a record corresponding to the data is stored. 10. The designating means considers document data structured by tags as the tree structure data, and regards information between two tags in the document data as a subtree and serves as the search target. 7. The data storage device according to claim 6, wherein the path group in a possible partial tree is specified. 11. A data storage device comprising: extraction means for extracting a partial tree from each layer of tree structure data; and storage means for collectively storing information of the extracted partial trees. 12. A recording medium on which a program for a computer is recorded, wherein in the tree structure data, a step of specifying a structure of a subtree that may be a search target is specified. A computer-readable recording medium which stores a program for causing the computer to execute a process including a step of extracting a subtree conforming to the extracted structure, and a step of collectively storing information of the extracted subtree. 13. A recording medium for recording tree structure data for a computer, wherein when the tree structure data specifies a structure of a subtree that may be a search target of the computer,
A computer-readable recording medium in which information of a subtree conforming to a specified structure is collectively recorded so that the computer can access it. 14. In the tree structure data, a structure of a subtree that may be a search target is specified, and a subtree conforming to the specified structure is extracted from the tree structure data. A data storage method characterized by storing the above information collectively.