WO2015125230A1 - Data update method, and computer system - Google Patents

Abstract

When new unit data is added to original graph data, a computer system identifies from meta information of contraction graph data a first contraction value which is a contraction value corresponding to a first node value in the new unit data and a second contraction value which is a contraction value corresponding to a second node value in the new unit data, and adds, to the contraction graph data, new unit contraction data combining the first contraction value, the second contraction value, and an edge from the first contraction value to the second contraction value (the same edge as an edge in the new unit data).

Description

Data update method and computer system

The present invention generally relates to updating graph data.

The graph data is used for at least a part of the database, for example, and is used as a search range. As graph data, for example, RDF data (data in a format called RDF (Resource Description Framework)) is known. Regarding the reduction of RDF data, a technique disclosed in Patent Document 1 is known. According to Patent Document 1, reduced RDF data obtained by reducing the original RDF data is generated.

International Publication No. 2013/111287 Pamphlet

When data is added to the original RDF data, new reduced RDF data is created from the original RDF data after data addition so that the data added from the RDF data can be acquired through the reduced RDF data. Will do.

However, reduction of graph data such as RDF data takes time according to the size of the graph data.

The original graph data is a set of a plurality of unit data, and each unit data is a combination of a first node value, a second node value, and an edge from the first node value to the second node value. The contract graph data is a set of unit contract data, and each unit contract data includes a contract value of the first node value, a contract value of the second node value, and a contract of the first node value. It is a combination with an edge from the reduced value to the reduced value of the second node value. When new unit data is added to the original graph data, the computer system determines from the meta information of the reduced graph data the first reduced value corresponding to the first node value in the new unit data. A reduction value and a second reduction value that is a reduction value corresponding to the second node value in the new unit data are specified, and the first reduction value, the second reduction value, New unit contracted data that is a combination of an edge from the contracted value of 1 to the second contracted value (the same edge as the edge in the new unit data) is added to the contracted graph data.

Even if new data is added to the original graph data, the data added from the RDF data after the data is added through the reduced RDF data without creating new reduced graph data from the original graph data after the data is added. Searchable.

1 shows a configuration of a computer system according to an embodiment. The table format structure of the original RDF data 115 is shown. The structure of unit RDF data is shown. The tree structure which the original RDF data 115 of FIG. 2 represents is shown. An example of adding unit RDF data to the original RDF data 115 is shown. An outline of a flow for creating the contraction criterion table 101 based on the original RDF data 115 is shown. An outline of the flow of creating the contracted RDF data 116 using the contraction criterion table 101 is shown. A table format structure of the reduced RDF data 116 is shown. An example of search processing using the contracted RDF data 116 is shown. It is a flowchart of a difference update process. 12 is a flowchart of contracted RDF update processing (step 1004 in FIG. 10). 12 is a flowchart of contracted value determination processing (step 1102 in FIG. 11). An example of the result of step 1203 of FIG. 12 is shown. An example of the result of step 1213 in FIG. 12 is shown. An example of the result of step 1103 in FIG. 11 is shown. It is a flowchart of a data reduction process. An example of a contraction condition setting screen is shown.

Hereinafter, an embodiment in which RDF data is employed as graph data will be described.

In the following description, information may be described by the expression “kkk table”, but the information may be expressed by a data structure other than the table. In order to show that it does not depend on the data structure, the “kkk table” can be called “kkk information”.

In the following description, the process may be described using “program” as a subject. However, the program is executed by the processor, so that the determined process can be appropriately performed with storage resources (for example, memory) and / or Alternatively, since the processing is performed using a communication interface device (for example, a communication port), the subject of processing may be a processor. On the contrary, the processing whose subject is the processor can be interpreted as being executed by executing one or more programs.

FIG. 1 shows a configuration of a computer system according to the embodiment.

The computer system 100 is a system including one or more computers. The one or more computers include at least one physical computer and may include one or more virtual computers. The computer system 100 includes an input device 111, an output device 112, a communication interface device (I / F) 113, a storage resource 103, and a processor 110 connected to them. At least one of the input device 111 and the output device 112 may be present in a remote display computer (not shown) connected to the computer system 100.

