Completion of partially specified paths

• US 7,945,559 B2
• Filed: 03/22/2006
• Issued: 05/17/2011
• Est. Priority Date: 03/22/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hays, Christopher Alan
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Moser; Bruce M
• Application Number:
  US11/386,298
• Publication Number:
  US 20070226337A1
• Time in Patent Office: 1,882 Days
• Field of Search: 707/2, 707/3, 707/4, 707/999.002, 707/999.003, 707/999.004, 707/716, 707/718, 707/714
• US Class Current: 707/714
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/2428 Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence

Abstract

Mechanisms are provided for completing partially specified paths. For example, users can partially specify paths by specifying some preferred entities and roles along the paths so that these paths have to incorporate these preferred entities and roles. From then, queries can automatically complete the paths, unless more specification information is needed. In completing these paths, numerous restrictions can be used, such as a role and its inverse cannot be used in a path, and no role may be traversed more than once in a path.

Claims

1. A computing system for creating at least one fully specified query path from a partially specified query path, comprising:

a relational database storing a source entity, wherein the source entity corresponds to the starting point of the partially specified query path, wherein the partially specified query path comprises a plurality of entities and roles and a target entity, wherein the target entity corresponds to the ending point of the partially specified query path, wherein the source entity and the target entity also correspond to the starting point and the ending point of the at least one fully specified query path; and

a processor programming to provide a first restriction for determining the at least one fully specified query path, wherein the first restriction disallows the use of at least one role and the inverse of the at least one role in between the source entity and the target entity and a second restriction for determining the at least one fully specified query path, wherein the second restriction disallows using the at least one role at least twice in between the source entity and the target entity,

wherein said processor further specifies at least one entity in the partially specified query path as a preferred entity through which the at least one fully specified query path should pass, wherein a combination of the preferred entity, the first restriction, and the second restriction determine the validity of the at least one fully specified query path, whereby upon a determination of the validity, the at least one fully specified query path is completed from the partially specified query path.

2. The system according to claim 1, further comprising at least one role in the partially specified query path that has been specified as a preferred role through which the at least one fully specified query path should pass, wherein the preferred role functions together with the combination of the preferred entity, the first restriction, and the second restriction in order to determine the validity of the at least one fully specified query path.

3. The system according to claim 1, wherein the at least one entity in the partially specified query path is specified as a preferred entity by a user of the system.

4. The system according to claim 3, wherein the at least one entity is specified by the user via a user interface.

5. The system according to claim 1, wherein the determination of the validity of the at least one fully specified query path is performed at query execution time.

6. The system according to claim 1, wherein the at least one fully specified query path is completed automatically.

7. The system according to claim 1, wherein the at least one fully specified query path is completed with input from a user.

8. A computer-implemented method for completing a partially specified query path, comprising:

the computer providing a first restriction for determining at least one query path from the partially specified query path, wherein the first restriction disallows the use of at least one role and the inverse of the at least one role in the at least one query path;

the computer providing a second restriction for determining the at least one query path, wherein the second restriction disallows using the at least one role at least twice in the at least one query path;

the computer making a determination regarding the validity of the at least one query path using at least one entity in the at least one query path that has been specified as a preferred entity through which the at least one query path passes, wherein the at least two of the preferred entity, the first restriction, and the second restriction are used in making a determination regarding the validity of the at least one query path; and

the computer designating a final query path from the at least one query path.

9. The method according to claim 8, further comprising following the determination, completing the at least one query path with user input.

10. The method according to claim 9, further comprising providing a user interface for the user input.

11. The method according to claim 8, further comprising following the determination, completing the at least one query path automatically.

12. The method according to claim 8, wherein the determination regarding the validity of the at least one query path is performed at query-execution time.

13. The method according to claim 8, further comprising using at least one role in the query path that has been specified as a preferred role through which the at least one query path passes.

14. The method according to claim 8, further comprising providing a third restriction that is based on changes in cardinality between any two entities in the partially specified query path.

15. A computer readable storage medium having tangible executable instructions stored thereon that when executed by a processor cause said processor to implement a method for completing at least one partially specified query path, said instructions comprising:

instructions for a first restriction functionality that determines at least one query path from the at least one partially specified query path, wherein the first restriction disallows the use of at least one role and the inverse of the at least one role in the at least one query path;

instructions for a second restriction functionality that determines the at least one query path from the at least one partially specified query path, wherein the second restriction disallows using the at least one role at least twice in the at least one query path;

instructions for.providing an option for selecting a preferred entity through which the at least one query path is fully completed; and

instructions for making a determination regarding the validity of at least one fully completed query path that is based on the at least one query path, wherein the determination is made based on the first restriction, the second restriction, and the preferred entity.

16. The computer readable storage medium according to claim 15, wherein the selecting of the preferred entity is made by a user.

17. The computer readable storage medium according to claim 15, wherein the option is provided through a user interface.

18. The computer readable storage medium according to claim 15, further comprising instructions for providing an option for selecting a preferred role through which the at least one query path passes.

19. The computer readable storage medium according to claim 15, wherein making the determination is performed at query-execution time.

20. The computer readable storage medium according to claim 15, further comprising instructions for initializing a third restriction that is based on changes in cardinality between any two entities in the at least one query path.