Representing Incomplete and Uncertain Information in Graph Data
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
15 Claims
-
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. - View Dependent Claims (2, 4, 5, 6, 7, 8, 9, 10)
-
3. (canceled)
-
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. - View Dependent Claims (12, 13, 14, 15)
Specification