Representing incomplete and uncertain information in graph data

• US 8,661,004 B2
• Filed: 05/21/2012
• Issued: 02/25/2014
• Est. Priority Date: 05/21/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kementsietsidis, Anastasios, Pema, Enela
• Primary Examiner(s): Fleurantin, Jean B
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US13/476,316
• Publication Number:
  US 20130311507A1
• Time in Patent Office: 645 Days
• Field of Search: 707/758, 707/714, 707/694, 707/760, 707/759, 707/791, 707/797, 707/798, 707/802, 707/748, 707/793, 707/E17.044, 707/E17.011, 707/E17.03, 707/E17.017, 707/E17.007, 707/E17.033, 707/E17.073, 707/616, 707/778, 707/956, 707/608, 707/609, 707/821, 707/736, 707/E17.014, 707/E17.055, 706/45, 345/440, 345/619, 370/410, 717/120, 717/142, 717/154
• US Class Current: 707/694
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A method for representing and querying incomplete and uncertain information in graph data receives a plurality of graphs containing subject nodes, object nodes and predicates extending between subject and object nodes. The subject nodes and predicates can be URIs or blank, and the object nodes can be URIs, literals or blank. Incomplete graph data sets are created by a variable into each blank subject node, each blank predicate and each blank object node, and uncertain graph data sets are created by substituting alternative values for all variables in the incomplete data graph. A query is received from a user and a naïve search of the graph data is performed for certain data. The incomplete and uncertain graphs are then used to determine potential answers and certain potential answers based on user-specified requirements. The certain answers and potential certain answers are returned to the user.

Claims

1. A method for representing incomplete and uncertain information in graph data, the method comprising:

receiving graph data comprising a plurality of graphs, each graph comprising a subject node, an object node and a predicate extending from the subject node to the object node; and

using a computer system comprising one or more processors running a computer application to;

create an incomplete graph data set comprising the plurality of graphs by inserting a variable into at least one of the subject node, the predicate and the object node in one or more graphs within the plurality of graphs; and

create an uncertain graph data set from the incomplete graph data set by substituting alternative values for all variables in the incomplete data graph set, wherein each variable is replaced by a given group of alternative values each group of alternative values selected from a set of alternative values comprising a union of all subsets of a set of all uniform resource identifiers in the received graph data and all subsets of a set of all literals in the received graph data;

wherein;

the step of creating an incomplete graph data set further comprises creating a plurality of incomplete graph data sets by inserting a variable into each blank subject node, each blank predicate and each blank object node in each one of a plurality of distinct sets of blank subject nodes, blank predicates and blank object nodes within the plurality of graphs; and

the step of creating an uncertain graph data set further comprises creating a plurality of uncertain graph data sets, one uncertain graph data set for each incomplete graph data set.

2. The method of claim 1, wherein:

each subject node comprises a uniform resource identifier or a blank subject node, each predicate comprises a uniform resource identifier or a blank predicate and each object node comprises a uniform resource identifier, a literal or a blank object node; and

to create the incomplete graph data set further comprises inserting the variable into each blank subject node, each blank predicate and each blank object node in each graph within the plurality of graphs.

3. The method of claim 1, wherein the method further comprises creating a partial uncertain graph data set by substituting alternative values for a portion of all variables in the incomplete data graph, wherein each variable is replaced by a given group of alternative values selected from the set of alternative values.

4. The method of claim 3, wherein the step of creating the partial uncertain graph data set further comprises creating a plurality of partial uncertain graph data sets by substituting alternative values for variables in each one of a plurality of portions of all variables in the incomplete data set, each portion in the plurality of portions comprising a distinct portion.

5. The method of claim 1, wherein the step of creating the incomplete graph data set further comprises only inserting variables in object nodes located at graph endpoints, each graph endpoint comprising a node within the graph data lacking any links extending out from that node.

6. The method of claim 1, wherein the step of creating an uncertain graph data set further comprises creating a plurality of uncertain graph data sets by substituting alternative values for all variables in each one of a plurality of subsets of variables in the incomplete data graph set, each subset of variables comprising a distinct subset of variables.