The input device 111 is one or more input devices, and may be a keyboard and a pointing device, for example. The output device 112 is one or more output devices including a display device, and may be a liquid crystal display, for example. The input device 111 and the output device 112 may be integrated like a touch panel.

The I / F 113 is one or more communication interface devices, and may be, for example, at least one of a LAN (Local Area Network) controller and an HBA (Host Bus Adapter). An external storage device 114 is connected to the I / F 113. The external storage device 114 may be a storage device such as SSD (Solid State Drive) or HDD (Hard Disk Drive), or one or more RAID (Redundant Arrays of Inexpensive (or It may be a storage device having an Independent) Disks) group. The external storage device 114 stores the original RDF data 115 and the reduced RDF data 116 that is the result of reducing the original RDF data 115. In the present embodiment, RDF data is referred to as “original RDF data” in the sense of original data of reduced RDF data. The original RDF data 115 and the contracted RDF data 116 may be data in a database, for example. There is no external storage device 114, and the original RDF data 115 and the reduced RDF data 116 may be stored in the storage resource 103 like an in-memory database.

Storage resource 103 is one or more storage devices including volatile or nonvolatile memory. The storage resource 103 stores the reduction criterion table 101 and the reduction table 102 created when the original RDF data 115 is reduced. The contraction criterion table 101 and the contraction table 102 are examples of meta information of the contracted RDF data 116. Further, the storage resource 103 includes an initial contracted program 104 that creates the contracted RDF data 116 for the first time, a query processing program 105 that converts the input original query into a contracted query and processes the contracted query, and the contracted RDF data 116. And a data organizing program 107 for newly creating contracted RDF data based on the original RDF data 115 even when a predetermined condition is met. These programs 104 to 107 are executed by the processor 110. For example, the difference update program 106 can perform reduced RDF update processing and reduced value determination processing described later.

The processor 110 is one or more processors. The processor may be a microprocessor such as a CPU (Central Processing Unit), a processor core such as a CPU core, or a part of processing (at least one of them) ( For example, a hardware circuit that performs encryption / decryption or compression / decompression) may be included.

FIG. 2 shows a tabular structure of the original RDF data 115.

As shown in FIG. 2, the original RDF data 115 has a tabular format, and is composed of a plurality of records respectively corresponding to a plurality of unit RDF data. Each record has the values of the subject, predicate, and object of the unit RDF data corresponding to the record. The original RDF data 115 represents the rank, the degree, the name, and the friendship of five countries A, B, C, D, and E.

As shown in FIG. 3, the unit RDF data is composed of three elements (values) called “subject”, “predicate”, and “object”. The unit data of the graph data is a combination of the first node value, the second node value, and the edge from the first node value to the second node value. In the unit RDF data, the subject is the first node value. It is an example, the predicate is an example of an edge, and the object is an example of a second node value. The unit RDF data may be referred to as “triple”.

The original RDF data 115 having a tree structure as shown in FIG. 4 is constructed by combining the unit RDF data as shown in FIG. In other words, the table of FIG. 2 represents the tree structure of FIG. The graph data is generally a set of a plurality of nodes and a plurality of edges, but the original RDF data 115 has the same configuration. In the original RDF data 115, a node (an example of a non-terminal node) that can be both a subject and an object is called a “resource”, and a node (an example of a terminal node) that can be only an object is called a “literal”. is there.

Unit RDF data may be added to the original RDF data 115 as shown in FIG. Specifically, a record corresponding to the unit RDF data to be added may be added to the original RDF data 115 in FIG. In this way, it is easy to add unit RDF data to the original RDF data 115.

However, in order to be able to acquire the added unit RDF data from the original RDF data 115 using the reduced RDF data 116, according to the prior art, the reduced unit RDF data 115 after the addition of the unit RDF data is used. RDF data 116 must be newly created.

In this embodiment, when the unit RDF data is added to the additional original RDF data 115, the contraction criterion table 101 and the contraction table 102 are updated as necessary, and the contraction criterion table 101 and the contraction table 102 are updated. The contracted values of the subject and the object in the added unit RDF data are acquired. Then, unit contracted RDF data including the two acquired contracted values and a predicate connecting them (the same predicate as the predicate in the added unit RDF data) is added to the contracted RDF data 115. Thus, the added unit RDF data can be acquired from the original RDF data 115 using the reduced RDF data 116 without newly creating the reduced RDF data 116 from the original RDF data 115 after the unit RDF data is added. In the present embodiment, the “contracted value” may be any unique value.

