Method and/or system for manipulating tree expressions

• US 20060095442A1
• Filed: 12/07/2004
• Published: 05/04/2006
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.), Virginia T. Jenkins
• Original Assignee: Robert T. and Virginia T. Jenkins as Trustees for the Jenkins Family Trust Dated February 8, 2002
• Inventors: LeTourneau, Jack J.
• Granted Patent: US 7,627,591 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Embodiments of methods and/or systems of manipulating tree expressions are disclosed.

Claims

1. A method of manipulating an edge-labeled tree (ELT) comprising:

converting a first ELT in a first view to a first ELT in a second view.

2. The method of claim 1, and further comprising:

combining said first ELT in said second view with a second ELT in said second view.

3. The method of claim 1, and further comprising:

applying a push operation to said first ELT in said second view.

4. The method of claim 3, and further comprising:

converting said first ELT in said second view to a natural numeral after applying said push operation.

5. The method of claim 4, wherein said converting said first ELT to a natural numeral includes employing a model of expressions in which a push operation has the form

Push(x)=Q(Rx−

s), where R and S are natural numerals and R>

S.

6. The method of claim 2, wherein said combining comprises:

converting said ELTs in said second view to numerals;

combining said numerals; and

converting said combined numerals to an ELT.

7. The method of claim 6, wherein said converting said ELTs to natural numerals includes employing a model of expressions in which a merger operation has the form:

X merged with Y=X*Y.

8. The method of claim 6, wherein said ELT comprises an ELT in said second view.

9. The method of claim 6, wherein said ELT comprises an ELT in a view other than said second view.

10. A method of manipulating an node-labeled tree (NLT) comprising:

converting a first NLT in a first view to a first NLT in a second view.

11. The method of claim 10, and further comprising:

combining said first NLT in said second view with a second NLT in said second view.

12. The method of claim 10, and further comprising:

applying a push operation to said first NLT in said second view.

13. The method of claim 12, and further comprising:

converting said first NLT in said second view to a natural numeral after applying said push operation.

14. The method of claim 13, wherein said converting said first NLT to a natural numeral includes employing a model of expressions in which a push operation has the form:

Push(x)=Q(Rx−

s), where R and S are natural numerals and R>

S.

15. The method of claim 11, wherein said combining comprises:

converting said NLTs in said second view to numerals;

combining said numerals; and

converting said combined numerals to an NLT.

16. The method of claim 15, wherein said converting said NLTs to natural numerals includes employing a model of expressions in which a merger operation has the form:

X merged with Y=X*Y.

17. The method of claim 15, wherein said NLT comprises an NLT in said second view.

18. The method of claim 15, wherein said NLT comprises an NLT in a view other than said second view.

19. A method of manipulating an edge-labeled tree (ELT) comprising:

applying a push operation to said ELT; and

changing said ELT to a different view.

20. The method of claim 19, wherein said push operation comprises adding an edge and labeling it.

21. The method of claim 20 wherein said push operation comprises labeling said edge with a first numeral.

22. The method of claim 21, wherein said ELT has a view of N, N being a second numeral;

and wherein said first numeral comprises a numeral selected from the group of numerals that are less than said second numeral.

23. A method of manipulating a node-labeled tree (NLT) comprising:

applying a push operation to said NLT; and

changing said NLT to a different view.

24. The method of claim 23, wherein said push operation comprises adding a node and labeling it.

25. The method of claim 24, wherein said push operation comprises labeling said node with a first numeral.

26. The method of claim 25, wherein said NLT has a view of M, M being a second numeral;

and wherein said first numeral comprises a numeral selected from the group of numerals that are less than said second numeral.

27. An article comprising:

a storage medium having stored thereon instructions that, when executed, result in performance of a method of manipulating an edge-labeled tree (ELT) as follows;

converting a first ELT in a first view to a first ELT in a second view.

28. The article of claim 27, wherein said instructions, when executed, further result in:

combining said first ELT in said second view with a second ELT in said second view.

29. The article of claim 27, wherein said instructions, when executed, further result in:

applying a push operation to said first ELT in said second view.

30. The article of claim 29, wherein said instructions, when executed, further result in:

converting said first ELT in said second view to a natural numeral after applying said push operation.

31. The article of claim 30, wherein said instructions, when executed, further result in said converting said first ELT to a natural numeral including employing a model of expressions in which a push operation has the form:

Push(x)=Q(Rx−

s), where R and S are natural numerals and R>

S.

32. The article of claim 28, wherein said instructions, when executed, further result in said combining comprising:

