Abstract:
A method and apparatus for relating (called hyperlinking) a region of one document to one or more regions of other documents. This is provided by using a mechanism for linking and embedding objects to establish the endpoints of the hyperlinks (called anchors) together with the creation of intermediate tables which maintain information about relations between regions of documents and attributes of the relationship. When a user selects a region in a document which participates in a relationship, a database program is invoked which displays information about related regions in other documents which may be accessed through the intermediate tables. An auxiliary table maintains information about attributes which may be custom designed by the user, such as author, date of creation, etc. The intermediate tables allow relationships among multiple regions of documents created by different applications. Relationships are bidirectional in that the user can traverse from any region in a document to any other region in the same relationship.

Description:
This is a continuation of application Ser. No. 08/540,322, filed Oct. 20, 1995, now abandoned, which is a continuation of application Ser. No. 07/999,110, filed Dec. 30, 1992, abandoned. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention presents a mechanism for establishing and maintaining associations among information residing in documents stored electronically in computer systems. More specifically, this invention presents a method of relating and maintaining arbitrary relationships among electronic documents created and updated by separate application programs. 
     2. Background Information 
     Definitions 
     We define an application program (or simply, application) as software that is not part of the underlying computer&#39;s operating system and performs a collection of related functions on behalf of users and under their control. Application programs allow users to create and manage different kinds of information. Examples of applications include spreadsheets, word processors, drawing packages, presentation graphics, and others. Applications can be characterized by a user interface, that is, the way in which users interact with the application, a data storage scheme, that is, the way in which the application stores its data, and the internal manipulations and transformations that the application applies to the data. In general, applications that fall in the same category have similar behavior but differ in their user interfaces, their data storage schemes, and their internal transformations, for example, there are several dozen word processing programs currently available. 
     We will use the term document to refer to the data users create using an application program. Users retrieve, manipulate and save the contents of a document using the same application that they used to create the document in the first place. Example documents include spreadsheets created by spreadsheet programs, reports created by word processors, and others. 
     A link is an arbitrary association, between a document or portion of a document and another document or portion of another document. A hyperlink is an association between a document or portion of a document and a collection or documents or portions of documents. A collection of such hyperlinks can be viewed to form a mathematical structure called a hypergraph. Neilsen, Jakob; Hypertext &amp; Hypermedia; Academic Press; 1990 (&#34;Neilsen 1990&#34;), Ullman, Jeffrey D.; Principles of Database Systems; Computer Science Press; 1980. If multiple documents (or portions of documents) have the same labeled links with a single document (or portion of a document) then those links are in reality a hyperlink. In this discussion, we will use the two terms link and hyperlink interchangeably, since in general, it is possible to represent a hyperlink as a collection of links and a link is simply a degenerate case of a hyperlink. The term hyperlink emphasizes the potential for multiple connections. 
     Motivation for the Present Invention 
     It has been long recognized that one of the major advantages of managing documents electronically lies in the ability to establish and maintain arbitrary associations between the various stored documents. Bush, Venevar; As We May Think; in Atlantic Monthly, July 1945. (Reprinted in CD-ROM--The New Papyrus, pp. 101-108, Lambert &amp; Ropiequet (eds.), Microsoft Press, 1986), Nelson, Ted; Computer Lib/Dream Machines; T. Nelson self-Published; 1974. Revised edition published by Microsoft Press 1980. For example, a document describing Hillary&#39;s first ascent of Everest might be related to treatises on the geography of the Khumbu glacier region, to sociology studies of the Sherpas, to socioeconomic studies of the effects of tourism on the local cultures, to the impact of siege-style climbing on the environment, and many others. All such associations would be represented in terms of the previously mentioned hyperlinks. Readers of any one of these cross-linked documents would be able to follow the links and open another document to the relevant passage 1 . For example, while reading about the use of bottled oxygen by the climbers, a user could, by invoking simple user interface commands or gestures such as pressing a button or selecting from a pull-down menu, open a study on oxygen debt incurred by high altitude climbers. This would be possible without burdening the user with following the path to the related document nor finding the application needed to view it. 
    
     The current state of the art in computer science has yielded a class of applications known as hypertext systems (Neilsen 1990) that allow such connections or associations to be established among electronic documents. Unfortunately, the current state of the art suffers from several major shortcomings: restricted support, monolithic applications, and monolithic environments. 
     Restricted support includes those hypertext systems that can not establish links among some classes of documents. For example, many hypertext systems can only link documents consisting of ASCII text. Such systems include Unix Guide from Owl International, and the Gnu TechInfo system. 
     Monolithic applications are those in which users not only establish links but also create and edit the documents from within the same application. Such systems combine word processing, drawing, and other capabilities with the linking tools in order to provide users with a single environment in which to perform all document management and linking tasks. The drawback is that users are confined to the system&#39;s own document editors (word processors, drawing tools, etc.) which will frequently differ from the ones most commonly used. Alternatively, users can create documents with their favorite tools and then import the documents into the hypertext system. However, under this scenario, any further changes to the document must be made within the hypertext system, or the document must be edited outside the system and re-imported, in which case all linking information is lost. Examples of such systems include Toolbook from Asymetrix, Hypercard from Apple Computer, Notecards (Halasz, F. G., Moran, T. P., and Trigg, R. H.; &#34;NoteCards in a nutshell&#34;, Proc. ACM CHI+GI&#39;87; 1987), KMS (Aksyn, R. M., McKracken D. L., Yoder, E. A.; &#34;KMS: A distributed hypermedia system for managing knowledge in organizations&#34;, in Communications of the ACM; Vol 31, No. 7; 1988), Intermedia (Yankelovich, N., Haan, B. J., Meyerowitz, N. K., and Druker, S. M.; &#34;Intermedia: The Concept and the Construction of a Seamless Information Environment&#34;; in IEEE Computer, January 1988) (&#34;Yankelovich, 1988&#34;), and many others. 
     Monolithic environments are computer operating environments that provide a complete suite of applications tailored to the environment. As in the case of monolithic applications, monolithic environment force users to adapt to those applications provided with the environment. However, unlike monolithic applications, users typically can not import documents created with their customary applications because those applications are unlikely to be available in the environments. Example environments include the Andrew system. Morris, J. H.; &#34;Make or Take&#34; Decisions in Andrew; in Proc. Winter Usenix Technical Conference; February 1988 and the Penpoint Operating System from Go Corp. 
     The purpose of this invention is to overcome the deficiencies of the existing state of the art by allowing users to establish and maintain links and hyperlinks among documents without requiring them to change the applications that manage their documents or to change the operating environment in which they do their computer-related work. This is done by an innovative and synergistic combination of two existing technologies: a mechanism for embedding and linking objects within documents and database management. Linking and embedding objects allow documents to contain data that are foreign and maintained by other applications. Database management technology provides general mechanisms for maintaining structured data in terms of homogeneous records and fields. Date, C. J.; An Introduction to Database Systems; Addison-Wesley Publishing Co.; 1981. 
     A general architecture for supporting hyperlinking has at least two components: a way to manage the endpoints of the links (called anchors in the hypertext literature (Yankelovich, 1988; Neilsen, 1990), and a way to associate the anchors to form the links themselves. This patent application will describe embedding and linking of objects within documents to implement anchors and database technology to implement the links. 
     One prior art system for linking and embedding is provided by the OLE (Object Linking and Embedding) system available from Microsoft Corporation of Redmond, Wash. Before proceeding to the remainder of this discussion, it will be necessary to provide an overview of OLE and its limitations with respect to hyperlinking. 
     OLE provides a mechanism where certain documents called container documents (or client documents in OLE jargon) can contain information created by applications different from those used to create the client document. Microsoft Windows Users Guide; Microsoft Corp.; 1992. As the name implies, OLE supports two different types of containment: embedding and linking. When the foreign data is embedded in a client document, it physically resides within the document. When the foreign data is linked into the client document, only a reference to the foreign data resides in the client. The contents comprising the foreign data usually reside elsewhere, typically in another electronic file in the file system. This difference is shown pictorially in FIG. 1. 
     FIG. 1 shows two views 100 and 150 of a client document (labeled &#34;client document&#34;). On the left hand side, 100 is a view as might be seen by a user, on the right hand side, an internal representation 150 as might be seen by the application managing the document. The user will see 120 and 130 as part of document 100. The application will see the embedded table 160 stored with the client document&#39;s native data 140, whereas an OLE link stores a pointer 170, or reference to a section within the document 175 containing the graph data 176. 
     The significant feature of OLE is that applications that manage client documents (called client applications) need not have the capability to manipulate the foreign data that is embedded or linked into the client documents. The foreign data &#34;encapsulates&#34; sufficient information to allow the OLE libraries to invoke the appropriate applications (called server applications) whenever the user wishes to alter any part of the document, whether it is native or foreign. If the part of the document to be edited is native, the user merely edits it using the tools and interface provided by the client application. If the information is foreign, the OLE libraries invoke the appropriate application with which the user then alters the foreign data. This mechanism is shown pictorially in FIG. 2. 
     FIG. 2 shows what happens when a user edits contained data. The client application realizing that the data to be edited is foreign calls the OLE libraries. They in turn, extract the information from the contained objects (a graph and a table, in this case) and invoke the appropriate editors. If the contained data is a link as in the case of the graph 170, the link contains a reference 165 to the file 175 where the graph data 176 resides. The data residing in that file is the one the user manipulates via the graph editor. If the data is embedded, it is copied to a temporary storage area 200 and then loaded into the server application. 
     OLE containment, whether via linking or embedding is not sufficient for hyperlinking documents for two important reasons: OLE connections are unidirectional and unitary. Unidirectionality of OLE connections means that the linked data does not contain information that records all of the places where it is contained. Thus the connection is strictly one way, from the container (or client) to the contained (or server). If the containment is through embedding, there is no way to reach the embedded data through a path other than the container. If the containment is through linking, there is no way to access the client document in which the link is contained from the server document. 
     A hyperlink is bi-directional, meaning it can be traversed in either direction from either anchor. For instance, in the earlier example, a document describing the 1954 British climbing expedition to Mt. Everest might have a hyperlink between Tenzing Norgay (Hillary&#39;s summit climbing partner) and his nephew Nawang Gombu (who accompanied Jim Whittaker in the first U.S. ascent of the mountain in 1963). Readers would be able to follow the link originating from a document describing either the U.S. or British expedition. Furthermore, as discussed earlier, hypertexts consist of hyperlinks, meaning the links can have multiple endpoints. Thus an anchor in one document may be linked to anchors in several document via the same link. For example, the route taken by the British expedition in 1954 (South Col) has been used by many subsequent expeditions. This relationship could be represented by a single hyperlink connecting all documents describing expeditions that followed that route. Both of these features of hypertext links (bidirectionality and multiplicity) are shown in FIG. 3. 
     FIG. 3 shows the bidirectionality of hyperlinks. If a reader of the U.S. Expedition document 310 wishes to follow the &#34;relatives of&#34; link 301, she will be taken to the British Expedition document 300 in the passage 302 describing Tenzing Norgay. Similarly, readers will open the U.S. Expedition document 310 when they follow the &#34;relative of&#34; link 301 from the British Expedition document 300. The figure also shows a hyperlink 311 connecting all documents 300, 310 and 320 describing expeditions that followed the South Col route. When readers wish to follow that link, they must specify which document (usually from a list of candidates which in this case would include all three documents 300, 310 and 320) they wish to open. 
     SUMMARY AND OBJECTS OF THE INVENTION 
     One of the objects of the present invention is to provide a mechanism that supports the establishment of arbitrary relationships (links) among a variety of documents or portions of documents without editors specially written to support such linking. 
     Another of the objects of the present invention is to provide a method for nonbinary linking of a variety of documents, that is, hyperlinks are allowed. 
     Another of the objects of the present invention is to provide a method for multidirectional linking of a variety of documents, that is, their traversal can begin from any endpoint. 
     Another of the objects of the present invention is to provide a method for linking a variety of document wherein links can have attributes with which they are associated. These attributes are used to help users determine which links are to be traversed. 
     These and other objects of the present invention are provided for by linking and embedding objects in documents to implement anchors, with database management technology to relate anchors to links and links to anchors. Specifically, in one embodiment, anchors are inserted, edited, and removed from documents using linking and embedding mechanisms. Additionally, database tables are used to manage anchors and hyperlinks, and to associate anchors with hyperlinks. The detailed description below provides one possible realization of this architecture. The essential characteristics of the implementation, as claimed by the invention, are that from an anchor a set of associated hyperlinks is determined using database technology, and from a hyperlink a set of associated anchors is determined using database technology. Furthermore, such anchors can be inserted into any document created by an application which is compliant with systems permitting embedding and/or linking of objects (e.g. OLE from Microsoft). The application need not be aware that its documents participate in any hyperlinks. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention is illustrated by way of example and not limitation in the figures of the accompanying in which like references indicate like elements and in which: 
     FIG. 1 shows a prior art method of linking and embedding documents. 
     FIG. 2 shows a prior art method of editing linked and embedded documents. 
     FIG. 3 shows a prior art method of hypertext linking of documents. 
     FIG. 4 shows a computer system upon which the methods and apparatus of the preferred embodiment may be implemented. 
     FIG. 5 shows linking documents according to the method of the preferred embodiment. 
     FIG. 6 shows the hyperlinks table used in the preferred embodiment. 
     FIG. 7 shows the connections table used in the preferred embodiment. 
     FIG. 8 shows the attributes table used in the preferred embodiment. 
     FIG. 9 shows a flow diagram of a process used when a user desires to traverse a link. 
     FIG. 10 shows a flow diagram of a process used for associating anchors with hyperlinks. 
    
    
     DETAILED DESCRIPTION 
     The present invention is related to improved methods of linking data. In the following description, for the purposes of explanation, specific types of data, applications, data structures, pointers, indices, and formats are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art, that the present invention may be practiced without these specific details. In other instances, well-known structures and data are shown in block diagram form in order to not unnecessarily obscure the present invention. 
     Referring to FIG. 4, the computer system upon which the preferred embodiment of the present invention is implemented is shown as 400. 400 comprises a bus or other communication means 401 for communicating information, and a processing means 402 coupled with bus 401 for processing information. System 400 further comprises a random access memory (RAM) or other dynamic storage device 404 (referred to as main memory), coupled to bus 401 for storing information and instructions to be executed by processor 402. Main memory 404 also may be used for storing temporary variables or other intermediate information during execution of instructions by processor 402. Computer system 400 also comprises a read only memory (ROM) and/or other static storage device 406 coupled to bus 401 for storing static information and instructions for processor 402, and a data storage device 407 such as a magnetic disk or optical disk and its corresponding disk drive. Data storage device 407 is coupled to bus 401 for storing information and instructions. Computer system 400 may further be coupled to a display device 421, such as a cathode ray tube (CRT) coupled to bus 401 for displaying information to a computer user. An alphanumeric input device 422, including alphanumeric and other keys, may also be coupled to bus 401 for communicating information and command selections to processor 402. An additional user input device is cursor control 423, such as a mouse, a trackball, or cursor direction keys, coupled to bus 401 for communicating direction information and command selections to processor 402, and for controlling cursor movement on display 421. Another device which may be coupled to bus 401 is hard copy device 424 which may be used for printing instructions, data, or other information on a medium such as paper, film, or similar types of media. Of course, system 400 may further be coupled to a network wherein file sharing (including the sharing of documents containing links) between nodes in the network may be accomplished for large shared hypertext systems. 
     In the preferred embodiment, computer system 400 is one of the IBM-type AT computers commercially available. Processor 402 is one of the Intel 80×86 family of microprocessors, such as the i386™ or i486™ (trademarks of Intel Corporation) manufactured by Intel Corporation of Santa Clara, Calif. This mechanism will work in any environment that supports object linking and embedding and database management systems. In a preferred embodiment, the DOS 5.0 brand operating system, Windows 3.1 and/or Windows for Workgroups brand operating environments are used, however, it can be appreciated by one skilled in the art that other systems having capabilities for object embedding and linking and database technology may be used in alternative embodiments. 
     In the preferred embodiment, hyperlinks, as described above, are implemented via four database tables. These are described in detail below. The first table represents the anchors, that is the endpoints of the hyperlinks. The rows in the anchors table include at least two fields: an internal identifier through which the system references the anchor, and a link to the container document (in a preferred embodiment, the link is created using the OLE brand object linking and embedding system available from Microsoft Corporation of Redmond, Wash., however, it can be appreciated by one skilled in the art that other mechanisms for linking and embedding objects in documents and maintaining those links can be used in alternative embodiments, e.g., the NewWave brand system available from Hewlett-Packard). The anchor object represented by a row in the table is embedded using OLE into the document to be hyperlinked. This is shown pictorially in FIG. 5. The dual use of OLE connections for a single anchor overcomes the limitations of the unidirectionality of OLE connections. The embedded anchor object allows the hyperlink application to be activated when users initiate a link traversal. The OLE link from the table entry to the anchor region in the document allows the hyperlink manager to open the appropriate document upon completion of a link traversal. 
     FIG. 5 shows the internal representation of hyperlink anchors used in the preferred embodiment. Each row (e.g. 591-595) of the table represents an OLE object that is embedded in a client document in the portion (e.g. 503, 504, 532, 573 and 574) corresponding to the anchor&#39;s location. That is shown as an arrow from the document (e.g. 501, 502, 531, 571, and 572). The portion of the document corresponding to the anchor&#39;s location is referenced in the database table as an OLE link (e.g. 505, 506, 535, 575, and 576). The anchor identifiers (e.g. 591a-595a) are generated automatically by the system, their actual value is immaterial, the only constraint is that different anchors have different ids. The arrows indicate directionality of hyperlink traversal, OLE embedding is used to initiate a hyperlink traversal, and the OLE link is used to complete a hyperlink traversal. 
     The second table is the hyperlinks table, holding information regarding each hyperlink. The rows in the hyperlinks table include at least an internal identifier through which the link can be referred by the system and an external identifier or name that is meaningful to users. This is shown pictorially in FIG. 6 discussed below. 
     FIG. 6 shows the Hyperlinks table 600 used in the preferred embodiment. Each row (e.g. 601, 602 . . . ) corresponds to a single hyperlink and is independent of the number of anchors that participate in the hyperlink. There may be additional information included in the table (e.g. in fields 630), such as hyperlink types, etc. in alternative embodiments, but for the purposes of this invention, only the two fields 610 and 620 are used. 
     The associations between anchors and hyperlinks is represented by a third table, the Connections table 700. Each entry in the Connections table includes both a link ID 710 and an anchor ID 720, indicating a single connection between anchor and link. There can be multiple rows (e.g. 730-732 or 741-742) with the same link ID, as well as multiple rows with the same anchor ID. This permits an anchor to participate in multiple hyperlinks and hyperlinks to connect to multiple anchors. As shown in the example above (FIG. 3), three anchors participate in the hyperlink 311 labeled &#34;South Col Route&#34;. The table may be indexed by either ID 710 or 720 to permit enumerating the hyperlinks associated with an anchor or the anchors associated with a hyperlink. The Connections table is shown pictorially in FIG. 7 discussed below. 
     FIG. 7 shows the Connections table 700. Each row (e.g. 730-732 and 741-742) corresponds to the association between an anchor and a hyperlink. The set of all such associations for a given link ID indicates all anchors connected with that hyperlink, that is, a set of anchors that are all linked to one another. Similarly, the set of all such associations for a given anchor ID indicates all hyperlinks in which the anchor participates. Table values shown above correspond to the values in the tables in FIGS. 5 and 6 above, showing the connections between the anchors (table 590) and the hyperlinks (table 600). 
     The fourth database table 800 in this embodiment manages arbitrary attributes associated with links. It is not essential for the maintenance of hyperlinks, however it is frequently useful to have such attributes, for they can store such information as the link&#39;s owner 811, the date in which it was established, etc. The attributes table is shown pictorially in FIG. 8 described below. 
     FIG. 8 shows the link attributes table. Each row (e.g. 810-814) corresponds to an attribute-value pair for a single link. Link 1 (the South Col Route link) has two attributes, an owner (Larson) 810 and a creation date 811. Link 2 (the Relatives Of link) has three attributes, an owner (Kogan) 813, a creation date 814, and a date when the link was last changed 812. 
     The first three database tables work together to provide the bidirectional, multiway linking (or hyperlinking) that is desired. The manner in which they work is explained below and pictorially in the flowchart of FIG. 9. 
     As shown in FIG. 9, the user selects an anchor at step 901 using the selection mechanisms available to the document&#39;s editor. The hyperlink manager is invoked via OLE and the anchor&#39;s identifier is determined from the database table entry corresponding to the anchor&#39;s OLE object. A database query determines whether the anchor participates in more than one hyperlink at step 902. If so, the user interactively selects one at step 903. Once a hyperlink is selected, the number of candidate anchors to which the traversal can complete is determined. If there is only one, the traversal completes without user interaction at step 904, otherwise, the user selects one at step 905 and the traversal completes at step 906. The actual opening of the target document, in which the target anchor is embedded, is achieved via OLE linking. 
     When a user opens a document that participates in a hypertext link (that is, it has incoming or outgoing links), the endpoints of the hyperlinks will be visible as anchors in this embodiment. Selecting one of the anchors will, upon user command 2  invoke the hyperlink application because anchors are OLE objects. The hyperlink manager will determine the anchor&#39;s identifier by table lookup in the Anchors table and then determine the links in which the anchor participates using the connections table. If the anchor participates in only one link (as in the case of the anchors in the Mt. Everest example), a link traversal is initiated. Otherwise the hyperlink manager presents to the user a list of all hyperlinks in which the anchor participates. Once the user chooses one of the hyperlinks, a link traversal is initiated. The set of hyperlinks in which the anchor participates is determined via a selection operation on the connections table and a join between that selection and the Hyperlinks table. The pseudo-SQL code to achieve this is shown below: 
    
     
         ______________________________________select link name from Hyperlinks, Connectionswhere Participant.sub.-- Anchor.sub.-- ID = &lt;the identifier of the anchorthe userselected&gt; ANDHyperlinks.Link.sub.-- ID = Connections.Link.sub.-- ID______________________________________ 
    
     To complete a link traversal, the hyperlink manager determines the possible anchors to which the traversal could go. If there is only one, the traversal is completed using that one anchor, otherwise, the hyperlink manager presents to the user the set of possible anchors to which the traversal can complete. To determine the set of all participant anchors in a hyperlink, the link manager performs a compound selection on the connections table to select only those anchors that participate in the selected hyperlink and do not equal the original anchor (the one selected by the user to initiate the process). The pseudo SQL to achieve this is shown below: 
     
         ______________________________________select anchor.sub.-- ID from Connectionswhere Participant.sub.-- Anchor.sub.-- ID &lt;the identifier of the anchorthe userselected&gt; ANDLink.sub.-- ID = &lt;the identifier of the link that initiates thistraversal&gt;______________________________________ 
    
     When the destination anchor is determined, link traversal finishes by following the OLE link from the anchor to the linked document. 
     The process of establishing a hyperlink is described with reference to FIG. 10. As shown in FIG. 10, the user selects an anchor using the selection mechanisms available to the document&#39;s editor at step 1001. The hyperlink manager is invoked via OLE and the anchors identifier is determined from the database table entry corresponding to the anchor&#39;s OLE object. The hyperlink manager determines whether the user is creating a new hyperlink or adding the selected anchor to an existing one at step 1002. If the user is creating a new hyperlink, the system prompts the user for all necessary information, e.g., hyperlink name at steps 1003 and 1004. Finally, the system establishes the connection between the selected anchor and the hyperlink at step 1006. If it is an existing hyperlink, it is selected at step 1005. 
     Establishing a connection between two anchors, i.e., those in two distinct documents, is achieved by connecting both anchors to the same hyperlink. This is done using the same method shown in FIG. 10 above once for each anchor. 
     The mechanism described above provides a way to establish and manage hyperlinks among different documents. This mechanism will work with any document whose application conforms to the OLE standard 3 . No other assumptions or restrictions are necessary. Users will not need to adapt to different applications in order to make use of this hyperlinking 4  mechanism and they will not be hampered by the limitations imposed by the OLE standard. 
    
    
     Thus, an invention for creating and maintaining links among heterogeneous documents has been described. Although the present invention has been described particularly with reference to specific data structures, processes, etc., it may be appreciated by one skilled in the art that departures and modifications may be made by one of ordinary skill in the art without departing from the general spirit and scope of the present invention.