Hereinafter, this embodiment will be described in more detail.

First, an outline of the flow of creating the reduced RDF data 116 will be described with reference to FIGS. 6 and 7. FIG. 6 shows an outline of a flow for creating the contracted criterion table 101 based on the original RDF data 115, and FIG. 7 shows an overview of a flow for creating the contracted RDF data 116 using the contracted criterion table 101. .

As shown in FIG. 6, the initial contraction program 104 creates a plurality of RDF data portions having the same structure by selecting a plurality of resources having the same predicate from the original RDF data 115. Each RDF data part has a resource (subject), two predicates (rank, degree) extending from the resource, and an object connected to each of the two predicates. The initial reduction program 104 takes out a set of object values from a plurality of RDF data parts, and sets values such that the value sets (number of objects) belonging to each group (object value range) are equal, for example. Divide the set. The value set may be divided according to other rules such as division based on access frequency. The initial contraction program 104 creates a contraction range (object value range) of the contraction criterion table 101 from the threshold values (maximum value and minimum value of the value set) at the time of division. For example, even if the value is a character string, the maximum value and the minimum value can be determined by arranging according to a predetermined rule such as a dictionary order or a character code order. The initial reduction program 104 generates and associates a reduction value uniquely corresponding to each reduction range, and manages the predicate as a reference predicate. The reduction standard table 101 created in this way represents a standard defined for associating a plurality of literals with reduction values. According to the contraction criterion table 101 shown in FIG. 6, with respect to the standard predicate “rank”, an object having a value less than 2 is converted into a contraction value “c1”, and an object having a value of 2 or more is contracted. It will be converted to the value “c2”.

Next, as shown in FIG. 7, the initial contraction program 104 contracts each literal (object) of a plurality of RDF data portions having the same structure using the contraction criterion table 101 (see FIG. 6). Convert to value. Then, the initial contraction program 104 creates a resource set by aggregating resources of two or more RDF data parts including the same contraction value. The initial reduction program 104 generates and associates a reduction value uniquely corresponding to each resource set, and registers the correspondence relationship in the reduction table 102. That is, the initial reduction program 104 obtains a reduction value based on the reduction criterion table 101 for all literals in the original RDF data 115, and a reduction table 102 indicating the correspondence between the original resource and the reduction value. Create If there are multiple resources to be the subject and each resource is connected to the same contracted object (literal contracted value), the resources connected to the same contracted value will have the same contracted value, The correspondence is managed in the contract table. The contraction table 102 is information that associates a plurality of resources included in the original RDF data 115 with one contracted value. The initial reduction program 104 converts the value of each resource into a reduction value based on the reduction table 102. As a result of executing such resource conversion (converting a resource value into a contracted value) and literal conversion (converting a literal value into a contracted value) on the original RDF data 115, the contracted RDF Data 116 is created. Note that the contracted value can be determined again by using the contracted value of the resource and obtaining a resource set using the contracted value as a predicate. By repeating this operation, all nodes of the original RDF data 115 can be converted into contracted values. FIG. 8 shows a tabular structure of the generated reduced RDF data 116. In FIG. 8, when the value of a literal (object) is a character string, it cannot be given an order such as descending order or ascending order, unlike a numerical value. In addition, since the distance between character strings cannot be defined, the value range cannot be set. Therefore, when the literal value is a character string, the literal value is an invalid value (for example, “other”) in the contracted RDF data 116, and the literal is not subject to contraction. However, the literal of the character string may be reduced by converting the character string into a numerical value by a character code or other rules.

The computer system 100 can retrieve data from the original RDF data 115 using the reduced RDF data 116.

For example, it is assumed that the computer system 100 receives a query (hereinafter, original query) 901 shown in FIG. 9 from a query issuer. The query issuer may be an application program (not shown) executed in the computer system 100 or a computer (not shown) outside the computer system 100. Further, the above-described programs 104 to 107 may be included in the database management system. The original query 901 is a request to search for a resource whose predicate “rank” has an object value of 4 or more and whose predicate “degree” has an object value of 1.