7. The method of claim 1, wherein the method further comprises creating a probabilistic graph data set by substituting a distinct set of alternative values for each variable in the incomplete data graph set, wherein each set of alternative values comprises at least one alternative value selected from the set of alternative values and a pre-determined probability associated with each alternative value in that set of alternative values.

8. A non-transitory computer-readable storage medium containing a computer-readable code that when read by a computer causes the computer to perform a method for representing incomplete and uncertain information in graph data, the method comprising:

receiving graph data comprising a plurality of graphs, each graph comprising a subject node, an object node and a predicate extending from the subject node to the object node;

creating an incomplete graph data set comprising the plurality of graphs by inserting a variable into at least one of the subject node, the predicate and the object node in one or more graphs within the plurality of graphs; and

creating an uncertain graph data set from the incomplete graph data set by substituting alternative values for all variables in the incomplete data graph set, wherein each variable is replaced by a given group of alternative values, each group of alternative values selected from a set of alternative values comprising a union of all subsets of a set of all uniform resource identifiers in the received graph data and all subsets of a set of all literals in the received graph data;

wherein;

the step of creating an incomplete graph data set further comprises creating a plurality of incomplete graph data sets by inserting a variable into each blank subject node, each blank predicate and each blank object node in each one of a plurality of distinct sets of blank subject nodes, blank predicates and blank object nodes within the plurality of graphs; and

the step of creating an uncertain graph data set further comprises creating a plurality of uncertain graph data sets, one uncertain graph data set for each incomplete graph data set.

9. The non-transitory computer-readable storage medium of claim 8, wherein:

each subject node comprises a uniform resource identifier or a blank subject node, each predicate comprises a uniform resource identifier or a blank predicate and each object node comprises a uniform resource identifier, a literal or a blank object node;

the step of creating the incomplete graph data set further comprises inserting the variable into each blank subject node, each blank predicate and each blank object node in each graph within the plurality of graphs.

10. The non-transitory computer-readable storage medium of claim 8, wherein the method further comprises creating a partial uncertain graph data set by substituting alternative values for a portion of all variables in the incomplete data graph, wherein each variable is replaced by a given group of alternative values selected from the set of alternative values.

11. The non-transitory computer-readable storage medium of claim 10, wherein the step of creating the partial uncertain graph data set further comprises creating a plurality of partial uncertain graph data sets by substituting alternative values for variables in each one of a plurality of portions of all variables in the incomplete data set, each portion in the plurality of portions comprising a distinct portion.

12. The non-transitory computer-readable storage medium of claim 8, wherein the step of creating the incomplete graph data set further comprises only inserting variables in object nodes located at graph endpoints, each graph endpoint comprising a node within the graph data lacking any links extending out from that node.

13. The non-transitory computer-readable storage medium of claim 8, wherein the step of creating an uncertain graph data set further comprises creating a plurality of uncertain graph data sets by substituting alternative values for all variables in each one of a plurality of subsets of variables in the incomplete data graph set, each subset of variables comprising a distinct subset of variables.

14. The non-transitory The computer-readable storage medium of claim 8, wherein the method further comprises creating a probabilistic graph data set by substituting a distinct set of alternative values for each variable in the incomplete data graph set, wherein each set of alternative values comprises at least one alternative value selected from the set of alternative values and a pre-determined probability associated with each alternative value in that set of alternative values.

15. A method for querying incomplete and uncertain information in graph data, the method comprising:

using a computing system comprising one or more processors running a computer application to;

create an incomplete graph data set comprising the plurality of graphs by inserting a variable into each blank subject node, each blank predicate and each blank object node in each graph within the plurality of graphs; and

create an uncertain graph data set from the incomplete data graph set by substituting alternative values for all variables in the incomplete data graph, wherein each variable is replaced by a given group of alternative values, each group of alternative values selected from a set of alternative values comprising a union of all subsets of a set of all uniform resource identifiers in the received graph data and all subsets of a set of all literals in the received graph data;

receiving a query from a user over graph data comprising a plurality of graphs, each graph comprising a subject node, an object node and a predicate extending from the subject node to the object node, each subject node comprising a uniform resource identifier or a blank subject node, each predicate comprising a uniform resource identifier or a blank predicate and each object node comprising a uniform resource identifier, a literal or a blank object node;

