METHOD AND SYSTEM FOR EFFICIENTLY CONSTRUCTING AND CONSISTENTLY PUBLISHING WEB DOCUMENTS

• US 20030079178A1
• Filed: 04/01/1999
• Published: 04/24/2003
• Est. Priority Date: 04/01/1999
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: IYENGAR, ARUN K., REED, PAUL, CHALLENGER, JAMES R. H., WITTING, KAREN A., FERSTAT, CAMERON
• Application Number:
  US09/283,561
• Publication Number:
  US 20030079178A1
• Time in Patent Office: Days
• US Class Current: 715/501.1
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking

Abstract

A method, which may be implemented by employing a program storage device, for determining an order in which to construct objects, in accordance with the present invention, includes the steps of providing a plurality of objects, at least one of the objects including a relationship with another object in the plurality of objects, identifying at least one relationship between the plurality of objects, representing the at least one relationship between the plurality of objects using at least one graph, and traversing at least one graph to determine the order in which to construct objects in accordance with the at least one relationship and an update to at least one of the objects in the plurality of objects.

Claims

1. A method for determining an order in which to construct objects comprising the steps of:

providing a plurality of objects, at least one of the objects including a relationship with another object in the plurality of objects;

identifying at least one relationship between the plurality of objects;

representing the at least one relationship between the plurality of objects using at least one graph; and

traversing at least one graph to determine the order in which to construct objects in accordance with the at least one relationship and an update to at least one of the objects in the plurality of objects.

2. The method as recited in claim 1, wherein the step of representing the at least one relationship between the plurality of objects includes the step of representing objects in the plurality of objects by nodes and representing the at least one relationship by at least one connection between nodes.

3. The method as recited in claim 1, wherein the step of traversing at least one graph to determine the order includes the step of selecting the order based on one of performance and correct construction of the plurality of objects.

4. The method as recited in claim 1, wherein the step of traversing at least one graph to determine the order includes the step of traversing by employing at least one topological sort on the at least one graph.

5. The method as recited in claim 4, wherein the order is constructed from the at least one topological sort.

6. The method as recited in claim 1, further comprising the step of constructing objects based on the order.

7. The method as recited in claim 1, further comprising the step of publishing at least one of the plurality of objects.

8. The method as recited in claim 7, wherein all of the at least one of the plurality of objects are published together.

9. The method as recited in claim 7, wherein the step of publishing includes the steps of:

partitioning the at least one of the plurality of objects into a plurality of groups; and

publishing all objects belonging to a same group together.

10. The method as recited in claim 9 wherein the step of publishing all objects belonging to a same group together includes the step of:

for at least two of the plurality of groups, publishing all objects belonging to a first group before publishing any objects belonging to a second group.

11. The method as recited in claim 7, wherein the step of publishing includes the step of satisfying at least one consistency constraint.

12. The method as recited in claim 11, wherein the step of satisfying at least one consistency constraint includes the step of delaying publication of a first object until a second object which is referenced by the first object is published.

13. The method as recited in claim 12, wherein the first object and the second object include Web pages and a reference between the first and second objects includes a hypertext link.

14. The method as recited in claim 11, wherein the step of satisfying at least one consistency constraint includes the step of publishing two compound objects together if the compound objects are both constructed from at least one common changed fragment.

15. The method as recited in claim 1, wherein at least one of the plurality of objects is a Web page.

16. A method for publishing a plurality of objects comprising the steps of:

providing a plurality of objects, including compound objects;

partitioning at least some of the plurality of objects into a plurality of groups such that if two compound objects are constructed from at least one common changed fragment, then the compound objects are placed in a same group; and

publishing all objects belonging to a same group together.

17. The method as recited in claim 16, wherein the step of publishing includes the step of:

for at least two of the plurality of groups, publishing all objects belonging to a first group before publishing any objects belonging to a second group.

18. The method as recited in claim 16, wherein the step of publishing includes the step of:

delaying publication of a first object until a second object which is referenced by the first object is published.

19. The method as recited in claim 18, wherein the first and the second objects are Web pages and a reference between the first and the second objects is a hypertext link.

20. The method as recited in claim 16, further comprising the steps of:

representing objects by nodes on at least one graph; and

representing relationships between the objects by connections between the nodes.

21. The method as recited in claim 20, wherein the connections include an edge between two nodes representing compound objects if the two compound objects are constructed from at least one common changed fragment.

22. The method as recited in claim 20, wherein the connections include a directed edge from a first node representing a first object to a second node representing a second object, if the second object includes a reference to the first object.

23. The method of claim 20, further comprising the steps of:

determining if a first compound object and a second compound object embed at least one common changed fragment by;

topologically sorting at least part of a graph including dependence edges between objects;

determining changed fragments needed to construct a first object by;

examining the graph in an order defined by the topological sort; and

constructing a union between a second object and changed fragments needed to construct the second object for at least one edge which begins with the second object and terminates in the first object and for which the second object has changed.

24. The method as recited in claim 20 further comprising the step of performing a topological sort on at least part of the at least one graph for finding strongly connected components.

25. The method as recited in claim 24, further comprising the step of publishing a set objects belonging to a same strongly connected component, of the at least one graph, together.

26. The method as recited in claim 24, further comprising the steps of:

examining objects in an order defined by the topological sort;

when an unpublished object is examined, publishing the unpublished object together with all objects belonging to a same strongly connected component.

27. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for determining an order in which to construct a plurality of objects, the method steps comprising:

providing a plurality of objects, at least one of the objects including a relationship with another object in the plurality of objects;

identifying at least one relationship between the plurality of objects;