First, the query processing program 105 converts the original query 901 into a contracted query 902. The contracted query 902 is a query in which the condition value in the original query 901 is converted into a contracted value.

Specifically, for example, the query processing program 105 converts literals connected to the predicates “rank” and “degree” into contracted values using the contraction criterion table 101, respectively. As a result, “4 or more” for “rank” is converted to the contracted value “c2”, and “1” for “degree” is converted to the contracted value “c3”. Further, if the value is a resource, the query processing program 105 converts the value of the resource using the contraction table 102. By the conversion so far, the contracted query 902 is generated.

The query processing program 105 executes pattern matching between the contracted query 902 and the contracted RDF data 116. As a result, the reduced RDF data part of the resource “c6” and the literals “c2” and “c3” can be found. Thereafter, the query processing program 105 uses the contraction table 102 and the original query 901 to return the contracted value to the original value. As a result, the reduced value “c6” is returned to the resource “B” or “D”, the reduced value “c2” is returned to “4 or more”, and the reduced value “c3” is returned to “1”. . The query processing program 105 searches the original RDF 115 using the information (the original query 901 in which “B” or “D” is substituted for the resource value). That is, the query processing program 105 determines that the data corresponding to “1” for “rank” and “1” for “rank” and “4” for “rank” and “rank” for the resource “B”. The data corresponding to “1” for “degree” is searched from the original RDF data 115. As a result, data with the resource “B” and “rank” “7” and “degree” “1” is found.

Thus, by using the contracted RDF data 116, a large number of resource candidates can be narrowed down to “B” and “D”. By narrowing down, it is not necessary to search for resources other than “B” and “D”, and the search time can be shortened.

In the present embodiment, in such a computer system 100, it is possible to update the contracted RDF data 116 and update the meta information (contraction standard table 101 and contract table 102). This will be described in detail below.

FIG. 10 is a flowchart of the difference update process.

The difference update program 106 acquires the difference with respect to the original RDF data 115 as an input (step 1001). The difference is addition of unit RDF data to the original RDF data 115 or deletion of unit RDF data from the original RDF data 115. When the value in a certain unit RDF data is updated to another value, both the deletion of the certain unit RDF data and the addition of the unit RDF data including the updated value are performed.

The difference update program 106 locks the database (step 1002). The database lock may be, for example, a state where the query processing program 105 does not process the original query. By locking the database, it is possible to avoid an error that data in the updated database is not returned to the query issuer.

Thereafter, the difference update program 106 updates the original RDF data 115 in accordance with the difference input in Step 1001 (Step 1003). For example, if the difference is addition of unit RDF data, the difference update program 106 adds a record corresponding to the addition target unit RDF data to the original RDF data 115. For example, if the difference is deletion of the unit RDF data, the difference update program 106 deletes the record corresponding to the unit RDF data to be deleted from the original RDF data 115.

The difference update program 106 performs a contracted RDF update process (step 1004).

Thereafter, the differential update program 106 unlocks the database (step 1005). Thereafter, the query processing program 105 can process the original query.

As alternative examples of database lock / unlock, the following alternative examples 1 and 2 can be considered. In alternative example 1, the differential update program 106 takes a snapshot of each of the original RDF data 115 and the reduced RDF data 116, and when processing the original query during the differential update process, the original RDF data 115 and the reduced RDF data 115 are reduced. Each snapshot of RDF data 116 may be referenced. In alternative example 2, the difference update program 106 uses the reduced RDF update process (step 1004) for the difference input in step 1001 for the reference RDF data 115 without using the reduction technique until the end. You can do a fallback.

FIG. 11 is a flowchart of the contracted RDF update process (step 1004 in FIG. 10).

The difference update program 106 determines whether or not the difference (input in step 1101 in FIG. 10) is deletion (step 1101).

When the difference is added (step 1101: No), the difference update program 106 performs a contracted value determination process (step 1102). Thereby, each of the subject and the object in the added unit RDF data is converted into a contracted value, and the contraction reference table 101 or the contraction table 102 is updated as necessary. Then, the difference update program 106 changes the predicate in the added unit RDF data from the first contracted value that is the contracted value of the subject to the second contracted value that is the contracted value of the object. A record corresponding to unit contracted RDF data that is a combination of the first contracted value, the second contracted value, and a predicate that connects them is added to the contracted RDF data 116 by connecting with the same predicate ( Step 1103). Thereby, the contracted RDF update process ends.

