Efficient processing of path related operations on data organized hierarchically in an RDBMS

• US 9,229,967 B2
• Filed: 02/22/2006
• Issued: 01/05/2016
• Est. Priority Date: 02/22/2006
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ge, Fei, Idicula, Sam, Jain, Namit, Agarwal, Nipun
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): NGUYEN, THU N
• Application Number:
  US11/360,792
• Publication Number:
  US 20070198545A1
• Time in Patent Office: 3,604 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees

Abstract

A mechanism is used to improve the efficiency of performing resource-to-path resolution. A hierarchical link structure contains entries and/or records (“link entries”) that each defines a parent-child link within an information hierarchy. A certain linking entry may have data that refers to another link entry representing a link to the parent—a link in which the parent is a child. This data allows resource-to-path resolutions to be performed more efficiently.

Claims

1. A computer-implemented method, comprising:

a computer system generating an information hierarchy comprising a link entry hierarchy and a node hierarchy;

wherein the link entry hierarchy is comprised of link entries, and a particular link entry in the link entry hierarchy contains a plurality of link entry identifiers;

wherein each link entry identifier of said plurality of link entry identifiers identifies a link entry that is a parent link entry of said particular link entry, the parent link entry identified by said each link entry identifier being different than said particular link entry;

wherein the node hierarchy is comprised of nodes, and a child node of the node hierarchy is associated with said particular link entry, wherein said particular link entry defines a link from a parent node to the child node;

and

wherein a parent link entry of the particular link entry defines a link between a grandparent node and the parent node, wherein the grandparent node is a parent of the parent node in the node hierarchy.

2. The method of claim 1, wherein the plurality of link entry identifiers includes at least two identifiers that each identify a parent link entry.

3. The method of claim 1, wherein each link entry of said link entries includes access control data describing access privileges for accessing a node associated with said each link entry.

4. The method of claim 1, wherein each link entry of said link entries includes access control data describing access privileges for accessing the child node associated with said each link entry.

5. The method of claim 1, wherein said information hierarchy is comprised of resources stored within a database managed by a database server.

6. The method of claim 5, wherein said database server adds or removes a link entry from said link entry hierarchy in response to said database server adding or removing a resource from said node hierarchy.

7. The method of claim 1, wherein:

said link entry hierarchy is a relational table;

said link entries are rows within said relational table; and

said plurality of link entry identifiers are row ids referring to a row in said relational table.

8. A computer-implemented method for performing a resource-to-path resolution, comprising:

a computer system performing the resource-to-path resolution using

an information hierarchy comprising a link entry hierarchy and a separate node hierarchy;

wherein the link entry hierarchy is comprised of link entries, and a particular link entry in the link entry hierarchy contains a set of one or more link entry identifiers;

wherein each link entry identifier of said set of one or more link entry identifiers identifies a link entry that is a parent link entry of said particular link entry, the parent link entry identified by said each link entry identifier being different than said particular link entry;

wherein the node hierarchy is comprised of nodes, and a child node of the node hierarchy is associated with said particular link entry, wherein said particular link entry defines a link from a parent node to the child node; and

wherein a parent link entry of the particular link entry defines a link between a grandparent node and the parent node, wherein the grandparent node is a parent of the parent node in the node hierarchy; and

wherein said performing the resource-to-path resolution includes;

accessing the particular link entry, and

using the set of one or more link entry identifiers in the particular link entry to access a particular parent link entry.

9. The method of claim 8, wherein the set of one or more link entry identifiers includes at least two identifiers that each identify a parent link entry.

10. The method of claim 8, wherein each link entry of said link entries includes access control data describing access privileges for accessing a node associated with said each link entry.

11. The method of claim 8, wherein each link entry of said link entries includes access control data describing access privileges for accessing the child node associated with said each link entry.

12. The method of claim 8, wherein said performing the resource-to-path resolution includes examining access control data within either said particular link entry or said particular parent link entry to determine access control privileges.

13. The method of claim 8, wherein the resource-to-path resolution is performed to evaluate an operator referenced in a statement being computed by a database server, said statement conforming to a database language.

14. A non-transitory computer-readable storage medium that stores an:

an information hierarchy comprising a link entry hierarchy and a separate node hierarchy;

wherein the link entry hierarchy is comprised of link entries, and a particular link entry in the link entry hierarchy contains a plurality of link entry identifiers;

wherein each link entry identifier of said plurality of link entry identifiers identifies a link entry that is a parent link entry of said particular link entry, the parent link entry identified by said each link entry identifier being different than said particular link entry;

wherein the node hierarchy is comprised of nodes, and a child node of the node hierarchy is associated with said particular link entry, wherein said particular link entry defines a link from a parent node to the child node; and

wherein a parent link entry of the particular link entry defines a link between a grandparent node and the parent node, wherein the grandparent node is a parent of the parent node in the node hierarchy.

15. the non-transitory computer-readable storage medium of claim 14, wherein the one or more link entry identifiers includes at least two identifiers that each identify a parent link entry.

16. the non-transitory computer-readable storage medium of claim 14, wherein each link entry of said link entries includes access control data describing access privileges for accessing a node associated with said each link entry.

17. the non-transitory computer-readable storage medium of claim 14, wherein each link entry of said link entries includes access control data describing access privileges for accessing the child node associated with said each link entry.

18. the non-transitory computer-readable storage medium of claim 14, wherein:

said link entry hierarchy is a relational table;

said link entries are rows within said relational table; and

said one or more link entry identifiers are row ids referring to a row in said relational table.

19. A non-transitory computer-readable storage medium storing sequences of instructions, that when executed by one or more processors, cause:

