Efficient path-based operations while searching across versions in a repository

• US 8,015,165 B2
• Filed: 12/14/2005
• Issued: 09/06/2011
• Est. Priority Date: 12/14/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Baby, Thomas, Idicula, Sam, Murthy, Ravi, Agarwal, Nipun
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Badawi; Sherief
• Application Number:
  US11/304,414
• Publication Number:
  US 20070136382A1
• Time in Patent Office: 2,092 Days
• Field of Search: 711/118, 707/4, 707/2, 707/1, 707/101, 707/203, 707/3, 707/695, 707/638, 707/999.203, 707/999.003, 707/806, 705/14, 717/100, 717/170
• US Class Current: 707/695
• CPC Class Codes: G06F 16/192 Implementing virtual folder structures
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries

Abstract

A technique and mechanism for efficiently searching across multiple versions of a resource is provided. New operators are provided that take into account the versions of a particular resource. The query engine evaluates the new operators using either an index-based approach or a functional approach. Under an index-based implementation, a hierarchical index is traversed to find a particular resource (or resources) associated with a specified path and the version history identifier associated with the particular resource(s). A version history table containing references to all versions of the particular resource(s) are then obtained. Under the functional implementation, a link table, which contains all paths in a user'"'"'s workspace, is examined to determine whether the version history identifier of a particular resource matches a version history identifier of a resource specified in the link table and whether the path to the resource in the link table is related to the path specified.

Claims

1. A method comprising the steps of:

receiving a database statement that specifies a particular path and one or more conditions relating to either content of one or more resources or metadata associated with the one or more resources; and

in response to receiving the database statement;

identifying a first set of versions, of one or more versioned resources, that satisfy the one or more conditions in the database statement;

determining, from among the first set of versions, a second set of one or more versions by determining which versions of the first set of versions are versions of any versioned resource that has any version that satisfies the particular path;

wherein the second set of one or more versions includes a particular version of a particular versioned resource;

wherein a path that identifies a hierarchical location of the particular version does not satisfy the particular path;

wherein a version of the particular versioned resource other than the particular version satisfies the particular path;

generating, based on the second set of one or more versions, a result of the database statement;

wherein the steps are performed on one or more computing devices.

2. The method of claim 1, wherein determining which versions of the first set of versions are versions of any versioned resource that has any version that satisfies the particular path includes:

for each version in the first set of versions,

selecting a row in a link table, wherein the row references a versioned resource and the versioned resource is associated with the same version history identifier as said each version;

using the link table, constructing a path, associated with the versioned resource, from child node to parent node, wherein the constructed path comprises a set of nodes; and

determining whether the constructed path satisfies the particular path.

3. The method of claim 2, further comprising:

when the constructed path satisfies the particular path, returning an indication that said each version is associated with the particular path; and

when the constructed path does not satisfy the particular path, returning an indication that said each version is not associated with the particular path.

4. The method of claim 2, wherein the constructed path satisfies the particular path if the constructed path is the same as the particular path.

5. The method of claim 2, wherein the constructed path satisfies the particular path if the constructed path is within a subtree identified by the particular path.

6. A method comprising the steps of:

receiving a database statement that specifies a particular path and does not specify any version information; and

in response to receiving the database statement;

determining that at least a first path, satisfies the particular path, wherein the first path identifies a first hierarchical location in a first hierarchy,

determining that a particular version of a particular versioned resource resides at the first hierarchical location,

after determining that the particular version resides at the first hierarchical location, searching for other versions of the particular versioned resource,

as a result of said searching, identifying a plurality of versions of the particular versioned resource, wherein each of the plurality of versions (a) is different than the particular version and (b) resides at a hierarchical location that is identified by a path that does not satisfy any path specified in the database statement, and

generating, based on the plurality of versions, results of the database statement;

wherein the steps are performed on one or more computing devices.

7. The method of claim 6, wherein:

determining that at least the first path satisfies the particular path includes using the particular path to identify, within a particular virtual workspace, the particular version of the particular versioned resource, wherein each version of the plurality of versions is associated with the same version history identifier;

searching for other versions of the particular versioned resource includes;

identifying the version history identifier associated with the particular version, and

using the version history identifier of the particular version to identify the plurality of versions, wherein each of the plurality of versions is associated with a different virtual workspace than the particular virtual workspace.

8. The method of claim 7, wherein using the particular path to identify the particular version of the particular versioned resource includes:

traversing a hierarchical index that is based on a plurality of paths in the repository; and

identifying a versioned resource, in the hierarchical index, that satisfies the particular path.

9. The method of claim 7, wherein using the version history identifier of the particular version to identify the plurality of versions includes:

identifying a resource identifier for each version of the plurality of versions;

returning each of the identified resource identifiers.

10. The method of claim 7, wherein using the version history identifier of the particular version to identify the plurality of versions includes:

based on the version history identifier, accessing a table, wherein the table maintains a resource identifier for each version of the plurality of versions; and

returning each of the resource identifiers.

11. The method of claim 7, wherein the particular path identifies the particular version.

12. The method of claim 7, wherein the particular path identifies the root of a particular subtree in the repository.

13. The method of claim 7, wherein each version of the plurality of versions is identified by a different path.

14. The method of claim 6, wherein:

the first hierarchy corresponds to a first virtual workspace; and

the path associated with each version of the plurality of versions identifies a hierarchical location of said each version in a hierarchy that corresponds to a virtual workspace that is different than the first virtual workspace.

15. The method of claim 6, wherein:

the database statement also includes one or more conditions that are different than the particular path;

the method further comprises, after identifying the plurality of versions of the particular versioned resource, determining which versions of the plurality of versions satisfy the one or more other conditions.

16. The method of claim 6, wherein:

determining that the particular version resides at the first hierarchical location includes determining that a first version of each versioned resource of a plurality of versioned resources reside at the first hierarchical location;

searching for other versions of the particular versioned resource includes searching, for each version of each versioned resource of said plurality of versioned resources, for other versions of said each versioned resource;

identifying the plurality of versions of the particular versioned resource includes identifying, for each versioned resource of the plurality of versioned resources, a certain plurality of versions of said each versioned resource, wherein each version of the certain plurality of versions of said each versioned resource (a) is different than said first version of said each versioned resource and (b) resides at a hierarchical location that does not satisfy any path specified in the database statement; and

generating results of the database statement includes generating said results based on the certain plurality of versions of each versioned resource of the plurality of versioned resources.

17. One or more storage media storing instructions which, when executed by one or more processors, cause:

receiving a database statement that specifies a particular path and does not specify any version information; and

in response to receiving the database statement;

determining that at least a first path, satisfies the particular path, wherein the first path identifies a first hierarchical location a first hierarchy,

determining that a particular version of a particular versioned resource resides at a first hierarchical location,

after determining that the particular version resides at the first hierarchical location, searching for other versions of the particular versioned resource,

as a result of said searching, identifying a plurality of versions of the particular versioned resource, wherein each of the plurality of versions (a) is different than the particular version and (b) resides at a hierarchical location that is identified by a path that does not satisfy any path specified in the database statement, and

generating, based on the plurality of versions, results of the database statement.

18. The one or more storage media of claim 17, wherein:

the first hierarchy corresponds to a first virtual workspace; and

the path associated with each version of the plurality of versions identifies a hierarchical location of said each version in a hierarchy that corresponds to a virtual workspace that is different than the first virtual workspace.

19. The one or more storage media of claim 17, wherein:

the database statement also includes one or more conditions that are different than the particular path; and

the instructions, when executed by the one or more processors, further cause, after identifying the plurality of versions, determining which versions of the one or more versions satisfy the one or more other conditions.

20. The one or more storage media of claim 17, wherein identifying the one or more versions includes:

determining that at least the first path satisfies the particular path includes using the particular path to identify, within a particular virtual workspace, the particular version of the particular versioned resource, wherein each version of the plurality of versions is associated with the same version history identifier;

searching for other versions of the particular versioned resource includes;

identifying the version history identifier associated with the particular version, and

using the version history identifier of the particular version to identify the plurality of versions, wherein each of the plurality of versions is associated with a different virtual workspace than the particular virtual workspace.

21. The one or more storage media of claim 20, wherein using the particular path to identify the particular version of the particular versioned resource includes:

traversing a hierarchical index that is based on a plurality of paths in the repository; and

identifying a versioned resource, in the hierarchical index, that satisfies the particular path.

22. The one or more storage media of claim 20, wherein using the version history identifier of the particular version to identify the plurality of versions includes:

identifying a resource identifier for each version of the plurality of versions;

returning each of the identified resource identifiers.

23. The one or more storage media of claim 20, wherein using the version history identifier of the particular version to identify the plurality of versions includes:

based on the version history identifier, accessing a table, wherein the table maintains a resource identifier for each version of the plurality of versions; and

returning each of the resource identifiers.

24. The one or more storage media of claim 20, wherein the particular path identifies the particular version.

25. The one or more storage media of claim 20, wherein the particular path identifies the root of a particular subtree in the repository.

26. The one or more storage media of claim 20, wherein each version of the plurality of versions is identified by a different path.

27. The one or more storage media of claim 17, wherein:

determining that the particular version resides at the first hierarchical location includes determining that a first version of each versioned resource of a plurality of versioned resources reside at the first hierarchical location;

searching for other versions of the particular versioned resource includes searching, for each version of each versioned resource of said plurality of versioned resources, for other versions of said each versioned resource;

identifying the plurality of versions of the particular versioned resource includes identifying, for each versioned resource of the plurality of versioned resources, a certain plurality of versions of said each versioned resource, wherein each version of the certain plurality of versions of said each versioned resource (a) is different than said first version of said each versioned resource and (b) resides at a hierarchical location that does not satisfy any path specified in the database statement; and

generating results of the database statement includes generating said results based on the certain plurality of versions of each versioned resource of the plurality of versioned resources.

28. One or more storage media storing instructions which, when executed by one or more processors, cause:

receiving a database statement that specifies a particular path and one or more conditions relating to either content of one or more resources or metadata associated with the one or more resources; and

in response to receiving the database statement;

identifying a first set of versions, of one or more versioned resources, that satisfy the one or more conditions in the database statement;

determining, from among the first set of versions, a second set of one or more versions by determining which versions of the first set of versions are versions of any versioned resource that has any version that satisfies the particular path;

wherein the second set of one or more versions includes a particular version of a particular versioned resource;

wherein a path that identifies a hierarchical location of the particular version does not satisfy the particular path;

wherein a version of the particular versioned resource other than the particular version satisfies the particular path;

generating, based on the second set of one or more versions, a result of the database statement.

29. The one or more storage media of claim 28, wherein determining which versions of the first set of versions are versions of any versioned resource that has any version that satisfies the particular path includes:

for each version in the first set of versions,

selecting a row in a link table, wherein the row references a versioned resource and the versioned resource is associated with the same version history identifier as said each version;

using the link table, constructing a path, associated with the versioned resource, from child node to parent node, wherein the constructed path comprises a set of nodes; and

determining whether the constructed path satisfies the particular path.

30. The one or more storage media of claim 29, wherein the instructions, when executed by the one or more processors, further cause:

when the constructed path satisfies the particular path, returning an indication that said each version is associated with the particular path; and

when the constructed path does not satisfy the particular path, returning an indication that said each version is not associated with the particular path.

31. The one or more storage media of claim 29, wherein the constructed path satisfies the particular path if the constructed path is the same as the particular path.

32. The one or more storage media of claim 29, wherein the constructed path satisfies the particular path if the constructed path is within a subtree identified by the particular path.