identifying certain answers to the query over the graph data, each certain answer comprising a certain value obtained from a given graph in the plurality of graphs that is equivalent for any alternative value of at least one of the subject node, the object node and the predicate of that given graph;

identifying potential answers to the query over the graph data by processing the query over the incomplete data set, each potential answer comprising two or more potential values for at least one of the subject node, the object node and the predicate from a given graph;

identifying certain potential answers to the query over the graph data using the uncertain graph data set, each certain potential answer having a number of potential values below a prescribed threshold; and

communicating the certain answers and the certain potential answers to the user in response to the query.

16. The method of claim 15, wherein:

the step of receiving the query from the user further comprises receiving a user-defined certainty threshold in combination with the query, the user-defined certainty threshold comprising a maximum amount of acceptable uncertainty in any given query answer; and

the method further comprises calculating the prescribed threshold based upon the user-defined certainty threshold.

17. The method of claim 15, wherein the step of identifying potential answers to the query further comprises processing the query over the incomplete data set to identify the potential answers, each potential answer comprising a variable in a given graph in at least one of the subject node, the object node and the predicate of that given graph that can yield the two or more potential values.

18. The method of claim 15, wherein the step of identifying the certain potential answers to the query further comprises evaluating the variable associated with each potential answer using the uncertain graph data set to identify variables having the number of potential values below the prescribed threshold.

19. A non-transitory computer-readable storage medium containing a computer-readable code that when read by a computer causes the computer to perform a method for querying incomplete and uncertain information in graph data, the method comprising:

creating an incomplete graph data set comprising the plurality of graphs by inserting a variable into each blank subject node, each blank predicate and each blank object node in each graph within the plurality of graphs;

creating an uncertain graph data set from the incomplete data graph set by substituting alternative values for all variables in the incomplete data graph, wherein each variable is replaced by a given group of alternative values, each group of alternative values selected from a set of alternative values comprising a union of all subsets of a set of all uniform resource identifiers in the received graph data and all subsets of a set of all literals in the received graph data;

receiving a query from a user over graph data comprising a plurality of graphs, each graph comprising a subject node, an object node and a predicate extending from the subject node to the object node, each subject node comprising a uniform resource identifier or a blank subject node, each predicate comprising a uniform resource identifier or a blank predicate and each object node comprising a uniform resource identifier, a literal or a blank object node;

identifying certain answers to the query over the graph data, each certain answer comprising a certain value obtained from a given graph in the plurality of graphs that is equivalent for any alternative value of at least one of the subject node, the object node and the predicate of that given graph;

identifying potential answers to the query over the graph data by processing the query over the incomplete data set, each potential answer comprising two or more potential values for at least one of the subject node, the object node and the predicate from a given graph;

identifying certain potential answers to the query over the graph data using the uncertain graph data set, each certain potential answer having a number of potential values below a prescribed threshold; and

communicating the certain answers and the certain potential answers to the user in response to the query.

20. The non-transitory computer-readable storage medium of claim 19, wherein:

the step of receiving the query from the user further comprises receiving a user-defined certainty threshold in combination with the query, the user-defined certainty threshold comprising a maximum amount of acceptable uncertainty in any given query answer; and

the method further comprises calculating the prescribed threshold based upon the user-defined certainty threshold.

21. The non-transitory computer-readable storage medium of claim 19, wherein

the step of identifying potential answers to the query further comprises processing the query over the incomplete data set to identify the potential answers, each potential answer comprising a variable in a given graph in at least one of the subject node, the object node and the predicate of that given graph that can yield the two or more potential values.

22. The non-transitory computer-readable storage medium of claim 21, wherein:

the method further comprises creating an uncertain graph data set by substituting alternative values for all variables in the incomplete data graph, wherein each variable is replaced by a given group of alternative values, each group of alternative values selected from a set of alternative values comprising a union of all subsets of a set of all uniform resource identifiers in the received graph data and all subsets of a set of all literals in the received graph data; and

the step of identifying the certain potential answers to the query further comprises evaluating the variable associated with each potential answer using the uncertain graph data set to identify variables having the number of potential values below the prescribed threshold.