If the difference is deleted (step 1101: Yes), the difference update program 106 ends the reduced RDF update process without executing steps 1102 and 1103. That is, when the difference is deleted, neither the contracted RDF data 116 nor its meta information is updated. In other words, the contracted RDF data 116 only needs to include the connection relationship in the original RDF data 115 without a shortage. Even if a contracted value of a node that is not in the original RDF data 115 is specified from the contracted RDF data 116 and the contracted value is used, only the corresponding data is not found in the original RDF data 115, and the query issuer is notified. It does not cause any problems. From this point of view, when the difference is deletion, steps 1102 and 1103 are skipped, so that the contracted RDF update process is completed in a short time.

In the case of updating the value in the unit RDF data, the difference is both deletion and addition as described above. In this case, the process when the difference is deletion is not executed, and only the process when the difference is added may be executed.

FIG. 12 is a flowchart of the contracted value determination process (step 1102 in FIG. 11). This processing is performed for each of the subject and object of the added unit RDF data. Therefore, the process of FIG. 12 is performed twice for one unit RDF data.

The difference update program 106 determines whether or not the object in the added unit RDF data is a literal (step 1201).

When the object is a literal (step 1201: Yes), the difference update program 106 determines whether or not the predicate in the added unit RDF data has been contracted based on the contraction criterion table 101 (step 1202). . If the same reference predicate as the predicate in the added unit RDF data is registered in the contraction standard table 101, the determination result in step 1202 is true (contracted).

When the determination result of step 1202 is false (step 1202: No), the difference update program 106 adds a record that uses the predicate in the added unit RDF data as a reference predicate to the contracted reference table 101 (step 1203). ). In the added record, the contracted value assigned by the difference update program 106 to the predicate and the contracted range using the object (value) in the added unit RDF data as a threshold value are registered. . FIG. 13 shows an example of the result of step 1203, that is, an example of a record (record in a broken line frame) added to the contraction criterion table 101. This example corresponds to the addition illustrated in FIG. 5 (unit RDF data in a broken line frame). After step 1203, the difference update program 106 determines a contracted value corresponding to the object in the added unit RDF data from the contraction criterion table 101 (step 1204). That is, the difference update program 106 converts the subject and object in the added unit RDF data into contracted values.

If the determination result in step 1202 is true (step 1202: Yes), the difference update program 106 determines a contraction value for each of the subject and object in the added unit RDF data without performing step 1203. (Step 1204).

If the object is not a literal (step 1201: No), the difference update program 106 determines whether the subject or object in the added unit RDF data is a new resource based on the contract table 102 (step 1212). ). If the subject (value) or object (value) in the added unit RDF data is not registered in the contract table 102 as a resource, the determination result in step 1212 is true (new resource).

If the determination result in step 1212 is true (step 1212: Yes), the difference update program 106 adds a record that uses the subject or object in the added unit RDF data as a new resource to the contraction table 102 ( Step 1213). In the added record, the contracted value assigned to the new resource by the differential update program 106 is registered. FIG. 14 shows an example of the result of step 1213, that is, an example of a record added to the contraction table 102 (a record in a broken line frame). This example corresponds to the addition illustrated in FIG. 5 (unit RDF data in a broken line frame). When both the subject and the object in the added unit RDF data correspond to the new resource, two records corresponding to the subject and the object are added to the contract table 102, respectively. After step 1213, the difference update program 106 determines a contracted value corresponding to the subject or object in the added unit RDF data from the contract table 102 (step 1214). That is, the difference update program 106 converts the subject and object in the added unit RDF data into contracted values.

If the determination result in step 1212 is false (step 1212: No), the difference update program 106 determines a contraction value for each of the subject or object in the added unit RDF data without performing step 1213. (Step 1214).

In step 1204 or 1214, the contracted value determination process (step 1102 in FIG. 11) ends. Thereafter, step 1103 in FIG. 11 is performed. FIG. 15 shows an example of the result of step 1103, that is, an example of a record (record in a broken line frame) added to the contracted RDF data 116. This example corresponds to the addition illustrated in FIGS. 5, 13, and 14 (unit RDF data in a broken line frame).

