Method and/or system for manipulating tree expressions

• US 7,627,591 B2
• Filed: 12/07/2004
• Issued: 12/01/2009
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: Lower48 IP, LLC (Lower48 Analytics, Inc.), Virginia T. Jenkins
• Original Assignee: Skyler Technology Incorporated
• Inventors: Letourneau, Jack J.
• Primary Examiner(s): Lu, Kuen S
• Application Number:
  US11/006,841
• Publication Number:
  US 20060095442A1
• Time in Patent Office: 1,820 Days
• Field of Search: 707/101
• 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. In one particular example, a tree expression may represent information and/or data in one particular view among a plurality of views. Further, in another particular example, a tree expression representing information and/or data in a first view may be transformed and/or converted to a tree expression which represents the information and/or data in a second view which is different from the first view.

Claims

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

executing instructions on one or more processors to;

convert a signal representing first ELT in a first view to a signal representing first ELT in a second view to recognize a particular pattern or relationship in a set of data;

apply a push operation to said signal representing said first ELT in said second view; and

convert said signal representing said first ELT in said second view to a signal representing a natural numeral after applying said push operation 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, where x is a natural numeral, and where Q( ) is an operation to generate non-composite numerals in ascending order,

wherein said first view is associated with a first number of distinct values in a first set of distinct values from which edge labels are selected for ELTs in said first view, wherein said second view is associated with a second number of distinct values in a second set of distinct values from which edge labels are selected for ELTs in said second view, and wherein said first number is not identical with said second number.

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

further executing said instructions on said one or more processors to combine said signal representing said first ELT in said second view with a signal representing a second ELT in said second view.

3. The method of claim 2, wherein said execution of said instructions to combine further comprises:

converting said signals representing said first and second ELTs in said second view to signals representing natural numerals;

combining said signals representing natural numerals; and

converting said combined numerals to a resulting ELT.

4. The method of claim 3, wherein said converting said signals representing 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, where X and Y are natural numerals associated with ELTs according to an association of ELTs with numerals “

*”

is a multiplication operation, and the value X*Y is a natural numeral associated, according to said association of ELTs with numerals, with a merger of said ELTs associated with X and Y.

5. The method of claim 3, wherein said resulting ELT comprises an ELT in said second view.

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

7. The method of claim 1, wherein x is a natural numeral associated with an operand tree according to an association of trees and natural numerals, wherein Q(Rx−

s) is a natural numeral associated with a pushed tree according to said association, and wherein said pushed tree comprises a root node connected to a root of said operand tree by a labeled edge.

8. The method of claim 1, wherein said push operation comprises providing a signal representative of an ELT comprising a root node connected by a labeled edge to a root node of said first ELT in said second view.

9. An article comprising:

a storage medium having stored thereon instructions that, in response to being executed by a processor, direct said processor to;

convert a signal representing a first ELT in a first view to a signal representing a first ELT in a second view to enable recognition of a pattern or relationship in a set of data;

apply a push operation to said signal representing said first ELT in said second view; and

convert said signal representing said first ELT in said second view to a signal representing a natural numeral after applying said push operation 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, where x is a natural numeral, and where Q( ) is an operation to generate non-composite numerals in ascending order,

wherein said first view is associated with a first number of distinct values in a first set of distinct values from which edge labels are selected for ELTs in said first view, wherein said second view is associated with a second number of distinct values in a second set of distinct values from which edge labels are selected for ELTs in said second view, and wherein said first number is not identical with said second number.

10. The article of claim 9, wherein said instructions, in response to being executed by said processor, further direct said processor to:

combine said signal representing said first ELT in said second view with a signal representing a second ELT in said second view.

11. The article of claim 10, wherein said instructions, in response to being executed by said processor, further direct said processor to combine said signal representing said first ELT in said second view with said signal representing a second ELT in said second view by:

converting said signals representing first and second ELTs in said second view to signals representing natural numerals;

combining said natural numerals; and

converting said combined numerals to a signal representing a resulting ELT.

12. The article of claim 11, wherein said instructions, in response to being executed by said processor, further direct said processor 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, where X and Y are natural numerals associated with ELTs and “

*”

is a multiplication operation, and the value X*Y is a natural numeral associated, according to said association of ELTs with numerals, with a merger of said ELTs associated with X and Y.

13. The article of claim 11, wherein said instructions, in response to being executed by said processor, further direct said processor so that said signal representing said resulting ELT comprises a signal representing an ELT in said second view.

14. The article of claim 11, wherein said instructions, in response to being executed by said processor, further direct said processor so that said signal representing said resulting ELT comprises a signal representing an ELT in a view other than said second view.

15. The article of claim 9, wherein x is a natural numeral associated with an operand tree according to an association of trees and natural numerals, wherein Q(Rx−

s) is a natural numeral associated with a pushed tree according to said association, and wherein said pushed tree comprises a root node connected to a root of said operand tree by a labeled edge.

16. The article of claim 9, wherein said push operation comprises providing a signal representative of an ELT comprising a root node connected by a labeled edge to a root node of said first ELT in said second view.

17. An apparatus comprising:

a computing platform, said computing platform comprising one or more processors programmed with instructions to recognize a particular pattern or relationship in a set of data;

