Relation path viability prediction
First Claim
1. In an information system comprising objects, instances of said objects and relationships between at least some of said objects and said instances of said objects, a method for predicting whether a query will produce a result, the method comprising the steps of:
- providing an instance-to-object bitmap which indicates whether instances of objects are related to other objects; and
accessing the bitmap to determine if the query will produce a result.
4 Assignments
0 Petitions
Accused Products
Abstract
There is provided a process for predicting whether a query will produce a result in an information system formed of objects having different instances and relations between the objects. An instance-to-object bitmap is computed off-line, before queries are generated by a user: the bitmap is used to represent the existence of a relation path from instances to the other objects of a database. When a query is generated, the bitmap is accessed to predict whether there exists a relation from the instance to the object, that is whether the query will issue a result. The process makes it possible for a user to abort queries without consuming run-time. It also makes it possible to guide users through navigation of a Webpage or the like, by suggesting relations that will produce results.
-
Citations
23 Claims
-
1. In an information system comprising objects, instances of said objects and relationships between at least some of said objects and said instances of said objects, a method for predicting whether a query will produce a result, the method comprising the steps of:
-
providing an instance-to-object bitmap which indicates whether instances of objects are related to other objects; and
accessing the bitmap to determine if the query will produce a result. - View Dependent Claims (2, 3, 4, 5, 6)
computing paths from instances to neighboring objects by determining a path from an instance in an object to an instance in a neighboring object; and
computing a path from an instance to a non-neighboring object by merging a path from an instance in a first object to an instance in a second object with a computed path from said instance in said second object to said non-neighboring object.
-
-
3. The method of claim 2, wherein the step of computing a path from an instance to a non-neighboring object is repeated.
-
4. The method of claim 2, wherein the step of computing a path from an instance to a non-neighboring object is repeated until relation paths of a predetermined length are computed.
-
5. The method of claim 3, wherein the step of providing an instance-to-object bitmap comprises providing an instance-to-object bitmap which indicates whether each instance of an object is related to all other objects by a relation path having a length equal to or lower than a predetermined length.
-
6. The method of claim 1, wherein the step of providing comprises providing an instance-to-object bitmap indicating whether each instance of an object is related to all other objects by a relation path having a length equal to or lower than a predetermined length.
- 7. An information system comprising objects, instances of said objects, relationships between at least some of said objects and said instances of said objects, and an instance-to-object bitmap indicating whether instances of objects are related to other objects.
-
13. In an information system comprising objects, instances of said objects and relationships between at least some of said objects and said instances of said objects, a method for generating an instance-to-object bitmap, comprising the steps of:
-
computing paths from instances to neighboring objects by determining a path from an instance in an object to an instance in a neighboring object; and
computing a path from an instance to a non-neighboring object by merging a path from an instance in a first object to an instance in a second object with a computed path from said instance in said second object to said non-neighboring object. - View Dependent Claims (14, 15, 16)
-
-
17. In an information system comprising objects, instances of said objects and relationships between at least some of said objects and said instances of said objects, a method for predicting a likelihood of whether a query will produce a result, the method comprising the steps of:
-
providing an object-to-object probability matrix, which indicates a likelihood that an instance of an object is related to another object; and
accessing the probability matrix to determine a likelihood that the query will produce a result. - View Dependent Claims (18, 19, 20, 21, 22, 23)
for each object, computing a probability that an instance in an object is related to a neighboring object; and
computing probabilities that instances in objects are related to non-neighboring objects using the probabilities computed in the previous step.
-
-
19. The method of claim 18, wherein the step of computing a probability that an instance in an object is related to a neighboring object comprises:
-
determining a number of instances in a first object related to a neighboring second object; and
calculating the probability that an instance in said first object is related to said neighboring second object by dividing the number of instances in said first object related to said neighboring second object by a total number of instances in said first object.
-
-
20. The method of claim 19, wherein the step of computing probabilities that instances in objects are related to non-neighboring objects comprises:
-
computing a first probability that an instance in a first object is related to a second object, said second object neighboring said first object;
computing a second probability that an instance in said second object is related to a third object, said third object neighboring said second object; and
computing a third probability that said first object is related to said third object, said third object not neighboring said first object, by multiplying said first probability by said second probability.
-
-
21. The method of claim 19, wherein the step of determining a number of instances in a first object that are related to a second object comprises using an instance-to-object bitmap to determine which instances of said first object are related to said second object.
-
22. The method of claim 21, wherein said instance-to-object bitmap is generated by:
-
computing paths from instances to neighboring objects by determining a path from an instance in an object to an instance in a neighboring object; and
computing a path from an instance to a non-neighboring object by merging a path from an instance in a first object to an instance in a second object with a computed path from said instance in said second object to said non-neighboring object.
-
-
23. The method of claim 22, wherein the step of computing a path from an instance to a non-neighboring object is repeated.
Specification