representing the plurality of objects and the at least one relationship between the plurality of objects using at least one graph; and

traversing at least one graph to determine the order in which to construct objects in accordance with the at least one relationship and an update to at least one of the objects in the plurality of objects.

28. The program storage device as recited in claim 27, wherein the step of graphically representing the at least one relationship between the plurality of objects includes the step of representing objects in the plurality of objects by a node and representing the at least one relationship by a connection between nodes.

29. The program storage device as recited in claim 27, wherein the step of traversing at least one graph to determine the order includes the step of selecting the order based on one of performance and correct construction of the plurality of objects.

30. The program storage device as recited in claim 27, wherein the step of traversing at least one graph to determine the order includes the step of traversing by employing at least one topological sort on at least part of the at least one graph.

31. The program storage device as recited in claim 30, wherein the order is constructed from the at least one topological sort.

32. The program storage device as recited in claim 27, further comprising the step of constructing the plurality of objects based on the order.

33. The program storage device as recited in claim 27, further comprising the step of publishing at least one of the plurality of objects.

34. The program storage device as recited in claim 33, wherein all of the at least one of the plurality of objects are published together.

35. The program storage device as recited in claim 33, wherein the step of publishing includes the steps of:

partitioning the at least one of the plurality of objects into a plurality of groups; and

publishing all objects belonging to a same group together.

36. The program storage device as recited in claim 35 wherein the step of publishing all objects belonging to a same group together includes the step of:

for at least two of the plurality of groups, publishing all objects belonging to a first group before publishing any objects belonging to a second group.

37. The program storage device as recited in claim 33, wherein the step of publishing includes the step of satisfying at least one consistency constraint.

38. The program storage device as recited in claim 37, wherein the step of satisfying at least one consistency constraint includes the step of delaying publication of a first object until a second object which is referenced by the first object is published.

39. The program storage device as recited in claim 38, wherein the first object and the second object include Web pages and a reference between the first and second objects includes a hypertext link.

40. The program storage device as recited in claim 37, wherein the step of satisfying at least one consistency constraint includes the step of publishing two compound objects together if the compound objects are both constructed from at least one common changed fragment.

41. The program storage device as recited in claim 27, wherein at least one of the plurality of objects is a Web page.

42. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for publishing a plurality of objects, the method steps comprising:

providing a plurality of objects, including compound objects;

partitioning at least some of the plurality of objects into a plurality of groups such that if two compound objects are constructed from at least one common changed fragment, then the compound objects are placed in a same group; and

publishing all objects belonging to a same group together.

43. The program storage device as recited in claim 42, wherein the step of publishing includes the step of:

for at least two of the plurality of groups, publishing all objects belonging to a first group before publishing any objects belonging to a second group.

44. The program storage device as recited in claim 42, wherein the step of publishing includes the step of:

delaying publication of a first object until a second object which is referenced by the first object is published.

45. The program storage device as recited in claim 44, wherein the first and the second objects are Web pages and a reference between the first and second objects is a hypertext link.

46. The program storage device as recited in claim 44, further comprising the steps of:

representing objects by nodes on at least one graph; and

representing relationships between the objects by connections between the nodes.

47. The program storage device as recited in claim 46, wherein the connections include an edge between two nodes representing compound objects if two compound objects are constructed from at least one common changed fragment.

48. The program storage device as recited in claim 46, wherein the connections include a directed edge from a first node representing a first object to a second node representing a second object, if the second object includes a reference to the first object.

49. The program storage device of claim 46, further comprising the steps of:

determining if a first compound object and a second compound object embed at least one common changed fragment by;

topologically sorting a graph including dependence edges between objects;

determining changed fragments needed to construct a first object by;

examining the graph in an order defined by the topological sort; and

constructing a union between a second object and changed fragments needed to construct the second object for at least one edge which begins with the second object and terminates in the first object and for which the second object has changed.

50. The program storage device as recited in claim 46, further comprising the step of performing a topological sort on at least part of the at least one graph for finding strongly connected components.

51. The program storage device as recited in claim 50, further comprising the step of publishing a set objects belonging to a same strongly connected component, of the at least one graph, together.

52. The method as recited in claim 50, further comprising the steps of:

examining objects in an order defined by the topological sort;

when an unpublished object is examined, publishing the unpublished object together with all objects belonging to a same strongly connected component.

53. A method for publishing a plurality of objects comprising the steps of:

providing a plurality of objects;

constructing at least one graph, the at least one graph including nodes representing objects and edges for connecting nodes having relationships, at least some of the edges being derived from at least one consistency constraint; and

finding at least one strongly connected component in the at least one graph.

54. The method as recited in claim 53, further comprising the step of publishing a set of objects belonging to a same strongly connected component group.

55. The method as recited in claim 53, further comprising the step of topologically sorting at least part of the at least one graph.

56. The method as recited in claim 55, further comprising the steps of:

examining objects in an order defined by topological sorting;

when an unpublished object is examined, publishing the unpublished object together with all objects belonging to a same strongly connected component.

57. The method as recited in claim 53, wherein one of the at least one consistency constraint includes delaying of a first object before a second object which is referenced by the first object is published.

58. The method as recited in claim 57, wherein the first and second objects include Web pages and at least one edge between the objects corresponds to at least one hypertext link.

59. The method as recited in claim 53, wherein an edge exists from a first object to a second object in at least one of the at least one graphs if the second object has a reference to the first object.

60. The method as recited in claim 53, wherein at least one of the consistency constraints includes publishing two compound objects together if the two compound objects are both constructed from at least one common changed fragment.