Method and apparatus for safe ontology reasoning

Abstract

The present invention is a method and apparatus for safe ontology reasoning. In one embodiment, a method for building safe sub-ontology that includes one or more elements of a given ontology includes designating at least one the elements as a sensitive element, where a sensitive element is an element not to be revealed. The method then designates a safe sub-ontology such that the safe sub-ontology does not include any elements that, alone or in combination, allow inference of a sensitive element, in accordance with one or more given inference rules. In another embodiment, a method for building a potential sub-ontology includes designating at least one of the elements as a sensitive element and including a maximal number of the elements in the potential sub-ontology, wherein the maximal number includes the greatest number of elements that can be revealed, cumulatively, without allowing inference of a sensitive element, in accordance with one or more given inference rules.

1 . A method for building a safe sub-ontology comprising one or more elements of a given ontology, the elements comprising one or more individuals, one or more relationships defined between the one or more individuals and one or more pieces of metadata relating to the one or more individuals and the one or more relationships, the method comprising: 
 designating at least one of said one or more elements as a sensitive element, where a sensitive element is an element not to be revealed;    designating at least one of said one or more elements as a potential safe sub-ontology such that said potential safe sub-ontology does not include any elements that, alone or in combination, allow inference of a sensitive element, in accordance with one or more given inference rules;    verifying that said potential safe sub-ontology does not include any elements that, alone or in combination, allow inference of a sensitive element, in accordance with said one or more given inference rules; and    storing said potential safe sub-ontology as the safe sub-ontology, if said verifying concludes that said potential safe sub-ontology does not include any elements that, alone or in combination, allow inference of a sensitive element, in accordance with said one or more given inference rules.    
   
   
       2 . (canceled)  
   
   
       3 . The method of  claim 1 , wherein said verifying comprises: 
 defining a first subset of said one or more elements, said first subset comprising said least one of said one or more elements that Is designated as a sensitive element;    defining a second subset of said one or more elements, where said second subset comprises a set of elements to be tested as said potential safe sub-ontology;    building a closure of said second subset; and    determining whether said closure intersects with said first subset.    
   
   
       4 . The method of  claim 3 , further comprising: 
 concluding that said potential safe sub-ontology is safe if said closure does not intersect with said first subset; and    concluding that said potential safe sub-ontology is not safe if said closure intersects with said first subset.    
   
   
       5 . The method of  claim 1 , wherein said ontology comprises: 
 a finite set of concepts;    a finite set of individuals;    a finite set of relationships; and    a finite set of metadata.    
   
   
       6 . The method of  claim 1 , further comprising the step of: 
 optimizing said potential safe sub-ontology with respect to a function of said potential safe sub-ontology, while maintaining said safe status.    
   
   
       7 . The method of  claim 6 , wherein said function is a counting function.  
   
   
       8 . The method of  claim 6 , wherein said including comprises: 
 defining, for each sensitive element, a minimal set of said one or more elements that is necessary to infer said sensitive element in accordance with said one or more given inference rules;    associating each minimal set with a matroid; and    identifying a single subset of said one or more elements, where each element in said single subset is independent in each minimal set.    
   
   
       9 . The method of  claim 8 , wherein said identifying comprises: 
 defining a first intersection of all of said matroids associated with a minimal set;    reducing said first intersection to a second Intersection of a subset of said matroids;    initiating a third intersection, said third intersection being an empty intersection;    building a border graph in accordance with said third intersection; and    selecting said maximal number in accordance with said border graph.    
   
   
       10 . The method of  claim 9 , wherein said selecting comprises: 
 determining whether an augmenting tree exists in said border graph;    augmenting said third intersection with said augmenting tree, if said augmenting tree is determined to exist in said border graph; and    selecting said third intersection as said maximal number, if no augmenting tree is determined to exist in said border graph.    
   
   
       11 . The method of  claim 9 , wherein said second intersection is an intersection of three matroids.  
   
   
       12 . A computer readable medium containing an executable program for building a safe sub-ontology comprising one or more elements of a given ontology, the elements comprising one or more individuals, one or more relationships defined between the one or more individuals and one or more pieces of metadata relating to the one or more individuals and the one or more relationships, where the program performs the steps of: 
 designating at least one of said one or more elements as a sensitive element, where a sensitive element Is an element not to be revealed;    designating at least one of said one or more elements as a potential safe sub-ontology such that said potential safe sub-ontology does not include any elements that, alone or in combination, allow inference of a sensitive element, in accordance with one or more given inference rules;    verifying that said potential safe sub-ontology does not include any elements that, alone or in combination, allow inference of a sensitive element, in accordance with said one or more given inference rules; and    storing said potential safe sub-ontology as the safe sub-ontology, if said verifying concludes that said potential safe sub-ontology does not include any elements that, alone or in combination, allow inference of a sensitive element, in accordance with said one or more given inference rules.    
   
   
       13 . (canceled)  
   
   
       14 . The computer readable medium of  claim 12 , wherein said verifying comprises: 
 defining a first subset of said one or more elements, said first subset comprising said least one of said one or more elements that is designated as a sensitive element;    defining a second subset of said one or more elements, where said second subset comprises a set of elements to be tested as said potential safe sub-ontology;    building a closure of said second subset; and    determining whether said closure intersects with said first subset.    
   
   
       15 . Apparatus for building a safe sub-ontology comprising one or more elements of a given ontology, the elements comprising one or more individuals, one or more relationships defined between the one or more individuals and one or more pieces of metadata relating to the one or more individuals and the one or more relationships, said apparatus comprising: 
 means for designating at least one of said one or more elements as a sensitive element, where a sensitive element is an element not to be revealed;    means for designating at least one of said one or more elements as a potential safe sub-ontology such that said potential safe sub-ontology does not include any elements that, alone or in combination, allow inference of a sensitive element, in accordance with one or more given inference rules;    means for verifying that said potential safe sub-ontology does not include any elements that, alone or in combination, allow inference of a sensitive element, in accordance with said one or more given inference rules; and    means for storing said potential safe sub-ontology as the safe sub-ontology, if said verifying concludes that said potential safe sub-ontology does not include any elements that, alone or in combination, allow inference of a sensitive element, in accordance with said one or more given inference rules.    
   
   
       16 . A method for building a potential sub-ontology comprising one or more elements of a given ontology, the elements comprising one or more individuals, one or more relationships defined between the one or more individuals and one or more pieces of metadata relating to the one or more individuals and the one or more relationships, the method comprising 
 designating at least one of said one or more elements as a sensitive element, where a sensitive element is an element not to revealed;    including a maximal number of said one or more elements in said potential sub-ontology, wherein said maximal number is a greatest number of elements that can be revealed, cumulatively, without allowing inference of a sensitive element, in accordance with one or more given inference rules;    verifying that said potential safe sub-ontology does not include any elements that, alone or in combination, allow inference of a sensitive element, in accordance with said one or more given inference rules: and    storing said potential safe sub-ontology as a safe subontology, if said verifying concludes that said potential safe sub-ontology does not include any elements that, alone or in combination, allow inference of a sensitive element, in accordance with said one or more given inference rules.    
   
   
       17 . The method of  claim 16 , wherein said including comprises: 
 defining, for each sensitive element, a minimal set of said one or more elements that is necessary to infer said sensitive element in accordance with said one or more given inference rules;    associating each minimal set with a matroid; and    identifying a single subset of said one or more elements, where each element in said single subset is independent in each minimal set.    
   
   
       18 . The method of  claim 17 , wherein said identifying comprises: 
 defining a first intersection of all of said matroids associated with a minimal set;    reducing said first intersection to a second intersection of a subset of said matroids;    initiating a third intersection, said third intersection being an empty intersection;    building a border graph in accordance with said third intersection; and    selecting said maximal number in accordance with said border graph.    
   
   
       19 . The method of  claim 18 , wherein said selecting comprises: 
 determining whether an augmenting tree exists in said border graph;    augmenting said third intersection with said augmenting tree, if said augmenting tree is determined to exist in said border graph; and    selecting said third intersection as said maximal number, if no augmenting tree is determined to exist in said border graph.    
   
   
       20 . The method of  claim 18 , wherein, said second intersection is an intersection of three matroids.