converting said ELTs in said second view to numerals;

combining said numerals; and

converting said combined numerals to an ELT.

33. The article of claim 32, wherein said instructions, when executed, further result in said converting said ELTs to natural numerals including employing a model of expressions in which a merger operation has the form:

X merged with Y=X*Y.

34. The article of claim 32, wherein said instructions, when executed, further result in said ELT comprising an ELT in said second view.

35. The article of claim 32, wherein said instructions, when executed, further result in said ELT comprising an ELT in a view other than said second view.

36. An article comprising:

a storage medium having stored thereon instructions that, when executed, result in performance of a method of manipulating an node-labeled tree (NLT) as follows;

converting a first NLT in a first view to a first NLT in a second view.

37. The article of claim 36, wherein said instructions, when executed, further result in:

combining said first NLT in said second view with a second NLT in said second view.

38. The article of claim 36, wherein said instructions, when executed, further result in:

applying a push operation to said first NLT in said second view.

39. The article of claim 38, wherein said instructions, when executed, further result in:

converting said first NLT in said second view to a natural numeral after applying said push operation.

40. The article of claim 39, wherein said instructions, when executed, further result in said converting said first NLT to a natural numeral including employing a model of expressions in which a push operation has the form:

Push(x)=Q(Rx−

s), where R and S are natural numerals and R>

S.

41. The article of claim 37, wherein said instructions, when executed, further result in said combining comprising:

converting said NLTs in said second view to numerals;

combining said numerals; and

converting said combined numerals to an NLT.

42. The article of claim 41, wherein said instructions, when executed, further result in said converting said NLTs to natural numerals including employing a model of expressions in which a merger operation has the form:

X merged with Y=X*Y.

43. The article of claim 41, wherein said instructions, when executed, further result in said NLT comprising an NLT in said second view.

44. The article of claim 41, wherein said instructions, when executed, further result in said NLT comprising an NLT in a view other than said second view.

45. An article comprising:

a storage medium having stored thereon instructions that, when executed, result in performance of a method of manipulating an edge-labeled tree (ELT) as follows;

applying a push operation to said ELT; and

changing said ELT to a different view.

46. The article of claim 45, wherein said instructions, when executed, further result in said push operation comprising adding an edge and labeling it.

47. The article of claim 46 wherein said instructions, when executed, further result in said push operation comprising labeling said edge with a first numeral.

48. The article of claim 47, wherein said instructions, when executed, further result in said ELT having a view of N, N being a second numeral, and further result in said first numeral comprising a numeral selected from the group of numerals that are less than said second numeral.

49. An article comprising:

a storage medium having stored thereon instructions that, when executed, result in a method of manipulating a node-labeled tree (NLT) as follows;

applying a push operation to said NLT; and

changing said NLT to a different view.

50. The article of claim 49, wherein said instructions, when executed, further result in said push operation comprising adding a node and labeling it.

51. The article of claim 50, wherein said instructions, when executed, further result in said push operation comprising labeling said node with a first numeral.

52. The article of claim 51, wherein said instructions, when executed, further result in said NLT having a view of M, M being a second numeral, and further result in said first numeral comprising a numeral selected from the group of numerals that are less than said second numeral.

53. An apparatus comprising:

a computing platform;

said computing platform being adapted to convert a first ELT in a first view to a first ELT in a second view.

54. The apparatus of claim 53, wherein said computing platform is further adapted to combine said first ELT in said second view with a second ELT in said second view.

55. The apparatus of claim 53, wherein said computing platform is further adapted to apply a push operation to said first ELT in said second view.

56. The apparatus of claim 55, wherein said computing platform is further adapted to convert said first ELT in said second view to a natural numeral after applying said push operation.

57. The apparatus of claim 56, wherein said computing platform is adapted to convert said first ELT to a natural numeral by employing a model of expressions in which a push operation has the form:

Push(x)=Q(Rx−

s), where R and S are natural numerals and R>

S.

58. The apparatus of claim 54, wherein said computing platform is further adapted to convert said ELTs in said second view to numerals, combine said numerals, and convert said combined numerals to an ELT.

59. The apparatus of claim 58, wherein said computing platform is adapted to convert said ELTs to natural numerals by employing a model of expressions in which a merger operation has the form:

X merged with Y=X*Y.

60. The apparatus of claim 58, wherein said computing platform is further adapted to convert said ELT to an ELT in said second view.

61. The apparatus of claim 58, wherein said computing platform is further adapted to convert said ELT to an ELT in a view other than said second view.

