Method and apparatus for creating an index in a database system

• US 6,240,407 B1
• Filed: 12/17/1998
• Issued: 05/29/2001
• Est. Priority Date: 04/29/1998
• Status: Expired due to Fees

• Current Assignee: Ineos USA LLC (Ineos AG)
• Original Assignee: International Business Machines Corporation
• Inventors: Cheng, Josephine Miu-Kung, Xu, Jian, Chow, Jyh-Herng, Chang, Daniel T.
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US09/215,036
• Time in Patent Office: 894 Days
• Field of Search: 707/1, 707/2, 707/3, 707/5, 707/101, 707/102, 707/103, 707/10, 709/225, 717/1, 714/4
• US Class Current: 707/711
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A method, apparatus and article of manufacture for computer-implemented creation of an index in a database system is defined, wherein a structured document, interactively entered by an operator or already stored in the database system, is parsed into at least one corresponding element, then abstracted using a predefined abstraction procedure to obtain a set of abstracted values, the set of abstracted values being stored in the index for efficient execution of structured queries.

Claims

1. A method of creating an index in a database system for execution of a structured query given by a user, comprising the steps of:

providing a structured document, having at least one element;

defining an abstraction procedure for said structured document;

parsing said structured document into said at least one element;

abstracting said at least one element using said abstraction procedure to obtain a set of abstract values; and

storing said set of abstract values in said index for execution of said structured query in said database system.

2. The method of claim 1, wherein said at least one element of said structured document is identified by tags defined by said user.

3. The method of claim 2, wherein in said abstracting step, said abstraction procedure is structured on at least one level, said at least one level including each of said at least one element having identical tags.

4. The method of claim 3, wherein said step of defining said abstraction procedure comprises mapping said structured document into itself.

5. The method of claim 3, wherein said step of defining said abstraction procedure comprises merging each of said at least one element having identical tags.

6. The method of claim 3, wherein said step of defining said abstraction procedure comprises merging said at least one element included in said at least one level into a new merged element having a new tag.

7. The method of claim 3, wherein said structured document comprises a plurality of elements and wherein said step of defining said abstraction procedure comprises removing, from said structured document, each of said plurality of elements having no importance to said structured query.

8. The method of claim 3, wherein said step of defining said abstraction procedure comprises collapsing said structured document into a unique element.

9. The method of claim 3, wherein said abstraction procedure is structured on a plurality of levels including a lower level and an upper level, said structured document comprises a plurality of elements, and said step of defining said abstraction procedure comprises collapsing each of said plurality of elements included in said lower level into one of said plurality of elements included in said upper level.

10. The method of claim 1, wherein said structured document having said at least one element resides in a concrete domain in said database system, and wherein said concrete domain comprises a plurality of structured documents within said database system.

11. The method of claim 1, wherein said set of abstracted values and said index reside in an abstract domain in said database system, and wherein said abstract domain comprises abstractions of a plurality of structured documents within said database system.

12. The method of claim 1, wherein in said defining step, said abstraction procedure is defined to further abstract a path expression given by said user in said structured query.

13. The method of claim 12, wherein in said defining step, said abstraction procedure comprises preserving said path expression of said structured query.

14. The method of claim 12, wherein in said defining step, said abstraction procedure comprises not preserving said path expression of said structured query.

15. The method of claim 2, wherein said at least one element of said structured document further comprises content, and wherein said content includes text within said tags defined by said user.

16. The method of claim 15, wherein said content of said at least one element of said structured document is a character string.

17. The method of claim 15, wherein said content of said at least one element of said structured document is a numeric value.

18. The method of claim 15, wherein said step of abstracting said at least one element of said structured document further includes abstracting said content of said at least one element.

19. The method of claim 2, wherein said at least one element of said structured document further comprises at least one attribute, and wherein said at least one attribute includes a plurality of corresponding names and values associated with said at least one element of said structured document.

20. The method of claim 19, wherein said step of abstracting said at least one element of said structured document further includes abstracting said at least one attribute of said at least one element.

21. The method of claim 19, wherein said at least one attribute of said at least one element of said structured document is a character string.

22. The method of claim 19, wherein said at least one attribute of said at least one element of said structured document is a numeric value.

23. An apparatus for creating an index in a database system for executing a structured query given by a user, said apparatus comprising:

a computer having at least one data storage device connected thereto, wherein said at least one data storage device stores said index and said database system; and

at least one computer program performed by said computer for

providing a structured document, having at least one element;

defining an abstraction procedure for said structured document;

parsing said structured document into said at least one element;

abstracting said at least one element using said abstraction procedure to obtain a set of abstract values;

storing said set of abstract values in said index for execution of said structured query in said database system.

24. The apparatus of claim 23, wherein said at least one element of said structured document is identified by tags defined by said user.

25. The apparatus of claim 24, wherein said abstraction procedure is structured on at least one level, said at least one level including each of said at least one element having identical tags.

26. The apparatus of claim 25, wherein said at least one computer program, during defining, further maps said structured document into itself.

27. The apparatus of claim 25, wherein said at least one computer program, during defining, further merges each of said at least one element having identical tags.

28. The apparatus of claim 25, wherein said at least one computer program, during defining, further merges said at least one element included in said at least one level into a new merged element having a new tag.

29. The apparatus of claim 25, wherein said structured document comprises a plurality of elements and wherein said at least one computer program, during defining, further removes each of said plurality of elements having no importance to said structured query from said structured document.

30. The apparatus of claim 25, wherein said at least one computer program, during defining, further collapses said structured document into a unique element.

