Efficient information storage and retrieval using subgraphs

Abstract

An extended ontology may be generated from an ontology such that one or more classes of the extended ontology is associated with a marker and input data may be received. Further, based on the extended ontology and the marker, a subgraph representation of the input data may be generated, where the subgraph representation omits a piece of information included in a first graph representation of the input data, and the subgraph representation includes a plurality of acyclic subgraphs. The acyclic subgraphs may be stored in one or more databases and an acyclic subgraph of the plurality of acyclic subgraphs may be provided as an input to an executable program, where the application of rules associated with the extended ontology by the executable program causes a cyclic graph to be generated from the acyclic subgraph such that the cyclic graph comprises a piece of information omitted from the acyclic subgraph.

What is claimed is: 
     
         1 . A tangible, non-transitory, machine-readable medium storing instructions that, when executed by one or more processors, effectuate operations comprising:
 obtaining, with a computer system, a first directed graph having nodes and directed edges connecting respective pairs of the nodes, the nodes representing entities in an ontology, the edges indicating relationships between entities represented by the respective pairs of nodes, at least some of the edges indicating different types of relationships among a plurality of relationships;   obtaining, with the computer system, a set of logic rules, at least some of the logic rules indicating that a first relationship among the plurality of relationships entails a second relationship among the plurality of relationships;   forming, with the computer system, a second directed graph that consumes less memory than the first directed graph by applying the set of logic rules to the first directed graph to detect information in the first directed graph that is entailed by other information in the first directed graph, the second directed graph encoding information sufficient to re-form the first directed graph through application of the logic rules, the second directed graph omitting at least some of the information in the first directed graph that the set of logic rules indicate is entailed in other information in the second directed graph; and   storing, with the computer system, the second directed graph in memory.   
     
     
         2 . The medium of  claim 1 , the operations comprising:
 receiving the second directed graph via a network, wherein conveying the second directed graph via the network consumes less bandwidth than conveying the first directed graph via the network; and   re-forming, from the received second directed graph, at least part of the first directed graph that is omitted from the second directed graph.   
     
     
         3 . The medium of  claim 2 , wherein re-forming the at least part of the first directed graph is performed with a rules engine responsive to the a least some of the set of logic rules. 
     
     
         4 . The medium of  claim 1 , wherein:
 a first node and a second node of the first directed graph are connected by both a first edge representing the first relationship and a second edge representing the second relationship; and   forming the second directed graph comprises omitting the second edge in the second directed graph based on the at least some of the logic rules indicating that the first relationship among the plurality of relationships entails the second relationship among the plurality of relationships.   
     
     
         5 . The medium of  claim 1 , wherein:
 the first directed graph is cyclic;   the second directed graph omits at least some cycles of the first directed graph; and   pairs of nodes connected by edges in the first directed graph encode semantic triples.   
     
     
         6 . The medium of  claim 1 , the operations comprising:
 forming the second directed graph comprises losslessly compressing the first directed graph.   
     
     
         7 . The medium of  claim 1 , wherein:
 the set of logic rules comprise class logic rules, general logic rules, and specific logic rules generated from corresponding types of ontologies.   
     
     
         8 . The medium of  claim 1 , wherein the operations comprise:
 steps for reconstructing the first directed graph from the second directed graph.   
     
     
         9 . The medium of  claim 1 , wherein:
 the first directed graph is a sub-graph of a third directed graph; and   the operations comprise forming a fourth directed graph from another sub-graph of the third directed graph by omitting, in the fourth directed graph, at least some information in the another sub-graph that members of the set of rules indicate is entailed by other information in the another sub-graph.   
     
     
         10 . The medium of  claim 9 , the operations further comprising;
 determining that the sub-graph and the another sub-graph correspond to different nodes in the first directed graph each marked as persisted data.   
     
     
         11 . The medium of  claim 10 , the operations further comprising:
 designating a first class and a second class of an ontology are persisted classes in response to usage patterns of the first class and the second class; and   determining that the different nodes are members of one of the first class and the second class.   
     
     
         12 . The medium of  claim 1 , wherein the operations comprise:
 steps for decomposing or segmenting subgraphs.   
     
     
         13 . The medium of  claim 1 , wherein the operations comprise:
 steps for generating an extended ontology.   
     
     
         14 . The medium of  claim 1 , wherein the operations comprise:
 steps for providing ontology-configurable computer programs.   
     
     
         15 . The medium of  claim 1 , wherein the operations comprise:
 steps for providing supplemental functionalities for a computer program.   
     
     
         16 . The medium of  claim 1 , wherein the operations comprise:
 steps for generating a programming interface and the set of logic rules   
     
     
         17 . The medium of  claim 1 , wherein the operations comprise:
 receiving input data;   forming the first directed graph based on the input data; and   designating at least some nodes of the first directed graph as persisted data and at least some other nodes of the first directed graph as support entities.   
     
     
         18 . The medium of  claim 17 , wherein:
 forming the second directed graph comprises omitting information not designed as persisted data and embedding support entities in other nodes.   
     
     
         19 . The medium of  claim 1 , wherein:
 the first directed graph is a healthcare ontology.   
     
     
         20 . A method, comprising:
 obtaining, with a computer system, a first directed graph having nodes and directed edges connecting respective pairs of the nodes, the nodes representing entities in an ontology, the edges indicating relationships between entities represented by the respective pairs of nodes, at least some of the edges indicating different types of relationships among a plurality of relationships;   obtaining, with the computer system, a set of logic rules, at least some of the logic rules indicating that a first relationship among the plurality of relationships entails a second relationship among the plurality of relationships;   forming, with the computer system, a second directed graph that consumes less memory than the first directed graph by applying the set of logic rules to the first directed graph to detect information in the first directed graph that is entailed by other information in the first directed graph, the second directed graph encoding information sufficient to re-form the first directed graph through application of the logic rules, the second directed graph omitting at least some of the information in the first directed graph that the set of logic rules indicate is entailed in other information in the second directed graph; and   storing, with the computer system, the second directed graph in memory.