62. An apparatus comprising:

a computing platform;

said computing platform adapted to convert a first NLT in a first view to a first NLT in a second view.

63. The apparatus of claim 62, wherein said computing platform is further adapted to combine said first NLT in said second view with a second NLT in said second view.

64. The apparatus of claim 62, wherein said computing platform is further adapted to apply a push operation to said first NLT in said second view.

65. The apparatus of claim 64, wherein said computing platform is further adapted to convert said first NLT in said second view to a natural numeral after applying said push operation.

66. The apparatus of claim 65, wherein said computing platform is further adapted to convert said first NLT to a natural numeral by employing a model of expressions in which a push operation has the form:

Push(x)=Q(Rx−

s), where R and S are natural numerals and R>

S.

67. The apparatus of claim 63, wherein said computing platform is further adapted to convert said NLTs in said second view to numerals, combine said numerals, and convert said combined numerals to an NLT.

68. The apparatus of claim 67, wherein said computing platform is adapted to convert said NLTs to natural numerals by employing a model of expressions in which a merger operation has the form:

X merged with Y=X*Y.

69. The apparatus of claim 67, wherein said computing platform is adapted to convert said NLT to an NLT in said second view.

70. The apparatus of claim 67, wherein said computing platform is adapted to convert said NLT to an NLT in a view other than said second view.

71. An apparatus comprising:

a computing platform;

said computing platform adapted to apply a push operation to an ELT, and to change said ELT to a different view.

72. The apparatus of claim 71, wherein said computing platform is further adapted to apply said push operation by adding an edge and labeling it.

73. The apparatus of claim 72, wherein said computing platform is adapted to apply said push operation by labeling said edge with a first numeral.

74. The apparatus of claim 73, wherein said computing platform is adapted to have said ELT comprise an ELT in a view of N, N being a second numeral, and is further adapted so that said first numeral comprises a numeral selected from the group of numerals that are less than said second numeral.

75. An apparatus comprising:

a computing platform;

said computing platform being adapted to apply a push operation to a NLT, and to change said NLT to a different view.

76. The apparatus of claim 75, wherein said computing platform is further adapted to apply said push operation by adding a node and labeling it.

77. The apparatus of claim 76, wherein said computing platform is further adapted to apply said push operation by labeling said node with a first numeral.

78. The apparatus of claim 77, wherein said computing platform is adapted to have said NLT comprise an NLT having a view of M, M being a second numeral, and is further adapted so that said first numeral comprises a numeral selected from the group of numerals that are less than said second numeral.

79. An apparatus comprising:

a computing platform;

said computing platform comprising means to convert a first ELT in a first view to a first ELT in a second view.

80. The apparatus of claim 79, wherein said computing platform further comprises means to combine said first ELT in said second view with a second ELT in said second view.

81. The apparatus of claim 79, wherein said computing platform further comprises means to apply a push operation to said first ELT in said second view.

82. The apparatus of claim 81, wherein said computing platform further comprises means to convert said first ELT in said second view to a natural numeral after applying said push operation.

83. The apparatus of claim 82, wherein said means to convert said first ELT to a natural numeral comprises means to employ a model of expressions in which a push operation has the form:

Push(x)=Q(Rx−

s), where R and S are natural numerals and R>

S.

84. The apparatus of claim 80, wherein said computing platform further comprises means to convert said ELTs in said second view to numerals, means to combine said numerals, and means to convert said combined numerals to an ELT.

85. The apparatus of claim 84, wherein said means to convert said ELTs to natural numerals comprises means to employ a model of expressions in which a merger operation has the form:

X merged with Y=X*Y.

86. The apparatus of claim 84, wherein said computing platform further comprises means to convert said ELT to an ELT in said second view.

87. The apparatus of claim 84, wherein said computing platform further comprises means to convert said ELT to an ELT in a view other than said second view.

88. An apparatus comprising:

a computing platform;

said computing platform comprising means to convert a first NLT in a first view to a first NLT in a second view.

89. The apparatus of claim 88, wherein said computing platform further comprises means to combine said first NLT in said second view with a second NLT in said second view.

90. The apparatus of claim 88, wherein said computing platform further comprises means to apply a push operation to said first NLT in said second view.

91. The apparatus of claim 90, wherein said computing platform further comprises means to convert said first NLT in said second view to a natural numeral after applying said push operation.

92. The apparatus of claim 91, wherein said means to convert said first NLT to a natural numeral comprises means to employ a model of expressions in which a push operation has the form:

Push(x)=Q(Rx−

s), where R and S are natural numerals and R>

S.

93. The apparatus of claim 89, wherein said computing platform further comprises means to convert said NLTs in said second view to numerals, means to combine said numerals, and means to convert said combined numerals to an NLT.

94. The apparatus of claim 93, wherein said means to convert said NLTs to natural numerals comprises means to employ a model of expressions in which a merger operation has the form:

X merged with Y=X*Y.

95. The apparatus of claim 93, wherein said computing platform comprises means to convert said NLT to an NLT in said second view.

96. The apparatus of claim 93, wherein said computing platform comprises means to convert said NLT to an NLT in a view other than said second view.

97. An apparatus comprising:

a computing platform;

said computing platform comprises means to apply a push operation to an ELT, and means to change said ELT to a different view.

98. The apparatus of claim 97, wherein said means to apply said push operation comprises means to add an edge and label it.

99. The apparatus of claim 98, wherein said means to apply said push operation comprises means to label said edge with a first numeral.

100. An apparatus comprising:

a computing platform;

said computing platform comprises means to apply a push operation to a NLT, and means to change said NLT to a different view.

101. The apparatus of claim 100, wherein said means to apply said push operation comprises means to add a node and label it.

102. The apparatus of claim 101, wherein said means to apply said push operation comprises means to label said node with a first numeral.

103. A tree structure comprising:

an edge labeled tree (ELT) structure formed by the following method;

converting a first ELT in a first view to a first ELT in a second view.

104. The tree structure of claim 103, and further formed by:

combining said first ELT in said second view with a second ELT in said second view.

105. The tree structure of claim 103, and further formed by:

applying a push operation to said first ELT in said second view.

106. The tree structure of claim 105, and further formed by:

converting said first ELT in said second view to a natural numeral after applying said push operation.

107. The tree structure of claim 106, and further formed by said converting said first ELT to a natural numeral including employing a model of expressions in which a push operation has the form:

Push(x)=Q(Rx−

s), where R and S are natural numerals and R>

S.

108. The tree structure of claim 104, and further formed by said combining comprising:

converting said ELTs in said second view to numerals;

combining said numerals; and

converting said combined numerals to an ELT.

109. The tree structure of claim 108, and further formed by said converting said ELTs to natural numerals including employing a model of expressions in which a merger operation has the form:

X merged with Y=X*Y.

110. The tree structure of claim 108, and further formed by said ELT comprising an ELT in said second view.

111. The tree structure of claim 108, and further formed by said ELT comprising an ELT in a view other than said second view.

112. A tree structure comprising:

a node labeled tree (NLT) structure formed by the following method;

converting a first NLT in a first view to a first NLT in a second view.

113. The tree structure of claim 112, and further having been formed by:

combining said first NLT in said second view with a second NLT in said second view.

114. The tree structure of claim 112, and further having been formed by:

applying a push operation to said first NLT in said second view.

115. The tree structure of claim 114, and further having been formed by:

converting said first NLT in said second view to a natural numeral after applying said push operation.

116. The tree structure of claim 115, and further having been formed by:

said converting said first NLT to a natural numeral including employing a model of expressions in which a push operation has the form;

Push(x)=Q(Rx−

s), where R and S are natural numerals and R>

S.

117. The tree structure of claim 113, and further having been formed by said combining comprising:

converting said NLTs in said second view to numerals;

combining said numerals; and

converting said combined numerals to an NLT.

118. The tree structure of claim 117, and further having been formed by said converting said NLTs to natural numerals including employing a model of expressions in which a merger operation has the form:

X merged with Y=X*Y.

119. The tree structure of claim 117, and further having been formed by said NLT comprising an NLT in said second view.

120. The tree structure of claim 117, and further having been formed by said NLT comprising an NLT in a view other than said second view.

121. A tree structure comprising:

an edge-labeled tree (ELT) structure formed by the following method;

applying a push operation to said ELT; and

changing said ELT to a different view.

122. The tree structure of claim 121, and further having been formed by said push operation comprising adding an edge and labeling it.

123. The tree structure of claim 122, and further having been formed by said push operation comprising labeling said edge with a first numeral.

124. A tree structure comprising:

a node-labeled tree (NLT) structure formed by the following method comprising;

applying a push operation to said NLT; and

changing said NLT to a different view.

125. The tree structure of claim 124, and further having been formed by said push operation comprising adding a node and labeling it.

126. The tree structure of claim 125, and further having been formed by said push operation comprising labeling said node with a first numeral.