said one or more processors being further programmed with instructions to;

convert a signal representative of a first ELT in a first view to a signal representative of a first ELT in a second view, wherein said first view is associated with a first number of distinct values in a first set of distinct values from which edge labels are selected for ELTs in said first view;

apply a push operation to said signal representing said first ELT in said second view; and

convert said signal representing said first ELT in said second view to a signal representing a natural numeral after applying said push operation 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, where x is a natural numeral, and where Q( ) is an operation to generate non-composite numerals in ascending order,

wherein said second view is associated with a second number of distinct values in a second set of distinct values from which edge labels are selected for ELTs in said second view, and wherein said first number is not identical with said second number.

18. The apparatus of claim 17, wherein said one or more processors are further programmed with instructions to combine said signal representative of said first ELT in said second view with a signal representative of a second ELT in said second view.

19. The apparatus of claim 18, wherein said computing platform is further adapted to convert said signals representative of said first and second ELTs in said second view to signals representative of natural numerals, combine said natural numerals, and convert said combined numerals to a signal representative of a resulting ELT.

20. The apparatus of claim 19, wherein said one or more processors are further programmed with instructions to convert said signals representative of ELTs to signals representative of natural numerals by employing a model of expressions in which a merger operation has the form:

X merged with Y=X*Y, where X and Y are natural numerals associated with ELTs and “

*”

is a multiplication operation, and the value X*Y is a natural numeral associated, according to said association of ELTs with numerals, with a merger of said ELTs associated with X and Y.

21. The apparatus of claim 19, wherein said one or more processors are further programmed with instructions to convert said signal representative of said resulting ELT to signal representative of an ELT in said second view.

22. The apparatus of claim 19, wherein said one or more processors are further programmed with instructions to convert said signal representative of said resulting ELT to a signal representative of an ELT in a view other than said second view.

23. The apparatus of claim 17, wherein x is a natural numeral associated with an operand tree according to an association of trees and natural numerals, wherein Q(Rx−

s) is a natural numeral associated with a pushed tree according to said association, and wherein said pushed tree comprises a root node connected to a root of said operand tree by a labeled edge.

24. The apparatus of claim 17, wherein said push operation comprises providing a signal representative of an ELT comprising a root node connected by a labeled edge to a root node of said first ELT in said second view.

25. An apparatus comprising:

a computing platform programmed to recognize a particular pattern or relationship in a set of data;

said computing platform comprising;

means to convert a signal representative of a first ELT in a first view to a signal representative of a first ELT in a second view

means to apply a push operation to said signal representative of said first ELT in said second view; and

means to convert said signal representative of said first ELT in said second view to a signal representative a natural numeral after applying said push operation 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, where x is a natural numeral, and where Q( ) is an operation to generate non-composite numerals in ascending order,

wherein said first view is associated with a first number of distinct values in a first set of distinct values from which edge labels are selected for ELTs in said first view, wherein said second view is associated with a second number of distinct values in a second set of distinct values from which edge labels are selected for ELTs in said second view, and wherein said first number is not identical with said second number.

26. The apparatus of claim 25, wherein said computing platform further comprises means to combine said signal representative of said first ELT in said second view with a signal representative of a second ELT in said second view.

27. The apparatus of claim 26, wherein said computing platform further comprises means to convert said signals representative of said first and second ELTs in said second view to signals representative of natural numerals, means to combine said natural numerals, and means to convert said combined numerals to a signal representing a resulting ELT.

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

X merged with Y=X*Y, where X and Y are natural numerals associated with ELTs and “

*”

is a multiplication operation, and the value X*Y is a natural numeral associated, according to said association of ELTs with numerals, with a merger of said ELTs associated with X and Y.

29. The apparatus of claim 27, wherein said computing platform further comprises means to convert said signal representative of said resulting ELT to a signal representative of an ELT in said second view.

30. The apparatus of claim 27, wherein said computing platform further comprises means to convert said signal representing said resulting ELT to a signal representative of an ELT in a view other than said second view.

31. The apparatus of claim 25, wherein x is a natural numeral associated with an operand tree according to an association of trees and natural numerals, wherein Q(Rx−

s) is a natural numeral associated with a pushed tree according to said association, and wherein said pushed tree comprises a root node connected to a root of said operand tree by a labeled edge.

32. The apparatus of claim 25, wherein said push operation comprises providing a signal representative of an ELT comprising a root node connected by a labeled edge to a root node of said first ELT in said second view.

33. A method of manipulating a labeled tree comprising:

executing instructions on one or more processors to;

convert one or more signals representative of a first labeled tree in a first view to a signal representative of a second labeled tree in a second view to recognize a particular pattern or relationship in a set of data;

apply a push operation to said signal representing said first labeled tree in said second view; and

convert said signal representing said first labeled tree in said second view to a signal representing a natural numeral after applying said push operation 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, where x is a natural numeral, and where Q( ) is an operation to generate non-composite numerals in ascending order,

wherein said first view is associated with a first number of distinct values in a first set of distinct values from which labels are selected for labeled trees in said first view, wherein said second view is associated with a second number of distinct values in a second set of distinct values from which labels are selected for labeled trees in said second view, and wherein said first number is not identical with said second number.