As described above, the contracted RDF data 116 is updated, and the meta information (contract standard table 101 and contract table 102) is updated. Thus, even if the original RDF data 115 is updated, the reduced RDF data 116 is used from the updated original RDF data 115 without newly creating the reduced RDF data 116 from the updated original RDF data 115. Data can be acquired.

If the reduced RDF data 116 is continuously updated as described above, the search performance may be deteriorated.

Specifically, for example, in creating the contracted RDF data 116, the literal value range (contracted range) is divided so that the number of literals is equal. For example, if there are 1000 literals and the value of 1000 literals is an integer consecutive with 1 to 1000, the literal value range is divided into 1 to 250, 251 to 500, 501 to 750, and 751 to 1000. May be. As a result, the number of literals belonging to each value range is equal to 250, and when the search range is narrowed down using the contracted RDF data 116, the bias in the number of elements (literal number) included in the narrowing down destination is prevented. Therefore, moderate search performance can be maintained. However, in this embodiment, the reduced RDF data 116 and its meta information are updated, but the value range (reduced range) is not subdivided. For this reason, when the difference increases, the bias (bias) of a plurality of literal numbers corresponding to each of a plurality of value ranges increases, and a sufficient narrowing effect cannot be obtained, thereby possibly degrading search performance. .

Therefore, in this embodiment, the data organization program 107 performs the data organization process shown in FIG. Specifically, the data reduction program 107, when a reduction condition, which is a predetermined condition for which the search performance is regarded as degraded (Step 1601: Yes), is updated from the original RDF data 115 to the latest reduced RDF. Data is created (step 1602). After step 1602, the old reduced RDF data may be deleted from the external storage device 114 by the data reduction program 107.

The contraction condition may be determined in advance so that it cannot be changed, may be changed by an administrator (manually), or automatically (for example, history information regarding search processing using the contracted RDF data 116 is stored. May be changed). For example, the data reduction program 107 displays a reduction condition setting screen for inputting reduction conditions on the output device (display device) 112.

FIG. 17 shows an example of the contraction condition setting screen.

The reduction condition setting screen is, for example, a GUI (Graphical User Interface), a tool (for example, a check box) that specifies which of the five conditions is adopted as the reduction condition, and a threshold value associated with each condition. And an input field. The data reduction program 107 sets contraction condition information representing the contraction condition input through the contraction condition setting screen in the storage resource 103.

As described above, the contraction condition includes at least one of the following five conditions.

(1) Frequency

The frequency is an elapsed time since step 1602 (new generation of contracted graph data) is performed immediately before. That is, “frequency” as the contraction condition means that step 1602 is periodically performed. The threshold corresponding to the frequency is the execution cycle of step 1602 (for example, “every Saturday”), and the execution cycle can be input in the threshold value input column corresponding to the frequency. The data reduction program 107 newly generates contracted graph data for each period set as the threshold value. Note that the data reduction program 107 changes the time series of the execution time of step 1602 and the search performance (for example, the time from when one original query is received until the search result according to the original query is returned to the query issuer), The history information including at least one of the time-series changes in the load of the processor 110 is stored in the storage resource 103 (or the external storage device 114), and the threshold corresponding to the frequency is updated based on the history information. Also good. When the new reduced RDF data 116 is newly created, a process for inspecting all of the original RDF data 115 is included. Therefore, the data reduction program 107 further determines the frequency based on the size of the original RDF data 115. You may update the threshold value corresponding to.

(2) Time

The time is a time (for example, year / month / day / minute) at which step 1602 (new generation of contracted graph data) is performed. That is, “time” as the contraction condition means that step 1602 is performed at the specified time. The threshold corresponding to the time is the execution time of step 1602, and the execution time (for example, “2014/02/12/02: 00”) can be input in the threshold value input field corresponding to the time. The data reduction program 107 newly generates contracted graph data when the current time reaches the time as a threshold. The data reduction program 107 stores history information including at least one of the execution time immediately before step 1602, a time-series change in search performance, and a time-series change in the load on the processor 110 as the storage resource 103 ( Alternatively, the threshold value corresponding to the time may be determined based on the history information stored in the external storage device 114). The data reduction program 107 may determine a threshold corresponding to the time based further on the size of the original RDF data 115.

