System and method for dynamic generation of structured documents

• US 6,912,538 B2
• Filed: 10/19/2001
• Issued: 06/28/2005
• Est. Priority Date: 10/20/2000
• Status: Expired due to Fees

• Current Assignee: Ed Gormsen, Kevin Stapel
• Original Assignee: Ed Gormsen, Kevin Stapel
• Inventors: Stapel, Kevin, Gormsen, Ed
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US10/032,223
• Publication Number:
  US 20020087571A1
• Time in Patent Office: 1,348 Days
• Field of Search: 707/100, 707/102, 707/101, 707/104.1, 715/501.1, 715/513, 715/900
• US Class Current: 1/1
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• 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

Abstract

A method and apparatus for representing complex data schemas and generating type validated output documents in a markup language. The methods apply to transforming document type definitions into extensible markup language coded information that can readily accommodate logical constraints imposed by recursion or repetition within the DTD structure. Furthermore, non-determinism arising from repetition or recursion in a data schema is resolved by traversal path coding using a matrix representation of the data schema.

Claims

1. A system for structured document generation, the system comprising:

a data structure input module which receives a data structure having a defined arrangement comprising one or more data elements having identifying relationships that associate the data elements;

a transformation module which transforms the data structure into a matrix representation to thereby preserve the defined arrangement of the data structure and wherein the matrix representation comprises an internally recognized organization of the data structure;

a data element input module that stores user specified information in the matrix representation of the data structure to thereby populate the data structure with information; and

a document generation module which accesses the matrix representation to generate a structured document comprising a representation of the information stored in the data elements in a markup language.

2. The system for structured document generation of claim 1, wherein the data structure received by the data structure input module comprises a document type definition that describes the organization of the data elements using an elemental identification scheme recognized by the transformation module.

3. The system for structured document generation of claim 2, wherein the document type definition is specified as an input file received by the data structure input module.

4. The system for structured document generation of claim 2, wherein the document type definition is specified by direct input into the data structure input module.

5. The system for structured document generation of claim 1, wherein the identifying relationships of the data structure comprise recursive relationships between the data elements.

6. The system for structured document generation of claim 5, wherein the recursive relationships between the data elements define non-deterministic relationships that are resolved through transformation into the matrix representation such that a deterministic relationship is produced between the data elements.

7. The system for structured document generation of claim 6, wherein the non-deterministic relationships derived from the recursive relationships that are resolved through transformation into the matrix representation using traversal ordering to produce the deterministic relationships between the data elements.

8. The system for structured document generation of claim 1, wherein the identifying relationships of the data structure comprise repetitive relationships between the data elements.

9. The system for structured document generation of claim 8, wherein the repetitive relationships between the data elements define non-deterministic relationships that are resolved through transformation into the matrix representation such that a deterministic relationship is produced between the data elements.

10. The system for structured document generation of claim 9, wherein the non-deterministic relationships derived from the repetitive relationships that are resolved through transformation into the matrix representation using traversal ordering to produce the deterministic relationships between the data elements.

11. The system for structured document generation of claim 1, further comprising a database that stores the matrix representation.

12. The system for structured document generation of claim 11, wherein the database that stores the matrix representation comprises a fixed number of tables that do not increase as a function of the data structure complexity.

13. The system for structured document generation of claim 1, wherein the markup language comprises extensible markup language.

14. The system for structured document generation of claim 1, wherein the markup language comprises wireless application protocol.

15. The system for structured document generation of claim 1, wherein the defined arrangement of the data structure comprises a hierarchical arrangement of the data structure that is preserved by the transformation module using the matrix representation.

16. The system for structured document generation of claim 1, wherein the defined arrangement of the data structure comprises a nonhierarchical arrangement of the data structure that is preserved by the transformation module using the matrix representation.

17. The system for structured document generation of claim 1, wherein the defined arrangement of the data structure comprises a hierarchical and nonhierarchical arrangement of the data structure that is preserved by the transformation module using the matrix representation.

