Representing Incomplete and Uncertain Information in Graph Data

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.

1 . A system for representing and querying incomplete and uncertain information in graph data, the system comprising:
 a computing system comprising:
 a graph data input module configured to receive 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; and 
 an uncertainty and incompleteness specification module in communication with the graph data input module, the uncertainty and incompleteness specification module comprising:
 an incompleteness modeler to insert a variable into each one of a plurality of graph nodes selected from the blank subject nodes, blank predicates and blank object nodes; and 
 an uncertainty modeler to determine alternative values for the inserted variables, wherein the uncertainty modeler comprises an uncertain graph data modeler configured to generate an uncertain graph data set comprising alternative values for all inserted variables and 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 plurality of graphs received by the graph data input module. 
 
   
     
     
         2 . The system of  claim 1 , wherein the incompleteness modeler comprises an incomplete graph data modeler configured to generate an incomplete graph data set by inserting a distinct variable into each blank subject node, each blank predicate and each blank object node in each graph within the plurality of graphs received by the graph data input module. 
     
     
         3 . (canceled) 
     
     
         4 . The system of  claim 1 , wherein the system further comprises a graph storage database comprising the incomplete graph data set and the uncertain graph data set. 
     
     
         5 . The system of  claim 2 , wherein the uncertainty modeler comprises a partial uncertain graph data modeler configured to generate a partial uncertain graph data set comprising alternative values for a portion of all variables in the incomplete data graph set, wherein each variable is replaced by a given 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 plurality of graphs received by the graph data input module. 
     
     
         6 . The system of  claim 5 , wherein the partial uncertain graph data modeler is further configured to substitute alternative values only in variables located 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. 
     
     
         7 . The system of  claim 2 , wherein the uncertainty modeler comprises a probabilistic graph modeler to create a probabilistic graph data set comprising 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 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 plurality of graphs received by the graph data input module and a pre-determined probability associated with each alternative value in that set. 
     
     
         8 . The system of  claim 1 , further comprising a query processing module in communication with the uncertainty and incompleteness specification module, the query processing module configured to process user-defined queries over models generated by the incompleteness modeler and the uncertainty modeler. 
     
     
         9 . The system of  claim 8 , wherein the query processing module comprises:
 a naive evaluator to identify certain answers to the user-defined query from 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;   a potential answer evaluator to identify potential answers to the query from the graph data, each potential answer comprising two or more potential values for at least one of the subject node, the object node and the predicate of a given graph; and   a certain potential answer evaluator to identify certain potential answers to the query over the graph data, each certain potential answer having a number of potential values below a prescribed threshold.   
     
     
         10 . The system of  claim 1 , wherein the uncertainty and incompleteness specification module further comprises:
 a plurality of incompleteness modelers, each incompleteness modeler generating a distinct type of incompleteness model by inserting variables into each one of a plurality of blank subject nodes, blank predicates and blank object nodes; and   a plurality of uncertainty modelers, each uncertainty modeler generating a distinct incompleteness model comprising a distinct set of alternative values for the inserted variables in one of the incompleteness models.   
     
     
         11 . A system for representing and querying incomplete and uncertain information in graph data, the system comprising:
 a computing system comprising:
 a graph data input module configured to receive graph data comprising a plurality of graphs, each 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; and 
 an uncertainty and incompleteness specification module in communication with the graph data module, the uncertainty and incompleteness specification module comprising:
 an incompleteness modeler comprising an incomplete graph data modeler configured to generate an incomplete graph data set by inserting a distinct variable into each blank subject node, each blank predicate and each blank object node in each graph within the plurality of graphs received by the graph data input module; and 
 an uncertainty modeler comprising:
 an uncertain graph data modeler configured to generate an uncertain graph data set comprising 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 plurality of graphs received by the graph data input module; 
 a partial uncertain graph data modeler configured to generate a partial uncertain graph data set comprising alternative values for a portion of all variables in the incomplete data graph set, wherein each variable is replaced by a given group of alternative values selected from the set of alternative values; and 
 a probabilistic graph modeler to create a probabilistic graph data set comprising 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. 
 
 
   
     
     
         12 . The system of  claim 11 , wherein the system further comprises a graph storage database comprising the incomplete graph data set and the uncertain graph data set. 
     
     
         13 . The system of  claim 11 , wherein the partial uncertain graph data modeler is further configured to substitute alternative values only in variables located 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. 
     
     
         14 . The system of  claim 11 , further comprising a query processing module in communication with the uncertainty and incompleteness specification module, the query processing module configured to process user-defined queries over models generated by the incompleteness modeler and the uncertainty modeler. 
     
     
         15 . The system of  claim 14 , wherein the query processing module comprises:
 a naive evaluator to identify certain answers to the user-defined query from 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;   a potential answer evaluator to identify potential answers to the query from the graph data, each potential answer comprising two or more potential values for at least one of the subject node, the object node and the predicate of a given graph; and   a certain potential answer evaluator to identify certain potential answers to the query over the graph data, each certain potential answer having a number of potential values below a prescribed threshold.