(3) Differential capacity ratio

The difference capacity ratio means a magnification of the size of the original graph data at the present time with respect to the size of the original graph data at a certain time in the past. If the original graph data is not updated, there will be no bias in the number of literals (number of elements) corresponding to each of a plurality of value ranges (reduction ranges). Even if the original RDF data 115 is contracted in a state where the number of literals is not biased, useless processing is performed. Therefore, the differential capacity ratio is adopted as an element of the contraction condition. The threshold value corresponding to the differential capacity ratio is the above-described magnification as the differential capacity ratio, and the magnification (for example, “200%”) can be input in the threshold value input field corresponding to the differential capacity ratio. The data reduction program 107 newly reduces the reduced graph when the magnification of the original graph data size at the present time reaches the magnification set as the threshold with respect to the original graph data size at a certain past time. Generate data. The data reduction program 107 stores history information including the time series change of the difference capacity ratio and the time series change of the search performance in the storage resource 103 (or the external storage device 114), and based on the history information, a difference is stored. The threshold value corresponding to the capacity ratio may be updated. The data reduction program 107 may update the threshold corresponding to the differential capacity ratio based on the size of the original RDF data 115.

(4) Search performance

The threshold corresponding to the search performance is the above time as the search performance, and the time (for example, “1 sec”) can be input in the threshold value input column corresponding to the search performance. The data reduction program 107 may monitor the search performance. When the search performance is lower than the search performance set as the threshold value by a predetermined number of times (for example, even once) (when the time required for the search becomes longer than the threshold time), the data reduction program 107 Generate reduced graph data.

(5) Unbalance

As described above, at the time of creation of the contracted RDF data 116, the number of literals belonging to each value range (contracted range) is equal. The number of literals for each value range may be stored in the storage resource 103 by the initial reduction program 104 or the data reduction program 107. Each time the original RDF data 115 is updated (data addition or data deletion), the data reduction program 107 or the difference update program 106 specifies the value range to which the literal included in the added or deleted data belongs, and the specified value The number of literals corresponding to the range may be updated. As the bias of the number of literals (number of elements), for example, a ratio of the minimum value of the literal number to the maximum value of the literal number can be input in the threshold value input field. The data reduction program 107 newly generates contracted graph data when the bias of the plurality of literal numbers respectively corresponding to the plurality of value ranges exceeds the bias as the input threshold value.

As mentioned above, although one embodiment was described, this is an illustration for explaining the present invention, and the scope of the present invention is not limited to this embodiment. The present invention can be implemented in various other forms. For example, link information (index) from the contracted RDF data 116 may be added to each record of the original RDF data 115. The link information may include contracted values corresponding to the subject and the object, respectively. In this case, the query processing program 105 can specify the resource from the original RDF data 115 using the contracted value as a key.

100: Computer system

Claims (14)

