Modeling graphs as XML information sets and describing graphs with XML schema

• US 20040239674A1
• Filed: 06/02/2003
• Published: 12/02/2004
• Est. Priority Date: 06/02/2003
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Box, Donald F., Ewald, Timothy J., Pharies, Stefan H., Ballinger, Keith W., Gudgin, Martin
• Application Number:
  US10/452,696
• Publication Number:
  US 20040239674A1
• Time in Patent Office: Days
• US Class Current: 345/440
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/154 Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets

Abstract

Systems and methods for modeling graphs as XML information sets and describing them with XML schema. An edge labeled directed graph is converted to an edge labeled directed tree representing some of the edges directly and some of the edges indirectly. A graph is completely traversed such that all nodes are visited and all edges are traversed. Nodes are included by value initially and then by reference. A schema is provided that describes the structure of an XML tree than contains graph data.

Claims

1. A method for converting a graph to a tree, the method comprising:

traversing a graph having a plurality of nodes and a plurality of transitions that connect the plurality of nodes such that each node is visited at least once and each transition is traversed; and

during a traversal of the graph;

including a particular node of the graph in a tree by value if the particular node has not been visited before; and

and including the particular node of the graph in the tree by reference if the particular node has been visited before.

2. A method as defined in claim 1, further comprising constructing a table for storing node pairs, wherein each node pair includes a unique ID and a node reference.

3. A method as defined in claim 2, wherein including a particular node of the graph in a tree by value if the particular node has not been visited before further comprises determining that a node pair for the particular node is not in the table.

4. A method as defined in claim 2, wherein including a particular node of the graph in a tree by value if the particular node has not been visited before further comprises:

adding a node pair for the particular node to the table; and

marking a transition that led to the particular node with a global ID attribute having a value equal to the unique ID of the particular node.

5. A method as defined in claim 4, further comprising:

traversing transitions leaving the particular node; and

storing data contained in the graph node in a tree element.

6. A method as defined in claim 2, wherein including the particular node of the graph in the tree by reference if the particular node has been visited before further comprises determining that a node pair for the particular node is in the table of nod e pairs.

7. A method as defined in claim 6, wherein including the particular node of the graph in the tree by reference if the particular node has been visited before further CD comprises:

marking an element that represents the transition that led to the particular node with a global REF attribute having a value equal to a unique ID of the particular node as stored in the table; and

not traversing transitions leaving the particular node.

8. A method as defined in claim 1, further comprising marking an element that represents a transition that does not lead to any node with a nil attribute whose value is true.

9. A method for converting a graph to a tree, the method comprising:

creating a table for storing pairs that is initially empty, wherein each pair includes a unique ID and a node reference for a node;

during a traversal of a graph, determining if a particular transition leads to a node that is already represented in the table by a particular pair;

if the node is not represented in the table by a particular pair then;

assigning a unique ID to the node;

adding a new pair to the table, wherein the new pair includes the unique ID and a node reference to the node; and

marking an element that represents the particular transition with a global ID whose value equals the unique ID of the node; and

if the node is represented in the table, then marking the element representing the particular transition with a global ref attribute whose value is the unique ID of the node as represented in the pair in the table.

10. A method as defined in claim 9, wherein marking an element that represents the particular transition with a global ID whose value equals the unique ID of the node further comprises storing data contained in the node in a tree element.

11. A method as defined in claim 10, wherein marking an element that represents the particular transition with a global ID whose value equals the unique ID of the node further comprises traversing directed edges leaving the node.

12. A method as defined in claim 9, wherein marking the element representing the particular transition with a global ref attribute whose value is the unique ID of the node as represented in the pair in the table further comprises not traversing transitions that leave the node.

13. A method as defined in claim 9, further comprising marking an element of the tree representing an edge that does not lead to a graph node with a global nil attribute having a value of true.

14. A method as defined in claim 9, further comprising representing the tree in XML.

15. A method as defined in claim 14, further comprising converting the tree represented in XML to a graph.

16. A method for converting a tree to a graph, the method comprising:

constructing a table for storing pairs that is initially empty, wherein each pair includes a unique ID and a node reference;

while traversing a particular transition in a tree, examining a particular element led to by the particular transition;