performing the resource-to-path resolution using an information hierarchy comprising a link entry hierarchy and a separate node hierarchy;

wherein the link entry hierarchy is comprised of link entries, and a particular link entry in the link entry hierarchy contains a set of one or more link entry identifiers;

wherein each link entry identifier of said set of one or more link entry identifiers identifies a link entry that is a parent link entry of said particular link entry, the parent link entry identified by said each link entry identifier being different than said particular link entry;

wherein the node hierarchy is comprised of nodes, and a child node of the node hierarchy is associated with said particular link entry, wherein said particular link entry defines a link from a parent node to the child node; and

wherein a parent link entry of the particular link entry defines a link between a grandparent node and the parent node, wherein the grandparent node is a parent of the parent node in the node hierarchy;

wherein said performing the resource-to-path resolution includes;

accessing the particular link entry, and

using the set of one or more link entry identifiers in the particular link entry to access a particular parent link entry.

20. the non-transitory computer-readable storage medium of claim 19, wherein the set of one or more link entry identifiers includes at least two identifiers that each identify a parent link entry.

21. the non-transitory computer-readable storage medium of claim 19, wherein each link entry of said link entries includes access control data describing access privileges for accessing a node associated with said each link entry.

22. the non-transitory computer-readable storage medium of claim 19, wherein each link entry of said link entries includes access control data describing access privileges for accessing the child node associated with said each link entry.

23. The non-transitory computer-readable storage medium of claim 19, the sequences of instructions including instructions that when executed by said one or processors, cause performing the resource-to-path resolution to include examining access control data within either said particular link entry or said link entry to determine access control privileges.

24. The non-transitory computer-readable storage medium of claim 19, the sequences of instructions including instructions that when executed by said one or more processors, cause the resource-to-path resolution to be performed to evaluate an operator referenced in a statement being computed by a database server, said statement conforming to a database language.

25. A computer-implemented method for performing a resource-to-path resolution, comprising:

a computer system performing the resource-to-path resolution using an information hierarchy comprising a link entry hierarchy and a separate node hierarchy;

wherein the link entry hierarchy is comprised of link entries, and a particular link entry in the link entry hierarchy contains a plurality of link entry identifiers;

wherein each link entry identifier of said plurality of link entry identifiers identifies a link entry that is a parent link entry of said particular link entry, the parent link entry identified by said each link entry identifier being different than said particular link entry;

wherein the node hierarchy is comprised of nodes, and a child node of the node hierarchy is associated with said particular link entry, wherein said particular link entry defines a link from a parent node to the child node; and

wherein a parent link entry of the particular link entry defines a link between a grandparent node and the parent node, wherein the grandparent node is a parent of the parent node in the node hierarchy;

wherein said performing the resource-to-path resolution includes;

accessing the particular link entry, and

using the plurality of link entry identifiers in the particular link entry to access a parent link entry.

26. A non-transitory computer-readable storage medium storing sequences of instructions, that when executed by one or more processors, cause:

performing the resource-to-path resolution using an information hierarchy comprising a link entry hierarchy and a separate node hierarchy;

wherein the link entry hierarchy is comprised of link entries, and a particular link entry in the link entry hierarchy contains a plurality of link entry identifiers;

wherein each link entry identifier identifies a link entry that is a parent link entry of said particular link entry, the parent link entry identified by said each link entry identifier being different than said particular link entry;

wherein the node hierarchy is comprised of nodes, and a child node of the node hierarchy is associated with said particular link entry, wherein said particular link entry defines a link from a parent node to the child node; and

wherein a parent link entry of the particular link entry defines a link between a grandparent node and the parent node, wherein the grandparent node is a parent of the parent node in the node hierarchy;

wherein said performing the resource-to-path resolution includes;

accessing the particular link entry, and

using the plurality of link entry identifiers in the particular link entry to access a parent link entry.

27. A non-transitory computer-readable storage medium storing sequences of instructions, that when executed by one or more processors, cause:

generating an information hierarchy comprising a link entry hierarchy and a separate node hierarchy;

wherein the link entry hierarchy is comprised of link entries, and a particular link entry in the link entry hierarchy contains a plurality of link entry identifiers;

wherein each link entry identifier of said plurality of link entry identifiers identifies a link entry that is a parent link entry of said particular link entry, the parent link entry identified by said each link entry identifier being different than said particular link entry;

wherein the node hierarchy is comprised of nodes, and a child node of the node hierarchy is associated with said particular link entry, wherein said particular link entry defines a link from a parent node to the child node; and

wherein a parent link entry of the particular link entry defines a link between a grandparent node and the parent node, wherein the grandparent node is a parent of the parent node in the node hierarchy.

28. the non-transitory computer-readable storage medium of claim 27, wherein the plurality of link entry identifiers includes at least two identifiers that each identify a parent link entry.

29. the non-transitory computer-readable storage medium of claim 27, wherein each link entry of said link entries includes access control data describing access privileges for accessing a node associated with said each link entry.

30. the non-transitory computer-readable storage medium of claim 27, wherein each link entry of said link entries includes access control data describing access privileges for accessing the child node associated with said each link entry.

31. the non-transitory computer-readable storage medium of claim 27, wherein said information

hierarchy is comprised of resources stored within a database managed by a database server.

32. the non-transitory computer-readable storage medium of claim 31, wherein said database server is configured to add or remove a link entry from said link entry hierarchy in response to said database server adding or removing a resource from said node hierarchy.

33. the non-transitory computer-readable storage medium of claim 27, wherein:

said link entry hierarchy is a relational table;

said link entries are rows within said relational table; and

said plurality of link entry identifiers are row ids referring to a row in said relational table.