A data update method used in a system for retrieving data from the original graph data using the reduced graph data, which is data obtained by reducing the original graph data,
The original graph data is a set of unit data,
Each unit data is a combination of a first node value, a second node value, and an edge from the first node value to the second node value,
The reduced graph data is a set of a plurality of unit reduced data,
Each unit reduced data includes a reduced value of the first node value, a reduced value of the second node value, an edge from the reduced value of the first node value to the reduced value of the second node value, and A combination of
The data update method includes:
When new unit data is added to the original graph data, a first contraction that is a contraction value corresponding to a first node value in the new unit data is obtained from the meta information of the contraction graph data. A value and a second reduced value that is a reduced value corresponding to the second node value in the new unit data;
The first reduced value, the second reduced value, and the edge from the first reduced value to the second reduced value, the same edge as the edge in the new unit data Adding new unit contracted data that is a combination of and to the contracted graph data,
Data update method. The meta information includes first and second sub meta information,
The first sub meta information is information representing a relationship between a contracted value for each edge in the original graph data and a range of terminal node values in the original graph data;
The second sub meta information is information representing a plurality of contracted values respectively corresponding to a plurality of non-terminal node values included in the original graph data.
The data update method according to claim 1. If the second node value in the new unit data is a terminal node value and the type of edge in the new unit data is not registered in the first sub meta information, the edge in the new unit data A first combination of a new contracted value and a value range determined according to a second node value in the new unit data is added to the first sub meta information,
The second contracted value is specified from the first sub meta information including the first combination.
The data update method according to claim 2. The second node value in the new unit data is a non-terminal node value, and at least one of the first node value and the second node value in the new unit data is not registered in the second sub meta information. A second combination of a value that is at least one of the first node value and the second node value in the new unit data and is not registered in the second sub-meta information, and a new contracted value, Adding to the second sub-meta information,
The first contracted value is specified from the second sub meta information including the second combination.
The data update method according to claim 2. Even if unit data is deleted from the original graph data, the contracted graph data is not updated.
The data update method according to claim 1. Accepts input for certain conditions that are considered degraded search performance,
When the predetermined condition is satisfied, the contracted graph data is newly generated by contracting the original graph data.
The data update method according to claim 1. That the predetermined condition is satisfied is that (a) a predetermined time has elapsed since the generation of the new reduced graph data immediately before, (b) the current time is the predetermined time, (c) the current source The size of the graph data is greater than or equal to a predetermined magnification compared to the size of the original graph data at a certain time in the past, (d) the performance of retrieving data from the original graph data has decreased below a predetermined value, (E) At least one of the plurality of terminal node biases belonging to the plurality of terminal node value ranges is equal to or greater than a predetermined bias,
The data update method according to claim 6. A storage resource for storing meta information of the reduced graph data, which is data obtained by reducing the original graph data;
A processor connected to the storage resource and retrieving data from the original graph data using the reduced graph data;
The original graph data is a set of unit data,
Each unit data is a combination of a first node value, a second node value, and an edge from the first node value to the second node value,
The reduced graph data is a set of a plurality of unit reduced data,
Each unit reduced data includes a reduced value of the first node value, a reduced value of the second node value, an edge from the reduced value of the first node value to the reduced value of the second node value, and A combination of
When new unit data is added to the original graph data, the processor
A first contracted value corresponding to a first node value in the new unit data and a second contracted value corresponding to a second node value in the new unit data. Identifying an approximate value from the meta information,
The first reduced value, the second reduced value, and the edge from the first reduced value to the second reduced value, the same edge as the edge in the new unit data Adding new unit contracted data that is a combination of and to the contracted graph data,
Computer system. The meta information includes first and second sub meta information,
The first sub meta information is information representing a relationship between a contracted value for each edge in the original graph data and a range of terminal node values in the original graph data;
The second sub meta information is information representing a plurality of contracted values respectively corresponding to a plurality of non-terminal node values included in the original graph data.
The computer system according to claim 8. If the second node value in the new unit data is a terminal node value, and the edge type in the new unit data is not registered in the first sub meta information, the processor Adding a first combination of an edge in the data, a new reduced value, and a value range determined according to a second node value in the new unit data to the first sub meta information;
The second contracted value is specified from the first sub meta information including the first combination.
The computer system according to claim 9. The second node value in the new unit data is a non-terminal node value, and at least one of the first node value and the second node value in the new unit data is not registered in the second sub meta information. In this case, the processor has a second value of a value that is at least one of the first node value and the second node value in the new unit data and is not registered in the second sub-meta information, and a new reduced value. Is added to the second sub-meta information,
The first contracted value is specified from the second sub meta information including the second combination.
The computer system according to claim 9. Even if unit data is deleted from the original graph data, the processor does not update the reduced graph data.
The computer system according to claim 8. The processor is
Accepts input for certain conditions that are considered degraded search performance,
When the predetermined condition is satisfied, the contracted graph data is newly generated by contracting the original graph data.
The computer system according to claim 8. That the predetermined condition is satisfied is that (a) a predetermined time has elapsed since the generation of the new reduced graph data immediately before, (b) the current time is the predetermined time, (c) the current source The size of the graph data is greater than or equal to a predetermined magnification compared to the size of the original graph data at a certain time in the past, (d) the performance of retrieving data from the original graph data has decreased below a predetermined value, (E) At least one of the plurality of terminal node biases belonging to the plurality of terminal node value ranges is equal to or greater than a predetermined bias,
The computer system according to claim 13.

Images