18. A method for generating markup language data representations of a data schema containing a plurality of elements interrelated by one or more relationships, the method comprising:

defining a matrix representation for the data schema wherein the matrix representation defines the relationships interrelating the elements in such a manner so as to permit the elements to be deterministically interrelated;

mapping the matrix representation of elements into a database structure;

storing information in the elements of the matrix representation; and

accessing the information stored in matrix representation and outputting at least a portion of the information using a markup language wherein the format of the information is determined by the elements and relationships of the data schema and is represented by an output markup language.

19. The method for generating data representations of claim 18, wherein the data schema comprises a non-hierarchical structure and the matrix representation preserves the non-hierarchical structure.

20. The method for generating data representations of claim 18, wherein the data schema comprises a hierarchical structure and the matrix representation preserves the hierarchical structure.

21. The method for generating data representations of claim 18, wherein the data schema comprises one or more relationships that are recursively defined and wherein the matrix representation of the data schema resolves the recursive relationships in a deterministic manner.

22. The method for generating data representations of claim 21, wherein the recursive relationships of the data schema are accommodated by defining one or more traversal paths that associate each element with a traversal order to make the recursive relationship resolvable.

23. The method for generating data representations of claim 18, wherein the data schema comprises one or more relationships that are repetitively defined and wherein the matrix representation of the data schema resolves the repetitive relationship in a deterministic manner.

24. The method for generating data representations of claim 23, wherein the repetitive relationships of the data schema are accommodated by defining one or more traversal paths that associate each element with a traversal order to make the repetitive relationship resolvable.

25. The method for generating data representations of claim 18, wherein the matrix representation comprises a fixed table number that does not increase in size as a function of complexity of the data schema.

26. A method for representing relationships between elements in a data schema, the method comprising:

identifying the elements and the relationships between the data elements of the data schema;

applying a plurality of matrix transformation operations to encode the data schema; and

storing the encoded data schema in a database having a fixed number of tables so as to confer independence from data schema complexity.

27. The method for representing relationships of claim 26, wherein the matrix transformation operations further comprise:

assigning each data element in the representation to a single node;

defining linkages between the nodes based upon the relationships identified in the data schema;

defining one or more matrix traversals that are associated with the relationships between the data elements and wherein the matrix traversal identifies deterministic paths between the nodes through the linkages; and

defining the encoded data schema based upon the nodes, linkages, and matrix traversals.

28. A method for coding a document type definition into a structured document, the method comprising:

receiving the document type definition comprising information defined by a plurality of elements and relationships coded in a pre-arranged structure;

mapping the pre-arranged structure of the document type definition into a coded representation comprising a singular mapping of each of the plurality of elements that preserves the relationships coded in the pre-arranged structure;

storing the coded representation in a database construct having a fixed table number that maintains the singular mapping of the plurality of elements and the associated relationships;

populating the elements contained in the coded representation with information; and

generating the structured document by extracting the information contained coded representation stored in the database construct and outputting the information in a markup language.

29. The method for coding a document type definition into a structured document of claim 28, the method further comprising:

validating the document type definition to verify that the document type definition conforms to one or more logical constraints.

30. The method for coding a document type definition into a structured document of claim 29;

wherein document type definitions that lack logical constraints conformity are identified as logically invalid.

31. The method for coding a document type definition into a structured document of claim 28, the method further comprising:

validating the document type definition to verify that the document type definition conforms to one or more structural constraints.

32. The method for coding a document type definition into a structured document of claim 31;

wherein document type definitions that lack structural constraint conformity are identified as structurally invalid.

33. The method for structured document generation of claim 31, wherein the markup language comprises extensible markup language.

34. The method for coding a document type definition into a structured document of claim 28, wherein the pre-arranged structure codes for one or more recursive relationships between the elements that are resolvable by mapping the pre-arranged structure into the coded structure.

35. The method for coding a document type definition into a structured document of claim 28, wherein the pre-arranged structure codes for one or more repetitive relationships between the elements that are resolvable by mapping the pre-arranged structure into the coded structure.