constructing a new graph node if a particular tree element has a global ID attribute that identifies a graph node directly;

if the particular tree element has a global REF attribute that identifies a graph node indirectly, then attaching a referenced graph node to a directed edge that has a name that is the same as a name of the particular tree element;

if the particular tree element has a global nil attribute then attaching a null reference to the directed edge that has the same name as the particular tree element; and

if the particular element does not have the global ID attribute, the global REF attribute or the global nil attribute, then the particular element does not lead to a graph node.

17. A method as defined in claim 16, wherein constructing a new graph node if a particular tree element has a global ID attribute that identifies a graph node directly further comprises adding a new pair to the table that corresponds to the particular tree element.

18. A method as defined in claim 16, wherein constructing a new graph node if a particular tree element has a global ID attribute that identifies a graph node directly further comprises storing data contained in the particular element in the new graph node.

19. A method as defined in claim 18, wherein constructing a new graph node if a particular tree element has a global ID attribute that identifies a graph node directly further comprises attaching the new graph node to a transition that has the same name as the particular element and is leaving a graph node identified by a parent element of the particular tree element.

20. A method as defined in claim 16, wherein attaching a referenced graph node to a directed edge that has a name that is the same as a name of the particular tree element further comprises attaching the new graph node to a transition that has the same name as the particular tree element and is leaving a graph node identified by a parent element of the particular tree element.

21. A method as defined in claim 16, wherein examining a particular element led to by the particular transition further comprising determining if the particular element is represented by a particular pair in the table.

22. A data structure for representing graph data as a tree, the data structure comprising:

one or more elements, wherein content of each element is optional;

a first attribute reference to a global ID attribute that is optional; and

a second attribute reference to a global ref attribute that is optional.

23. A data structure as defined in claim 22, further comprising an element content sequence.

24. A data structure as defined in claim 22, wherein the global ID attribute and the global ref attribute are mutually exclusive.

25. A data structure as defined in claim 24, wherein the data structure does not does not include a global ID attribute if the data structure includes a global ref attribute.

26. A data structure as defined in claim 24, wherein the data structure does not includes the global ref attribute if the data structure includes a global ID attribute.

27. A schema for defining an Infoset that contains graph data, the schema comprising:

one or more complexTypes, wherein at least one complexType includes;

a content sequence that includes one or more elements, each element having a type; and

a global ID attribute and a global ref attribute that are mutually exclusive such that use of the global attribute excludes use of the global ref attribute and use of the global ref attribute excludes use of the global ID attribute for a particular instance of the schema.

28. A schema as defined in claim 27, wherein each complexType has a name.

29. A schema as defined in claim 27, wherein a minimum occurrence constraint of the content sequence is zero.

30. A schema as defined in claim 29, wherein the content sequence includes one or more elements, wherein content of each element is optional.

31. A schema as defined in claim 27, wherein a use constraint of the global ID attribute is optional.

32. A schema as defined in claim 27, wherein a sue constraint of the global ref attribute is optional.

33. A schema as defined in claim 27, wherein an element declaration may be marked nil and a declaration nil attribute may be true.

34. A computer program product for implementing a method for converting a graph to a tree, the computer program product comprising:

a computer readable having computer executable instructions for implementing the method, the method comprising;

traversing a directed graph such that each node is visited at least once;

when a node in the directed graph is visited, determining if the node is being visited for the first time;

creating an element in a tree if the node is being visited for the first time, wherein an edge leading to the node is assigned to the element and the element is marked with a global ID attribute; and

if a node in the directed graph is being visited for a time that is not the first time, adding an element to the tree that is marked with a global ref attribute to correspond to the node.

35. A computer program product as defined in claim 34, the method further comprising constructing a table correlating nodes to global ID attributes, wherein an entry is made into the table each time that a node is visited for the first time.

36. A computer program product as defined in claim 35, the method further comprising:

assigning a unique ID to a node of a node is not in the table;

marking an element representing the node with the global ID attribute whose value is the unique ID of the node; and

storing data in the node in a tree element.

37. A computer program product as defined in claim 35, the method further comprising:

marking an element that leads to a particular node with a particular global ref attribute if the particular node is in the table; and

not traversing transitions leaving the particular node.