Abstract:
A system for linking elements representing stored information in a data base comprising a link structure formed in a section of the data base independent of the elements, a pointer in the link structure indicating the location of a first element, and a second pointer in the link structure indicating the location of a second element. The data base contains items comprising textual data and a plurality of categories into which the items may be categorized such that each item may be linked to more than one category. The invention automatically assigns an element in a data base to a parent category if it has been assigned to a child category of the parent. The invention will allow a user to modify data in a data base in a view mode, and will resolve ambiguities by guessing as to the most likely interpretation intended by the user. The invention will allow a user to change the number or organization of categories in the data base while the user is in a view mode.

Description:
BACKGROUND OF THE INVENTION 
     This invention relates to the organization of and access to information stored in a computer system. 
     Computer systems frequently organize data into categories, usually called fields, each category having a number of items of information. The categories can be arranged in a hierarchical structure such that each category may include a &#34;parent&#34; category, one or more &#34;sibling&#34; categories, and one or more &#34;children&#34; categories. For example, a category called &#34;Companies&#34; may have as its children the categories &#34;Financial Information&#34; and &#34;Personnel&#34;, and Personnel could have &#34;Name&#34;, &#34;Address&#34; and &#34;Salary&#34; as its children. In this example, Financial Information and Personnel are sibling categories since they both have the same parent category, i.e., Companies. Similarly, Name, Address and Salary are siblings with Personnel as the common parent. The category hierarchy can continue to many levels or &#34;generations.&#34; 
     Items are specific textual information such as a single word or several lines of text. Items appear in fields (i.e., under one of the available categories). Using the above example, the names of specific companies would appear under the category Company. Similarly, specific names of employees are under the category Names. 
     Prior art systems generally operate in two distinct modes, a data entry mode and a report writer or view mode. As its name implies, the data entry mode is used when data is to be entered, deleted or modified in any way. The user directly accesses the files in the data base and makes the desired changes. 
     SUMMARY OF THE INVENTION 
     The invention features a system for linking elements representing stored information in a data base, the system comprising: a link structure formed in a section of the data base independent of the elements; a pointer in the link structure indicating the location of a first element; and a second pointer in the link structure indicating the location of a second element. The first element belongs to a first group of elements and the second element belongs to a second group of elements. In the preferred embodiment the system includes a plurality of independent link structures, each of which has a pointer indicating the location of an element in the first group and a pointer indicating the location of an element in the second group. The first group of elements can represent items and the second group can represent categories. The elements are represented by objects, and each object includes a pointer indicating a location of a link structure. Link structures that include pointers to the same element form a chain of link structures, with each member of the chain indicating the location of the preceding and following members. 
     The invention also generally features a system for assigning an element in a data base to one or more of a plurality of categories, the categories hierarchically arranged such that each category may have one parent category and a predetermined number of children categories, the system comprising: means for assigning the element to a category in response to information input by a user; and means for automatically assigning the element to a second category, the second category being the parent category of the category to which it was assigned by the means for assigning. In the preferred embodiment the system further comprises means for automatically assigning the element to a third category, the third category being the parent category of the second category. 
     The invention also generally features a system for modifying data in a data base comprising: means for presenting data to a user in a view mode, the view mode providing a view comprising a compilation of selected portions of the data base that satisfy one or more criteria; means for receiving information input by the user through the view mode specifying a desired modification to the data being viewed; and means for modifying the data base in accordance with the input information. In the preferred embodiment the means for modifying the data base resolves ambiguities introduced by the received information by guessing as to the most likely interpretation intended by the user by utilizing data related to the data to be modified to resolve the ambiguities, the related data being data immediately adjacent to or preceding the data to be modified in the view. 
     The invention generally features a system for modifying a category structure of a data base, the category structure comprising a plurality of categories, the system comprising: means for presenting the data to a user in a view mode, the view mode providing a view comprising a compilation of selected portions of the data base that satisfy one or more criteria; means for receiving information input by a user through the view mode specifying a desired change to the category structure; and means for modifying the category structure in accordance with the input information. The desired change may comprise adding or deleting a category. The categories are arranged in a category hierarchy and the desired change may comprise moving a category within the hierarchy. 
     The invention further generally features a system for organizing data in a data base comprising: a plurality of items, the items comprising textual data; a plurality of categories into which the items may be categorized; and means for linking items to selected categories such that each item may be linked to more than one category. Each category can be linked to more than one item. In the preferred embodiment the system further comprises means for linking one of the categories to another of the categories. 
     The invention also generally features a system for modifying data in a data base comprising: means for receiving information input by a user specifying a desired modification to the data; means for modifying the data in response to the received information; means for identifying data in the data base that is related to the data modified by the means for modifying; and means for modifying the identified data in accordance with the received information. If the received information specifies a category to be modified within the data base, the means for identifying identifies categories related to said modified category. If the received information identifies information to be modified within a specified category, the means for identifying identifies categories that contain the information to be modified. 
     The invention provides a user with much greater flexibility in modifying and managing data than any system available in the prior art. Through the use of the unique link structures, items may be easily linked to many different categories, in contrast to prior art systems where items were in fields under specific categories. Items therefore exist independently of categories allowing much greater flexibility as explained more fully below. Users modify data through a view, and the system resolves ambiguities using available information to determine the most likely intent of the user. The data structure of the invention also allows side effects to be quickly resolved. The use of subsumption to automatically assign an item to the parent category of a category to which the item is directly assigned by the user further improves the performance of the system. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates a category hierarchy used in accordance with the invention. 
     FIG. 2 is a diagrammatical representation of the linking of items to categories. 
     FIGS. 3A and 3B illustrate the storage of data in a data base. 
     FIG. 4 is a combination of the diagrams illustrated in FIG. 1 and FIG. 2. 
     FIG. 5 is a diagrammatical representation of the linking of categories to views. 
     FIG. 6 is a diagrammatical representation of the linking of categories to categories. 
     FIG. 7 is a flowchart illustrating the modification of data in a data base. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The invention is embodied in software commercially available under the registered trademark &#34;Agenda&#34;, produced by Lotus Development Corporation of Cambridge, Mass., which has published the following documentation and software for Agenda®, incorporated herein by reference: Lotus Agenda User&#39;s Guide, Lotus Agenda Tutorial, Lotus Agenda Sample Applications, Lotus Agenda Definition Files (all Copyright 1988 Lotus Development Corp., First Edition); and Lotus Agenda Install, Program, Utility, Applications, Help and Demo Disks (all Release 1.0, Copyright 1988 Lotus Development Corp.) for the IBM® Personal Computer or certified compatible or IBM PS/2® series computer, with hard disk, 31/2&#34; or 51/4&#34; floppy drive, 640 K. RAM and MS-DOS®, version 2.0 or higher. 
     In order to illustrate how data is organized and accessed in accordance with the invention an illustrative category hierarchy will be described. 
     Referring to FIG. 1, parent category C 1  is linked by means of pointers (represented by arrows) to its first child category C 2  and last child category C 8 . Other children categories of C 1 , C 7  for example, are linked between C 2  a C 8 , to form a chain of categories. Each child category includes pointers, which can be thought of as backwards and forwards, to its nearest two (i.e., adjacent) siblings in the chain, and a pointer to its parent (C 1 ). The children categories of each of C 2  &#39;s children are similarly arranged. Accordingly, C 2  includes pointers to its first child C 3  and last child C 6 , with each of C 2  &#39;s children including pointers to its nearest two siblings (e.g., C 5  points to C 4  and C 6 ) and to its parent (C 2 ) C 8  has only one child, C 9 , and therefore has two pointers to C 9 , since it is both the first and last child. 
     Associated with each chain of sibling categories is a genealogy (&#34;G&#34;) which lists the &#34;ancestors&#34; of those categories. For example, the sibling chain system of C 3 , C 4 , C 5  and C 6  has as its ancestors categories C 2  and C 1 . The genealogy is used to quickly determine all of the ancestors of any category in the linked sibling chain. 
     Categories, items and other elements such as genealogies and views are represented in the data base through the use of objects. An object is a section of memory that contains a plurality of pointers that point to or indicate other sections of memory as described more fully below. Each object also includes other information depending on the specific type of object. For example, an item object would include the item itself (i.e., the textual data) and a category object includes the name of the category. 
     Unlike the prior art systems discussed above, items exist independently of the categories with which they are associated. In other words, they are not listed in fields that &#34;belong&#34; to one category. Instead they are linked to specified or logically determined categories through the use of link structures which are also independent. Referring to FIG. 2, each of items I 1  -I 8  are linked to one or more of categories C 1  -C 9  through link structures represented in FIG. 2 by small squares appearing at the intersection of each linked item and category pair. The item and category are diagrammatically the coordinates of the link structure. Accordingly, I 1  is linked to categories C 9  and C 6 , I 2  is linked to categories C 7 , C 5  and C 3  etc. FIG. 2 is referred to as a &#34;cross-linked diagram.&#34; 
     Link structures are similar to objects in that each link structure comprises a section of memory consisting largely of pointers pointing to other sections of memory, with each link section being separate or independent from the elements that are linked. 
     As shown in FIG. 3A, the data structure of the data base has two separate files for objects and link structures, designated by extensions .AGA and .AGB respectively, the structure of each being illustrated in FIG. 3B. Object file .AGA includes objects 1-N (N being any desired number within the memory limitations of the system). Each object includes an object address and type, object specific information, and a plurality of pointers. The object specific information varies depending on the specific type of element that the object represents. For example, if the object is an item object this information would include the textual data that makes up the item itself. A category object would include the name of the category, etc. The pointers assigned to each object also depend on the type of element that the object represents, as well as other factors. For example, and as discussed above, the pointers assigned to a category depend on its position in the category hierarchy, as well as its position in the cross-linked diagram. 
     Similarly, link structure file .AGB includes link structures 1-N. Each link structure includes the link structure address and type, a plurality of pointers, and may include other information described below. The link structure pointers depend on the link structure&#39;s position in the cross-linked diagram. For example, link 10 in FIG. 2 contains a pointer to the item object for I 4 , the category object for C 6 , and four pointers to the immediately adjacent link structures 12, 14, 16, and 18, in both chains to which it belongs. 
     Each item object includes a pointer to the first and last link structures in its chain. Therefore, if an item is being viewed, such as I 4 , all of the categories to which this item is linked can quickly be determined by following the chain of link structures (I 4  points to link structure 12, which points to C 9  and to link structure 10 etc.). This structure also allows each item within a specified category to be quickly located. For example, if all of the items in C 5  need to be accessed, its chain is used in the same way. 
     FIG. 4 combines FIGS. 1 and 2 to illustrate the linking of items to the category hierarchy. When an item is linked to a category the item is also linked by subsumption (also called &#34;inheritance&#34;) to each ancestor of the category. For example, I 4  is linked to C 9 , C 6  and C 5  directly and to C 8 , C 2  and C 1  by subsumption. In other words, since C 6  and C 5  are subcategories or children of C 2 , any item linked to C 4  or C 5  is automatically linked to C 2 . Similarly, C 2  is a child of C 1  and I 4  must also be linked to C 1 . The genealogy objects are used to quickly determine all the ancestors of a given category. 
     Link structures are also used to create views. Referring to FIG. 5, view objects V 1  -V 9  (similar to category and item objects described above) are linked to any desired number of categories whose assigned items are to be viewed in a display. For example, V 1  comprises data from C 1  and C 4  while V 2  comprises data only from C 5 . The link structures are the same as described above, and each would contain pointers to the category object and view object which it links as well as the nearest link structures (if any) in both chains. Each category object and view object contains a pointer to the first and last link structures in the chain to which it belongs. 
     Referring to FIG. 6, link structures are also used to link categories to other categories. For example, it may be desirable to have any or all items that are linked to one category automatically linked to another category. This can be accomplished by using a link structure to link the two categories together. Link structures can also contain information regarding the nature of the link. It may also be desirable to have all items that are not linked to one category automatically linked to another category. These &#34;negative links&#34; are illustrated by squares with an X. For example, categories C 2  and C 11  are negatively linked and no item can be linked to both C 2  and C 11 . 
     Since the link structures, items and categories are all independent elements connected through the link structures, the system is extremely versatile allowing the data base to be easily modified (e.g., items and categories may be easily created, deleted or otherwise modified). 
     All modifications to the data base are performed through a view, each view comprising some desired combination of categories. A user makes a modification or enters new data by directly modifying the view. For example, a user may desire to add an item directly to a category in the view or may choose to add a new subcategory to a displayed category. 
     In the Agenda® implementation of the present invention, views are constructed as screens of information organized into sections having categories as section heads and items presented one after another beneath a given section head of the category to which the item has been assigned. A new item is entered into the database by entering or inserting its text under a given section head or category in the view on the screen. The category under which the item is entered is taken as the first category to which the new item is to be assigned. 
     The view can also have one or more columns to the right of the sections to indicate other categories or subcategories (e.g., &#34;high&#34;, &#34;medium&#34; and &#34;low&#34; subcategories of the category &#34;priority&#34;) to which the various items under a given section head are also assigned. Each column consists of a column head, which is a category, and one or more column entries which are also categories, for example, subcategories under the column head. The table below gives an example of a view. 
     
         ______________________________________View: ActivitiesCalls             Priority   Contact______________________________________Set up meeting atTerracotta Corp todiscuss CopyCatbefore the end ofthe month.Don&#39;t forget to call             Medium     Anna LasAnna Lasky with theinformation sherequested.Call Marketing to High       Abigailarrange a Rapidfiredemo for AbigailScheer this Tuesday.Check with Abigail             Low        AbigailScheer on meetingtimes.Contact Daniel Fiske -             Medium     Daniel F.get feedback!______________________________________ 
    
     The above view has one section with the section head &#34;calls&#34; and two columns with column heads &#34;Priority&#34; and &#34;Contact&#34;, as specified by the view object. A new item &#34;Setup meeting . . . &#34; has just been entered by the user under &#34;Calls&#34;. After entering the item, the user can make further assignments directly by moving to the columns of the view and entering an existing name of a subcategory under the column head. A new item is also screened or searched automatically to find words which match or nearly match existing category names. For example, in the above view, the assignment of the second item to the contact subcategory &#34;Anna Las&#34; would have been made automatically by means of the key word search of the item immediately after entry or modification. 
     FIG. 7 is a flowchart that illustrates the steps performed by the system when a user wishes to add a new item to the database. A &#34;free&#34; object must be obtained from the .AGA file (step 1). An object is free if it has not yet been used or if the element it once represented was deleted. The textual data that makes up the item itself (e.g., an employee&#39;s name) is added to the object (step 2). The system must then link the item object into the data base (i.e., into the cross-linked diagram shown in FIG. 2). A free link structure is obtained from the .AGB file (step 3) and a pointer in the link structure is set to point to the address of the item object (step 4). 
     The category object address of the category to which the item object is to be linked must now be obtained (step 5). When a user enters an item in a view, he enters the item directly into a specific category, so the first link established for the item in the cross-linked diagram will be to this category, and a pointer in the link structure is set to the category object address (step 6). 
     As discussed above, each object includes pointers to the first and last link structures in its chain in the cross-linked diagram. Therefore, these pointers must be updated whenever a link is added to an object&#39;s chain (step 7). Since the item is new, both its first and last link structure pointers will point to the same link structure (there is only one link structure so far). Next, the pointers in the link structure that point to the four adjacent link structures must be properly set (step 8). Note that there may be fewer than four adjacent link structures depending on the link structure&#39;s position in the cross-linked diagram. 
     Finally, pointers in adjacent link structures to the currently added link structure must also be set since, as noted above, each link structure points to adjacent link structures (step 9). 
     This completes the linking of the item to the first category. There may, however, be additional categories to which links must be established. For example, two categories may be directly linked together (see FIG. 6) such that an item linked to one must be linked to the other. Furthermore, logical criteria can be used to directly assign items to categories. For example, the preferred system uses a key word search in assigning items to categories. Consider a category called &#34;John Smith.&#34; The system can automatically assign an item to this category if the words John Smith appear in the item. Therefore, if a user is looking at a view that has a category called &#34;Meetings&#34; and he enters the item &#34;Meet with John Smith on Tuesday&#34;, this item would be linked to both the category Meetings and the category John Smith. 
     Accordingly, once the first link is established, the system will determine whether an additional category is to be linked to the item (step 10). If not, then the process is complete. If there is an additional category, the system returns to step 3 and repeats the process. 
     Other modifications to the data are performed similarly. The linking of any element to the cross-linked diagram involves obtaining a free object, and linking it through link structures to the appropriate place in the cross-linked diagram. Deleting an item or category is the reverse process. Each link must be broken and any affected pointers (e.g., adjacent link structure pointers) must be revised. 
     Categories can be created or inserted by getting a free category object and adding the appropriate pointers to insert it at a desired location in the category hierarchy. Of course, related category objects will also need to be modified to accommodate the new category. For example, if a category is inserted as the first category in a chain of siblings, the parent category object will need to be modified since it must have a pointer to its first child. The new category is then linked into the cross-linked diagram utilizing the necessary link structures. 
     Through the use of independent link structures, there is a &#34;many to many&#34; linking or mapping of elements achieved with the invention. In the prior art an item was a part of one category and existed only within that category. In the present invention, however, items and categories are separate and independent entities and a single item may be linked to many categories. 
     The invention performs modifications while the system is in a view mode. If changes made in the view mode produce any ambiguities, the system will resolve the ambiguities using a &#34;best guess method.&#34; One way in which an ambiguity could arise is where a category is by definition the union (boolean OR) of two otherwise unrelated categories. To maintain the truth of the category relationship, the item must be assigned to at least one of the OR&#39;ed categories. The choice is inherently ambiguous. If a new item is inserted and the system must choose between two categories in which to place the new item, it will put the item in the category corresponding to the immediately preceding item in the same view since it is likely that adjacent items in a view are related. If there is no preceding item then the following item may be used. The system could also choose the category that was first created, or the one with the most assigned items etc. By attempting to resolve the ambiguity without asking the user to perform elaborate programming, the system provides greater freedom in modifying data. 
     The cross-linked model used with the present invention allows side effects resulting from the modification of data in a view to be quickly resolved. For example, referring to FIG. 4, if C 5  is deleted each of the link structures in its chain will be quickly found and eliminated. For example, the link structure linking I 6  to C 5  will be eliminated, and I 6  will no longer be linked to C 5 , or to C 2  and C 1  (it would have been linked to these two categories by subsumption). If a user was viewing either categories C 2  or C 1  the side effect associated with eliminating C 5 , namely the deletion of I 2  from C 1  and C 2 , would be quickly resolved. 
     Other embodiments of the invention are within the scope of the appended claims.