36. The method for coding a document type definition into a structured document of claim 28, wherein the markup language used to code the information comprises extensible markup language.

37. The method for coding a document type definition into a structured document of claim 28, wherein the structured document generated using the markup language is type validated.

38. A method for structured document generation, the method comprising:

receiving a data structure comprising one or more data elements having identifying relationships that associate the data elements;

transforming the data structure into a matrix representation comprising an internally recognized organization of the data structure;

populating the data elements of the data structure transformed into the matrix representation with information; and

accessing the information in the matrix representation to generate a structured document comprising a representation of the information in a markup language.

39. The method for structured document generation of claim 38, wherein the received data structure comprises a document type definition that describes the organization of the data elements using an elemental identification scheme recognized by the transformation module.

40. The method for structured document generation of claim 39, wherein the document type definition comprises a non-hierarchical structure that is transformed into the matrix representation to thereby preserve the non-hierarchical organization of the document type definition.

41. The method for structured document generation of claim 39, wherein the document type definition comprises a hierarchical structure that is transformed into the matrix representation to thereby preserve the hierarchical organization of the document type definition.

42. The method for structured document generation of claim 39, wherein the identifying relationships of the data structure comprise recursive relationships between the data elements.

43. The method for structured document generation of claim 42, wherein the recursive relationships between the data elements define non-deterministic relationships that are resolved through transformation into the matrix representation such that a deterministic relationship is produced between the data elements.

44. The method for structured document generation of claim 39, wherein the identifying relationships of the data structure comprise repetitive relationships between the data elements.

45. The method for structured document generation of claim 44, wherein the repetitive relationships between the data elements define non-deterministic relationships that are resolved through transformation into the matrix representation such that a deterministic relationship is produced between the data elements.

46. A system for structured document generation, the system comprising:

an input module which receives a data structure comprising one or more data elements having identifying relationships that associate the data elements;

a transformation module which transforms the data structure into a matrix representation wherein the matrix representation comprises an internally recognized organization of the data structure;

a data element input module which populates the matrix representation with information; and

a document generation module which accesses the information of the matrix representation to generate a structured document comprising a representation of the information in a markup language.

47. The system for structured document generation of claim 46, wherein the data structure received by the input module comprises a non-hierarchical data structure.

48. The system for structured document generation of claim 46, wherein the data structure received by the input module comprises a hierarchical data structure.

49. The system for structured document generation of claim 46, wherein the data structure received by the input module comprises both a non-hierarchical data structure and a hierarchical data structure.

50. The system for structured document generation of claim 46, wherein the data structure received by the input module comprises a document type definition file that describes the organization of the data elements using an elemental identification scheme recognized by the transformation module.

51. The system for structured document generation of claim 46, wherein the identifying relationships of the data structure comprise recursive relationships between the data elements.

52. The system for structured document generation of claim 51, wherein the recursive relationships between the data elements define non-deterministic relationships that are resolved through transformation into the matrix representation such that a deterministic relationship is produced between the data elements.

53. The system for structured document generation of claim 46, wherein the identifying relationships of the data structure comprise repetitive relationships between the data elements.

54. The system for structured document generation of claim 53, wherein the repetitive relationships between the data elements define non-deterministic relationships that are resolved through transformation into the matrix representation such that a deterministic relationship is produced between the data elements.

55. The system for structured document generation of claim 46, wherein the identifying relationships of the data structure comprise multiple-dependent relationships in which a child data element is directly related to a plurality of parent data elements and wherein the multiple-dependent relationships are resolved through the use of a traversal order to identify one or more deterministic relationships between the child data element and the plurality of parent data elements.

56. The system for structured document generation of claim 46, further comprising a database that stores the matrix representation.

57. The system for structured document generation of claim 56, wherein the database that stores the matrix representation comprises a fixed number of tables that do not increase as a function of the data structure complexity.

58. The system for structured document generation of claim 46, wherein the markup language comprises extensible markup language.