31. The apparatus of claim 25, wherein said abstraction procedure is structured on a plurality of levels including a lower level and an upper level, said structured document comprises a plurality of elements, and said at least one computer program, during defining, further collapses each of said plurality of elements included in said lower level into one of said plurality of elements included in said upper level.

32. The apparatus of claim 23, wherein said structured document having said at least one element resides in a concrete domain in said database system, and wherein said concrete domain comprises a plurality of structured documents within said database system.

33. The apparatus of claim 23, wherein said set of abstracted values and said index reside in an abstract domain in said database system, and wherein said abstract domain comprises abstractions of a plurality of structured documents within said database system.

34. The apparatus of claim 23, wherein said at least one computer program, during defining, defines said abstraction procedure to further abstract a path expression given by said user in said structured query.

35. The apparatus of claim 34, wherein said at least one computer program, during defining, further defines said abstraction procedure to preserve said path expression of said structured query.

36. The apparatus of claim 34, wherein said at least one computer program, during defining, further defines said abstraction procedure not to preserve said path expression of said structured query.

37. The apparatus of claim 24, wherein said at least one element of said structured document further comprises content, and wherein said content includes text within said tags defined by said user.

38. The apparatus of claim 37, wherein said content of said at least one element of said structured document is a character string.

39. The apparatus of claim 37, wherein said content of said at least one element of said structured document is a numeric value.

40. The apparatus of claim 37, wherein said at least one computer program, during abstracting, further abstracts said content of said at least one element.

41. The apparatus of claim 24, wherein said at least one element of said structured document further comprises at least one attribute, and wherein said at least one attribute includes a plurality of corresponding names and values associated with said at least one element of said structured document.

42. The apparatus of claim 41, wherein said at least one computer program, during abstracting, further abstracts said at least one attribute of said at least one element.

43. The apparatus of claim 41, wherein said at least one attribute of said at least one element of said structured document is a character string.

44. The apparatus of claim 41, wherein said at least one attribute of said at least one element of said structured document is a numeric value.

45. An article of manufacture comprising a program storage device readable by a computer and tangibly embodying at least one program of instructions executable by said computer to perform method steps for creating an index in a database system, said computer having at least one data storage device coupled thereto for storing said index and said database system, the method comprising the steps of:

providing a structured document, having at least one element;

defining an abstraction procedure for said structured document;

parsing said structured document into said at least one element;

abstracting said at least one element using said abstraction procedure to obtain a set of abstract values; and

storing said set of abstract values in said index for execution of said structured query in said database system.

46. The article of manufacture of claim 45, wherein said at least one element of said structured document is identified by tags defined by said user.

47. The article of manufacture of claim 46, wherein in said abstracting step, said abstraction procedure is structured on at least one level, said at least one level including each of said at least one element having identical tags.

48. The article of manufacture of claim 47, wherein said step of defining said abstraction procedure comprises mapping said structured document into itself.

49. The article of manufacture of claim 47, wherein said step of defining said abstraction procedure comprises merging each of said at least one element having identical tags.

50. The article of manufacture of claim 47, wherein said step of defining said abstraction procedure comprises merging said at least one element included in said at least one level into a new merged element having a new tag.

51. The article of manufacture of claim 47, wherein said structured document comprises a plurality of elements and said step of defining said abstraction procedure comprises removing each of said plurality of elements having no importance to said structured query from said structured document.

52. The article of manufacture of claim 47, wherein said step of defining said abstraction procedure comprises collapsing said structured document into a unique element.

53. The article of manufacture of claim 47, wherein said abstraction procedure is structured on a plurality of levels including a lower level and an upper level, said structured document comprises a plurality of elements, and said step of defining said abstraction procedure comprises collapsing each of said plurality of elements included in said lower level into one of said plurality of elements included in said upper level.

54. The article of manufacture of claim 45, wherein said structured document having said at least one element resides in a concrete domain in said database system, and wherein said concrete domain comprises a plurality of structured documents within said database system.

55. The article of manufacture of claim 45, wherein said set of abstracted values and said index reside in an abstract domain in said database system, and wherein said abstract domain comprises abstractions of a plurality of structured documents within said database system.

56. The article of manufacture of claim 45, wherein in said defining step, said abstraction procedure is defined to further abstract a path expression given by said user in said structured query.

57. The article of manufacture of claim 56, wherein in said defining step, said abstraction procedure comprises preserving said path expression of said structured query.

58. The article of manufacture of claim 56, wherein in said defining step, said abstraction procedure comprises not preserving said path expression of said structured query.

59. The article of manufacture of claim 46, wherein said at least one element of said structured document further comprises content, and wherein said content includes text within said tags defined by said user.

60. The article of manufacture of claim 59, wherein said content of said at least one element of said structured document is a character string.

61. The article of manufacture of claim 59, wherein said content of said at least one element of said structured document is a numeric value.

62. The article of manufacture of claim 59, wherein said step of abstracting said at least one element of said structured document further includes abstracting said content of said at least one element.

63. The article of manufacture of claim 46, wherein said at least one element of said structured document further comprises at least one attribute, and wherein said at least one attribute includes a plurality of corresponding names and values associated with said at least one element of said structured document.

64. The article of manufacture of claim 63, wherein said step of abstracting said at least one element of said structured document further includes abstracting said at least one attribute of said at least one element.

65. The article of manufacture of claim 63, wherein said at least one attribute of said at least one element of said structured document is a character string.

66. The article of manufacture of claim 63, wherein said at least one attribute of said at least one element of said structured document is a numeric value.