Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
5379366
Noyes
January 3, 1995
Title
Method for representation of knowledge in a computer as a network database system
Abstract
A system for knowledge representation in a computer, together with the ability to recognize, store and use patterns in the knowledge representation, together with the ability for Natural Language Interaction with the knowledge representation system, together with systems to automatically transform information in the knowledge representation into a multitude of documents or other human interpretable displays in a plurality of different formats or views. User interaction with the knowledge representation through the view documents is achievable through a multitude of various possible formats. The Knowledge Representation system defines a novel database engine constituting a method for modeling knowledge as a network of concepts and a plurality of relationships between the concepts comprising the network. Each concept is represented as a record in the database which is identified by a unique record reference number. The unique record reference numbers are stored within the records comprising the database to record the plurality of relationships between concepts.
Inventors:
Noyes; Dallas B.
(Richland,
WA
)
Appl. No.:
011355
Filed:
January 29, 1993
Current U.S. Class:
706/55
706/11
706/50
Field of Search:
395/51,11,12,275,600,54,60
U.S. Patent Documents
4930071
May 1990
Tou et al.
4965741
October 1990
Winchell et al.
4974191
November 1990
Amirghodsi et al.
5068894
November 1991
Hoppe
Other References
Object-Oriented Concepts, Databases, and Applications Won Kim et al. Dec. 31, 1989, ACM Press pp. 79-120. .
Classification as a Query Processing Technique in The Candide Semantic Data Model H. Beck et al. IEEE/6-10 Feb. 1989, pp. 572-581. .
Classification as a Query Processing Technique in the Candide Semantic Data Model H. Beck et al. IEEE/6-10 Feb. 89 pp. 572-581..~
Primary Examiner:
MacDonald; Allen R.
Assistant Examiner:
Dorvil; Richemond
Attorney, Agent or Firm:
Rothwell, Figg, Ernst & Kurz
Claims
What is claimed is:
1. A method for representing information in a computer system, comprising the steps of:
establishing in said computer system a knowledge representation database made up of individual records, wherein each record is associated with a unique reference number (URN) which identifies each record and wherein each record stores at least one relationship comprised of a characterization and a value,
the characterization of said relationship being a URN of a second record which defines [the]a nature of said relationship, and
the value of said relationship being a complex data representation composed of at least one internal value, external value, or mixed value which define an object of said relationship,
internal values storing only URNs of other records,
external values storing external data such as character strings, integers, and real numbers, and
mixed values storing a combination of internal and external values;
establishing an index to said knowledge representation database made up of the name of each record together with the associated URN of said record, wherein the name of the record is an external value of a relationship stored therein which designates that external value as a character string description of a concept represented by said record;
establishing, for each record in said knowledge representation database, fundamental relationships between said record and other records in said database, said fundamental relationships being comprised of
intrastratum relationships which store URNs of other records on the same strata or level of abstraction designated as separate libraries within the knowledge representation system, said intrastratum relationships being designated as parent and children relationships which identify the record in which said parent and children relationships are stored as a member of the same library as the records identified by the URNs stored in said intrastratum relationships, and
interstrata relationships which store URNs of other records in different strata or libraries, said interstrata relationships being designated as Type record relationships which identify the record in which said Type record relationships are stored as a particular instance of records in another stratum or library;
designating certain records as system concepts by storing the URNs of said certain records in a system concept index to said database reserved for records which represent system concepts of said knowledge representation database,
system concept records being records which are used as termination points of networks of said fundamental relationships and which are recognized by the system by determining whether the URN or the name of a particular record is in said system concept index, wherein
system concept records designating strata or libraries (such as System library, Attribute library, Component library, and Project library) are the termination of parent fundamental relationships,
system concept records designating attribute classes (such as Assignment, Connection, Non-Binding, Rules, and External) are the termination of parent fundamental relationships for records which are descendants thereof and which store the URN of the Attribute library system concept as a parent relationship, and
system concept records designating attribute properties (such as Name, Data Type, Field Length, and Prompt) are the termination of relationship characterization networks,
said system concepts being required to store only fundamental relationships;
storing within each record comprising said Attribute library at least one relationship which is characterized by a URN of an attribute property system concept record, wherein said at least one relationship stores the value of the name of the concept represented by the record in which said attribute property System record URN is stored;
storing within each record comprising said Component library at least one relationship which is characterized by a URN of an Attribute library record, wherein said at least one relationship stores the value of the name of the concept represented by the record in which said Attribute library record URN is stored;
storing within each record comprising said Project library at least one relationship which is characterized by a URN of a Component library record, wherein said at least one relationship stores the value of the name of the concept represented by the record in which said Component library record URN is stored;
establishing in said computer system at least one editor for modifying the records and relationships stored in said database, including means for recognizing patterns in the relationships stored in said records;
storing said recognized patterns as relationships in the records associated with the recognized patterns;
establishing an additional class of system concept records to identify relationships storing values that define said recognized patterns, wherein each of said additional class system concept records represent particular types of patterns in said relationships;
operating on said stored patterns in the operation of said at least one editor by reading relationships storing patterns predetermined to be relevant to said at least one editor and using the values of said relationships in limiting the operation of said editor, said relationships storing patterns relevant to said editor being identified by the characterization of said relationships as system concepts identified by the system as being relevant to said editor;
establishing in said computer a descriptive database for describing an active concept record designated by a user, comprised of a plurality of records each of which stores a single relationship having an associated URN for said active concept record, and an associated URN for a source record in which said relationship is stored,
the URN for said active concept being the URN of the record in said knowledge representation database for which the description in the descriptive database is assembled, and
the URN for said source record being the URN of that record in said knowledge representation database in which said relationship is stored;
reading a descriptive network for said active concept by reading all records in said knowledge representation database forming a network of related records through the fundamental relationships of parent and type, combining the relationship lists from said read records, and storing said relationships from said read records in said descriptive database,
said relationship lists being combined by applying Taxonomy, Type, Composition and User inheritance rules,
said relationships being stored in said descriptive database together with the URN of said active concept and the URN of said source record;
selecting a view, class and type of display for said active concept and deriving the selected type of display by assigning icons to the records representing concepts in said descriptive database according to the type of display selected, organizing and locating said icons in a display space of said computer according to the selected class, and creating connection icons for interconnections between concept icons located in said display space according to the selected view; and
interacting with said knowledge representation database through interaction with said icons in said display space and evaluation of said icon interaction through the use of decision trees for evaluation of the view, command history, system flags, and icon association for identification of appropriate responses to said icon interaction.
2. The method for representing information in a computer system according to claim 1, further comprising the step of establishing at least one optional user relationship in the knowledge representation database by specifying a user defined Attribute other than a system concept, and storing said user defined Attribute as a record in said knowledge representation database, wherein the URN of said user defined Attribute is stored in records having said user defined Attribute as the characterization of a relationship stored therein.
3. The method for representing information in a computer system according to claim 1, further comprising the step of establishing in said computer system a plurality of editors for modifying the records of said database and relationships stored in said records, wherein said editors enable users to create, read and replace information in each of the records in the knowledge representation database, and enable users to identify and store relationships in the records in the knowledge representation database by specifying the characterization and value of a relationship and storing the specified relationship in a record.
4. The method for representing information in a computer system according to claim 1, wherein said patterns in said relationships are comprised of recurring correlations in values of fundamental relationships in Project library records, and recurring correlations in values of user relationships in records of the Project and Component libraries.
5. The method for representing information in a computer system according to claim 4, further comprising the step of storing patterns recognized in Project library records in the component record represented by the URN stored in the type fundamental relationship of said Project records or in a parent record of said component record, and
storing patterns recognized in Component library records in the component record in which they are first identified or in a parent record of said component record;
the characterization of the relationship storing the recognized pattern being designated as a system concept.
6. The method for representing information in a computer system according to claim 1, further comprising the steps of:
evaluating a natural language user input expression by sequential application of an augmented transition network parse based on identification of the function of a recognized expression in said knowledge representation database, and by parsing by differences based on the evaluation of said recognized expression and said identified function;
wherein a recognized expression corresponds to a name associated with a record in the knowledge representation database, and the function of a recognized expression is evaluated by identifying the system concepts in a descriptive network of recognized expressions.
7. The method for representing information in a computer system according to claim 6, further comprising the steps of dynamically defining concepts not found in said knowledge representation database and adding said defined concepts to the knowledge representation database in a particular location within a particular library through evaluation of said input expression as a constraint on the fundamental relationships of said dynamically defined concepts.
8. The method for representing information in a computer system according to claim 6, further comprising the steps of coordinating the derivation of appropriate views of the information in the knowledge representation database in response to said natural language user input expression through evaluation of the input expression for specifying the active concepts and selected appropriate view, class and type of display for response to the input expression.
9. A method for representing information in a computer system, comprising the steps of:
establishing in said computer system a knowledge representation database made up of individual records, wherein each record is associated with a unique reference number (URN) which identifies each record;
storing in each of a plurality of records of said knowledge representation database the URN of at least one other record of said knowledge representation database; and
establishing means in said computer system for automatically deriving a human understandable format for displaying information contained in said records through reading and evaluation of said stored URNs.
10. The method for representing information in a computer system according to claim 9, further comprising the step of storing in at least one record the URN of a second record with said second record storing the URN of said at least one record.
11. The method for representing information in a computer system according to claim 9, wherein each record of said database stores a plurality of relationships, said relationships being comprised of a characterization and a value,
the characterization of said relationship being a URN of a second record which defines the nature of the relationship, and
the value of said relationship being a complex data type comprised of internal, external and mixed values which define the object of a relationship,
internal values storing only URNs of other records and,
external values storing values other than the URNs of other records such as character strings, integers, and real numbers, and
mixed values storing a combination of values typical of internal and external values.
12. The method for representing information in a computer system according to claim 11, further comprising the step of storing in at least one record a relationship that has the URN of a second record as an internal value and storing in said second record a relationship that has the URN of said at least one record as an internal value.
13. The method for representing information in a computer system according to claim 11, further comprising the step of naming each record by storing a designated name of thereof as an external value of a relationship in each record.
14. The method for representing information in a computer system according to claim 11, further comprising the step of providing an index to said knowledge representation database made up of a name of each record together with its associated URN, wherein said name is a designated external value of a relationship stored therein as being the name of a concept represented by that record.
15. The method for representing information in a computer system according to claim 14, further comprising the step of designating certain records as System Concepts in a system concept index to said database, said system concepts being recognized by the system by determining whether the URN or the name of a particular record is in said system concept index.
16. The method for representing information in a computer system according to claim 15, further comprising the step of defining System Concepts designating strata, levels of abstraction, or libraries (such as System, Attribute, Component, and Project).
17. The method for representing information in a computer system according to claims 15, further comprising the step of defining System Concepts designating attribute classes (such as Assignment, Connection, Non-Binding, and External).
18. The method for representing information in a computer system according to claim 17, further comprising the steps of:
reading the relationships stored in a designated active concept record and identifying the attribute class concepts of the characterizations of said relationships;
identifying relevant documents to said record by comparing said identified attribute class concepts to system concepts known by the system to be associated with the types of documents which the system can automatically derive;
selecting from said identified relevant documents a specific document for display of said record;
deriving said specific document; and
displaying said specific document.
19. The method for representing information in a computer system according to claim 18, wherein the step of deriving a specific document includes the steps of:
selecting a view, class, and type of display for said active concept record;
automatically deriving the selected type of display by reading a subset of the records in said knowledge representation database relative to said active concept record, based on stored relationships therein, which subset defines the concepts constituting said selected type of display;
assigning icons to said subset of the records according to said selected type of display;
organizing and locating said icons in a display space of said computer system according to said selected class; and
creating connection icons for interconnections between concept icons located in said display space according to said selected view.
20. The method for representing information in a computer system according to claim 19, wherein the type specifies particular procedures for selecting a subset of the information in said knowledge representation database, reading the descriptive networks for the concepts in said subset, and assigning icons to the concepts in said subset.
21. The method for representing information in a computer system according to claim 19, wherein the class identifies the relevant types and specifies particular procedures for organizing and locating the icons of the concepts in said display space.
22. The method for representing information in a computer system according to claim 19, wherein the view identifies the relevant classes and specifies particular procedures for creating icons for the relationships between the concepts located in the document display space.
23. The method for representing information in a computer system according to claim 15, further comprising the step of defining System Concepts designating attribute properties (such as Name, Data Type, Field Length, and Prompt).
24. The method for representing information in a computer system according to claim 15, further comprising the step of defining system concepts designating pattern storage characterizations (such as Children, Node Name Attr, Parent, Use Isa Name, Concat Attrs, Os Path Name, Sibling Inc, User Text, Connect To, Linear, Multiple, and Single).
25. The method for representing information in a computer system according to claim 15, further comprising the steps of:
evaluating a natural language user input expression by sequential application of an augmented transition network parse based on identification of the function of a recognized expression in said knowledge representation database, and by parsing by differences based on the evaluation of said recognized expression and said identified function;
wherein a recognized expression corresponds to a name associated with a record in the knowledge representation database, and the function of said recognized expression corresponds to the system concepts in a descriptive network of said recognized expressions.
26. The method for representing information in a computer system according to claim 25, wherein the recognition of the user input expression occurs by matching the input expression to names of records in said knowledge representation database and associating with said input expression the library system concept in the parent fundamental relationship of said records.
27. The method for representing information in a computer system according to claim 26, further comprising the steps of dynamically defining concepts not found in said knowledge representation database and adding said defined concepts to the knowledge representation database in a particular location within a particular library through evaluation of said input expressions as a constraint on the fundamental relationships of said dynamically defined concepts.
28. The method for representing information in a computer system according to claim 26, further comprising the steps of coordinating the derivation of appropriate documents from the information in the knowledge representation database in response to said natural language user input expression through evaluation of the input expression for specifying the active concepts and selected appropriate view, class, and type of display for response to the input expression.
29. The method for representing information in a computer system according to claim 11, further comprising the steps of:
establishing, for each record in the knowledge representation database, fundamental relationships between said record and other records of said knowledge representation database, said fundamental relationships being comprised of:
intrastratum relationships which store URNs of other records on the same strata or level of abstraction designated as separate libraries within the knowledge representation system, said intrastratum relationships comprised of parent and children relationships, and
interstrata relationships which store URNs of other records in different strata or libraries, said interstrata relationships being comprised of Type relationships which identify the record in which they are stored as a particular instance of records in another stratum or library.
30. The method for representing information in a computer system according to claim 11, further comprising the step of establishing at least one optional user relationship stored in at least one of the records in the knowledge representation database by specifying a user defined Attribute that is not a system concept and storing the URN of said user defined Attribute in said at least one record as the characterization of said optional user relationship.
31. The method for representing information in a computer system according to claim 11, further comprising the step of establishing in said computer system a plurality of editors for modifying the relationships stored in said records of said knowledge representation database, wherein said editors enable users to identify and store relationships in said records in said knowledge representation database by specifying the characterization and value of a relationship and storing said relationships in at least one of said records.
32. The method for representing information in a computer system according to claim 31, wherein relationships are created further comprising the steps of:
identifying the characterization of a relationship pertinent to a given record;
designating the record in which said characterization is to be stored, wherein said designated record is either said given record or one of its taxonomy ancestors; and
storing said characterization in said designated record in a relationship with a nil value.
33. The method for representing information in a computer system according to claim 31, wherein relationships are edited further comprising the steps of:
identifying the value to be edited;
identifying a source record of said value to be edited, wherein said source record is the record in said knowledge representation database wherein said value to be edited is stored;
modifying said value to be edited to obtain a new value; and
replacing said value to be edited in the relationship in said source record in which said value to be edited is stored with said new value.
34. The method for representing information in a computer system according to claim 31, further comprising the steps of:
establishing in said computer system means for recognizing, storing, and operating on patterns in the records and relationships created by said modifying editors; and
recognizing the patterns in the records and relationships by recording the plurality of URNs of records and relationships created by one of said editors and determining whether said URNs are typical of the operation of said one of said editors in modifying said records and relationships.
35. The method for representing information in a computer system according to claim 34, wherein said patterns in said relationships are comprised of recurring correlations in values of fundamental relationships in Project library records, and recurring correlations in values of user relationships in records of the Project and Component libraries.
36. The method for representing information in a computer system according to claim 35, wherein patterns recognized in Project library records are stored in the component record represented by the URN stored in the type fundamental relationship of said project records or in a parent record of said component record, and wherein patterns recognized in Component library records are stored in the component record in which said recognized patterns are first identified or in a parent record of said component record;
the characterization of the relationship storing the recognized pattern being designated as a system concept.
37. The method for representing information in a computer system according to claim 34, further comprising the steps of:
establishing system concepts to characterize relationships storing values that define recognized patterns established by said one of said editors, wherein each of said system concepts identify particular types of patterns created by said one of said editors; and
storing relationships characterized by said system concepts in relevant records comprising said knowledge representation database.
38. The method for representing information in a computer system according to claim 34, further comprising the steps of:
identifying the relevant relationship storing said stored pattern as a value;
reading said relevant relationship; and
using the pattern stored within said relevant relationship within the operation of said one of said editors.
39. The method for representing information in a computer system according to claim 11, further comprising the step of establishing in said computer system a plurality of editors for that enable users to create a new record in said knowledge representation database, said editors including means for establishing appropriate fundamental relationships of said new record to other records in said knowledge representation database and storing said fundamental relationships in said new record.
40. The method for representing information in a computer system according to claim 11, further comprising the step of:
establishing in said computer system a descriptive database for describing an active concept record designated by a user, comprised of a plurality of records each of which stores a single relationship having an associated URN for said active concept record, and an associated URN for a source record in which said relationship is stored,
the URN for said active concept being the URN of the record in said knowledge representation database for which the description in the descriptive database is assembled, and
the URN for the source record being the URN of that record in the knowledge representation database in which said relationship is stored.
41. The method for representing information in a computer system according to claim 40, further comprising the steps of:
reading a descriptive network for an active concept in the knowledge representation database forming a network of related records through the fundamental relationships of parent and type, combining the relationship lists from said read records, and storing the said relationships from said read records in said descriptive database,
said relationship lists being combined by applying inheritance rules comprised of Taxonomy, Type, Composition and User inheritance,
each relationships comprising said relationship list being stored in said descriptive database together with the URN of said active concept and the URN of source record, wherein said each relationship is stored in the Knowledge Representation Database.
42. The method for representing information in a computer system according to claim 41, wherein Taxonomy inheritance rules define manners of combining the relationship list in the series of records linked through the parent fundamental relationship for component and attribute library records.
43. The method for representing information in a computer system according to claim 41, wherein Type inheritance rules define manners of combining the relationship list in the component records identified by the URNs stored in the type fundamental relationship of a project record.
44. The method for representing information in a computer system according to claim 41, wherein Composition inheritance rules define manners of combining the relationship list in the series of records linked through the parent fundamental relationship for project library records.
45. The method for representing information in a computer system according to claim 41, wherein User inheritance rules define manners of combining the relationship lists in a series of records linked through the URNs stored as internal values in relationships stored in said records.
46. The method for representing information in a computer system according to claim 11, further comprising the steps of:
establishing user interaction with said knowledge representation database through interaction with a display of said computer system;
selecting a view, class, and type of display for a designated active concept record and automatically deriving the selected type of display by reading a subset of the records in said knowledge representation database relative to said active concept, based on stored relationships therein, which subset defines the concepts constituting said selected type of display;
assigning icons to said subset of the records according to said selected type of display;
organizing and locating said icons in the display space of said computer system according to said selected class, and creating connection icons for interconnections between concept icons located in said display space according to said selected view;
detecting user interaction with the icons in said display space;
evaluating said icon interaction through the use of decision trees for evaluation of the view, command history, system flags, and icon association for identification of the appropriate process or procedure for response to said interaction; and
applying said appropriate process or procedure for response and developing a response to said interaction.
47. The method for representing information in a computer system according to claim 46, wherein said icon is interpreted as the entities comprising said icon.
48. The method for representing information in a computer system according to claim 46, wherein said icon is interpreted as the location in said display space occupied by said icon.
49. The method for representing information in a computer system according to claim 46, wherein said icon is interpreted as one of the plurality of URNs associated with said icon.
50. The method for representing information in a computer system according to claim 9, wherein each record is also associated with a name by which each record is identified.
51. The method for representing information in a computer system according to claim 9, further comprising the step of establishing in said computer system a plurality of editors for modifying the records of said knowledge representation database and information stored in said records, wherein said editors enable users to create, read and replace information in each of the records in the knowledge representation database.
52. A method for representing information in a computer system, comprising the steps of:
establishing in said computer system a knowledge representation database made up of individual records, wherein each record is associated with a unique reference number (URN) by which each record is identified and wherein each record stores at least one relationship comprised of a characterization and a value,
the characterization of said relationship being a URN of a second record which defines the nature of said relationship, and
the value of said relationship being a complex data representation composed of at least one internal value, external value, or mixed value which define the object of said relationship,
internal values storing only URNs of other records,
external values storing external data such as character strings, integers, and real numbers, and
mixed values storing a combination of internal and external values;
designating certain records of said knowledge representation database as System Concepts by including the names and associated URNs of said certain records in a System Concept index to said knowledge representation database provided in said computer system;
creating user defined records based on said System Concepts, and storing said user defined records in said knowledge representation database, wherein at least one user defined record stores therein the URN of a System Concept as a relationship thereof, and wherein all of said user defined records store therein the URN of least one other record in said knowledge representation database; and
deriving comprehensible information through evaluation of relationships stored in said records of said knowledge representation database and recognition of System Concepts through consultation of said System Concept index.
53. A method for representing information in a computer system, comprising the steps of:
establishing in said computer system a knowledge representation database made up of individual records, wherein each record is associated with a unique reference number (URN) by which each record is identified and wherein each record stores at least one relationship comprised of a URN to a second record, said stored relationships constituting a knowledge network conceptually interconnecting said records of said database in said computer system so as to yield comprehensible information; and
deriving comprehensible information by designating a record in said database as an active record, assembling in said computer system all records related to said active record by reading relationships stored in said active record, and deriving information about said designated active record by evaluating said assembled records.
Description
MICROFICHE APPENDIX
A microfiche appendix of the code of a working embodiment of the invention, consisting of 13 microfiche and 732 frames, is included as part of this disclosure. It will be useful as a guide in implementing the invention.
BACKGROUND OF THE INVENTION
This invention relates to a system for knowledge representation in a computer system together with Natural Language Interface, together with the ability to recognize, store and use patterns in the knowledge representation, together with computerized means for automatically transforming information in the knowledge representation into a multitude of documents or other human interpretable displays in a plurality of different formats or views, together with means for user interaction with the knowledge representation through the documents or displays.
The Knowledge Representation system defines a novel database engine constituting a method for modeling knowledge as a network of concepts and the relationships of each concept to other concepts. Each concept is represented as a record in the database which is identified by a unique record reference number. Relationships are represented by storing the unique record reference numbers of relevant records within the records comprising the knowledge representation database.
The records are organized into strata or levels of abstraction by means of storing relationships to other records within a given stratum. These relationships organize each level into hierarchies and a plurality of other relational networks which represent generally accepted ways of thinking about various fields of knowledge.
The concepts in lower levels of abstraction are related to those in higher levels by storing the unique record reference numbers of records of simple (more abstract) concepts within the structure of records representing more complex (more specific) concepts. Thus, more complex concepts are defined by the records whose reference numbers are stored within their record structure.
This invention further relates to a novel system for a Natural Language Interface (NLI) including a new method of parsing and evaluating input expressions in conjunction with the information in the Knowledge Representation Database.
The system includes a method for dynamically updating the Knowledge Representation database to "learn" through interaction with system users. This is accomplished by programmed means which automatically recognize, store, and utilize patterns in the knowledge representation database.
The system further includes a novel method for automatically transforming knowledge embodied in the Database into a plurality of human-perceivable documents expressing the knowledge.
User interaction with the Knowledge Representation through the Documents enables user interactions typical of Graphical User Interfaces (GUI), Hypertext, Object Linking Embedding (OLE), and context sensitive operation in a single unified user interface.
The present invention can be evaluated by referring to five major constituents which are illustrated in FIG. 1.
A) The data-base engine referred to herein as a "knowledge representation" system is most closely related to hierarchical and network databases. It differs from previously disclosed databases in that this invention employs a record system which embeds the database record numbers of a plurality of other records within a list stored in a particular record in a network of interrelated records. Each record is allowed to maintain an unbounded list of relationships to other records within the Knowledge Representation database.
System concepts are defined which allow the creation of levels of abstraction within the knowledge representation.
Fundamental relationships are the minimum set of relationships which each record is required to have in order to assure that the concept is related to the other concepts of the knowledge representation database. Each record is required to store the reference number of at least one record in a higher level of abstraction than that record, and every record on each level of abstraction is required to store at least one record reference number of another record on the same level in a relationship which is characterized by an attribute typical of the level.
The Knowledge Representation system further requires a separate, non-permanent database in which to assemble descriptions of particular records from the network of records in the primary Knowledge Representation database.
The retrieval system of an individual record and the records whose reference numbers are embedded in its substructure provides means for relationship inheritance and is without precedent.
B) The means for pattern recognition, storage and utilization employed in the invention are unique and provide novel means for machine "learning" by recognizing patterns in the relationships comprising the records, storing the patterns as relationships and utilizing the patterns in creating additional concepts and relationships in the Knowledge Representation Database.
C) The Natural Language Interface (NLI) is a novel system for enabling human interaction with the Knowledge Representation Database by using human language. The NLI system employs novel means for parsing input expressions in that it employs a sequential combination of a transitional network parser (related to an Augmented Transition Network) and a pattern matching parser (related to Parsing by differences lists methods). Both parsers are further unique in that they are based on the level of abstraction and fundamental relationships of a concept in the knowledge representation database instead of the human language grammatical function of the concept.
D) The method for automatically deriving a multitude of documents is based on abstracting standard documents or displays of knowledge into Views, Classes, and Types, wherein the Types define the vocabulary, the Class defines the grammar, and the View defines the connectivity and interaction, and is without precedent.
E) The user interface integrates the principal characteristics of GUI, Hypertext, OLE, and context sensitive programming in a single integrated user environment. This integration is without precedent, and is implemented in the invention by novel means which are significant improvements over the means currently known to the art for these technologies.
In this invention, the hypertext-like behavior is a consequence of the relationships stored at each record so that the view document has the feel of having hypertext implemented on a massive scale; every icon is a portal to all other view documents containing the concept and is also a portal to all related concepts. This contrasts with the Hypertext idiom which typically employs user defined locational links between documents which operate as an adjunct to static document representation.
The Knowledge Representation system further utilizes external relationships which enable the linking of records in the database to files or programs external to the Knowledge Representation Database.
NOTES ON IMPLEMENTATION
A suitable computer platform and programming environment for the implementation of the invention must be selected by the system developer. The programming environment should easily accommodate the kinds of structures that are required for the knowledge representation.
The Knowledge Representation Database can be implemented on a wide variety of computer systems and hardware. Generally the Knowledge Representation Database will be stored on nonvolatile memory media such as a hard disk, tape, optical disk, etc.
The minimum requirements of a programming environment with database capabilities suitable for implementation of the knowledge representation are summarized in FIG. 2. The database capabilities can either be native to the programming environment or developed by the system developer. Unique reference numbers (2a) must be available in the system for each record. A reference number is any unique tag or label (of any data type) for the record. The reference numbers must be permanently associated with the records (2b). The database must be able to store reference numbers in the database records and associated index(es) (2c). The reference number is typically a standard data type in the development environment.
The reference numbers must be uniquely and permanently associated with each record because the reference numbers are used to cross reference the records by recording reference numbers within the records themselves. The system must store these reference numbers in the database records, as the references to other records contained in a record define the relationship of record to the network of records in the knowledge representation database. The environment should include a database indexing scheme or enable the designer to be able to implement an index to the records in the database (2d). The provision for indexing the records in the database enables rapid identification and retrieval of desired records. The indexing scheme should accommodate indexing key word(s) associated with a record and also indexing selected reference numbers indicating relationships to other records.
Various standard schemes for indexing (B-Trees, hashing, etc.) are currently available. An appropriate scheme will be apparent to the developer once the principles of the invention are understood. Therefore no specific disclosure of an indexing scheme or details of implementation of the indexing scheme are provided in this disclosure. The embodiment in the appendix used a B-tree indexing scheme.
The environment should not restrict the record data type which may be declared for the database since the record data types of the invention include complex data types as disclosed subsequently (2e). The relationships maintained by a record are represented in substructures of complex data types accommodating a wide variety of standard data types. The environment should not restrict the record length (2f). Variable length records are desirable to enable the dynamic addition of relationships to the records. Each record may maintain an unbounded number of relationships: the number and type of relationships differ with each record.
The lack of restriction on the record data typing and record length will provide the widest possible latitude to the system designer in selecting and implementing data types appropriate to the knowledge domain. If restrictions on data type and record length do exist, it may be possible to implement work arounds. Such work arounds may include record chaining and data type conversion algorithms. Such algorithms, if required, will be known to a skilled practitioner and are not discussed further herein. It is best to avoid systems which will restrict the data typing and record length of the records.
The structures of the records for the Knowledge Representation Database are typically established as data typing (domain) declarations in the programming language in which the structures are implemented. Suitable mechanisms for declaring such structures are provided by the various programming languages or tools which are suitable for implementation of the invention. Since such mechanisms are a property of the specific system in which the invention is implemented, they are considered to be standard and are not discussed in detail in this disclosure.
The invention can be implemented in a wide variety of standard computer systems. The preferred embodiment of the invention included in the appendix was on DOS.RTM. PCs using the programming language PDC Prolog.RTM. with Pharlap.RTM. Extenders. The preferred embodiment illustrates the adaptability of this invention to standard programming environments.
Prolog.RTM. is a declarative language. Declarative languages are distinct from procedural languages in that Declarative languages are not easily represented as procedural flow diagrams. In the following discussions, flow diagrams are used to illustrate the essential procedures and processes embodied in the invention. However, these flow diagrams, while illustrating the essential procedures, must be understood as embodying a procedural equivalent of the declarative code found in the Prolog program.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a schematic diagram of a system for representing knowledge in a computer database according to the present invention;
FIG. 2 is a chart of Minimum Requirements for a Development Environment Suitable for Implementation of the Knowledge Representation Database;
FIG. 3 is a Schematic Summary of the Means for Knowledge Representation;
FIG. 4 is a Schematic Diagram of Knowledge Representation Implemented in Multiple Files;
FIG. 5 is a diagram of References in Values of Conjugate Relationships Must Correlate;
FIG. 6 is an illustration of the Organization of Records in Knowledge Representation;
FIG. 7 is an illustration of Library Structure Used in Knowledge Representation;
FIG. 8 is a chart of Summary of Strata Characteristics;
FIG. 9 is an illustration of System Concepts in the Library Structure used in Knowledge Representation;
FIG. 10 is a chart of Summary of Typical Useful Attribute Properties;
FIG. 11 is a chart of Summary of Typical Useful Attribute Classes;
FIG. 12 is a chart example of Domain Declaration for Knowledge Representation Database;
FIG. 13 is a Flow Diagram of Programmed Means for Recognition of System Concepts;
FIG. 14 is a Flow Diagram of Programmed Means for Assuring that System Concepts are Inviolate;
FIG. 15 is a Flow Diagram of Programmed Means for Assembling Ancestor Lists as an Example of Network Traversal;
FIG. 16 is a Flow Diagram of Programmed Means for Saving Information Stored in the Descriptive Database by Storing it in the Knowledge Representation Database;
FIG. 17 is a chart Summary of the types of Relationship Inheritance Based on the Descriptive Networks;
FIG. 18 is a logic diagram illustration of concepts in the descriptive network of an attribute record;
FIG. 19 is a logic diagram illustration of concepts in the descriptive network of a component record;
FIG. 20 is a logic diagram illustration of concepts in the descriptive network of a project record;
FIG. 21 is a Flow Diagram of Programmed Means for Implementing Relationship Inheritance;
FIG. 22 is a Flow Diagram of Programmed Means for Implementing Characterization Inheritance;
FIG. 23 is a chart of Domain Declaration for Descriptive Database;
FIG. 24 is a Flow Diagram of Programmed Means for Adding a Node to the Knowledge Representation Database;
FIG. 25 is a Flow Diagram of Programmed Means for Adding a Relationship to the Relationship.sub.-- List of a Record;
FIG. 26 is a Flow Diagram of Programmed Means for Instituting the Value of an Internal Relationship;
FIG. 27 is a Flow Diagram of Programmed Means for Instituting the Value of an External Relationship;
FIG. 28 is a Tree Diagram of the Taxonomy of Rules System Concepts;
FIG. 29 is a chart Summary and Description of Specific Rules implemented as System Concepts in the Preferred Embodiment;
FIG. 30 is a chart Summary and Description of Specific Rule Properties Implemented as System Concepts in the Preferred Embodiment;
FIG. 31 is a Flow Diagram of Programmed Means for Pattern Recognition and Storage in the Knowledge Representation;
FIG. 34 is a Flow Diagram of Programmed Means for Natural Language Processing;
FIG. 35 is a Flow Diagram of Programmed Means for Augmented Transition Network Parse;
FIG. 36 is a Database Declaration for NLI Functional Identification Used in Augmented Transition Network Parse;
FIG. 37 is a chart Summary of Suggestions for System Concepts and Associated User Concepts to add to the Knowledge Representation Database for NLI;
FIG. 38 is a Flow Diagram of Programmed Means for Parse by Differences;
FIG. 39 is a chart showing Examples of Views, Classes, and Types Comprising a Plurality of Views of the Knowledge Representation;
FIG. 40 is a Flow Diagram of Programmed Means for View Management;
FIG. 41 is a chart Domain Declaration for Tracking Active;
FIG. 42 is a Flow Diagram of Programmed Means for Deriving a Plurality of Documents of the Knowledge Representation;
FIG. 43 is a chart Summary of Correlation Between View Derivation Step and Level of View Document Abstraction;
FIG. 44 is a Flow Diagram of Programmed Means For Deriving A Plurality of Views of the Knowledge Representation;
FIG. 45 is a Flow Diagram of Programmed Means For Deriving a Plurality of Schematic Classes of the Knowledge Representation;
FIG. 46 is a Flow Diagram of Programmed Means For Deriving a Plurality of Types of Schematic Cluster Diagrams of the knowledge Representation;
FIG. 47 is a Flow Diagram of Programmed Means For Reading Descriptive Sets;
FIG. 48 is a chart showing Examples of Defining and Auxiliary Relationships for Various Types of Documents;
FIG. 49 is a Flow Diagram of Programmed Means For Reading Defining Relationships;
FIG. 50 is a Flow Diagram of Programmed Means For Reading Auxiliary Relationships;
FIG. 51 is a Flow Diagram of Programmed Means For Assigning Icons to a Descriptive Set;
FIG. 52 is a Flow Diagram of Programmed Means For User Interaction with the Knowledge Representation Through the View Documents;
FIG. 53 is a chart Summary of Icon Symbology;
FIG. 54 is a chart Summary of Symbol Interpretation;
FIG. 55 is a Standard Decision tree for Event Processing;
FIG. 56 is a Recommended Decision Tree for Icon Symbol Interpretation;
FIG. 57 is a Flow diagram of Programmed Means for Updating Active Based on User Event Location;
FIG. 58 is a Flow Diagram of Programmed Means For Highlighting Entities;
FIG. 59 is a Flow Diagram of Programmed Means For Interpreting Icon as System Concept Associated with Icon Entities;
FIG. 60 is a Flow Diagram of Programmed Means For Interpreting Icon as Abstraction Associated with Icon Entities;
FIG. 61 is a Flow Diagram of Programmed Means For Interpreting Icon as Entity Editing Procedure;
FIG. 62 is a Flow Diagram of Programmed Means For Interpreting Icon as Procedure for Transferring View Derivation to Active;
FIG. 63 is a Flow Diagram of Programmed Means For Changing View of Active;
FIG. 64 is a Flow Diagram of Programmed Means For Interpreting Icon as Procedure for Identifying Library System Concept of Active;
FIG. 65 is a Flow Diagram of Programmed Means For Interpreting Icon as Abstraction Associated with Active;
FIG. 66 is a Flow Diagram of Programmed Means For Interpreting Icon as Procedure for Concept and Relationship Editing;
FIG. 67 is a Flow Diagram of Programmed Means For Interpreting Icon as External Procedure;
FIG. 68 is a Flow Diagram of Programmed Means For Interpreting Icon as Ancestry Context;
FIG. 69 is a Flow Diagram of Programmed Means For Interpreting Icon as Descendants Context;
FIG. 70 is a Flow Diagram of Programmed Means For Interpreting Icon as Type Context;
FIG. 71 is a Flow Diagram of Programmed Means For Identifying Attribute Class Concepts for Active Attribute User Concept; and
FIG. 72 is a Flow Diagram of Programmed Means For Interpreting Icon as User Connection Context.
DESCRIPTION OF THE PREFERRED EMBODIMENT
FIG. 1 is a schematic diagram which highlights the primary constituents of the invention. A detailed discussion of each of the constituents is provided in subsequent sections following this introductory overview.
The Knowledge Representation Database (1a) is a new type of database system which represents knowledge as a network of a plurality of cross-referenced records comprising a computer database. The representation of knowledge is based on the insight that knowledge is a network of concepts and relationships between concepts (i.e. the meaning of a concept is defined by its relationship to other concepts). Concepts are embodied as individual database records. Relationships between concepts are embodied as substructures within the records which store database reference numbers of other records. "Knowledge" is thus embodied in the resulting network of records and cross references between records.
An effect of this system for Knowledge Representation is the creation of a massively cross-referenced database wherein the cross-referencing is the essence of the database instead of an adjunct or supplement thereto. All of the cross referencing is transparent to the user. An advantage of this system is thus that it achieves the implementation of "knowledge" representation in a computer instead of just data storage, and thus may be contemplated as a "thought" processing system as opposed to a conventional "data" processing system.
The pattern recognition, storage, and use module (1b) enables the representation of abstractions of the patterns of relationships in the knowledge representation. These abstractions of the patterns of relationships are stored as relationships within the Knowledge Representation. When these stored patterns are used in conjunction with means for editing the network of the knowledge representation, the result is intelligent behavior reminiscent of some types of expert systems. The results are, however, achieved by means novel to this invention.
If, for example, in the creation of a chemical processing plant five different kinds of instruments have been used in subassemblies of a tank, upon creation of another tank, the system will suggest the five instruments as likely subassemblies to the system user. Because this is a "learn by use" system instead of an a priori declaration-of-rules type system, the system "gets smarter" the more it is used.
The Knowledge Representation system enables the implementation of a Natural Language Interface (1c) with the Knowledge Representation Database. The Natural Language Interface enables human language interaction with the Knowledge Representation. This is accomplished by recognizing possible patterns (or schemas) of relationship between the concepts in the database. Human language queries or statements are then evaluated by matching patterns in the expression to the patterns of relationship in the knowledge representation database by means of serial parsing a primary characteristic of which is the use of the location of a recognized expression in the Knowledge Representation Database instead of the grammatical function.
This means, for example, that a system user can ask for `all devices connected to FCV100 and not in cabinet M4F` directly, without resorting to any special commands for structured query languages.
A major consequence of the Knowledge Representation system of this invention is enabling the Knowledge Representation to be "viewed" or perceived through a multitude of documents, through the (1d) means for automatically deriving a plurality of documents of the Knowledge Representation. The Knowledge Representation is not oriented to representation of data in any one particular document or view format: rather, it is enabling of all possible documents. Given the view, the computer can automatically derive any specific document embodying portions of the information in the Knowledge Representation Database.
Both traditional and non-traditional documents which illustrate or describe portions of the concepts and relationships in the knowledge representation can be implemented in the system. Examples of traditional documents include schematic diagrams, dimensioned drawings, standard database forms, text based documents, spreadsheet and financial summaries, etc.
For example, a valve may appear in as many as sixteen different documents in the documentation for a process plant, represented by four or five different icons.
The knowledge representation supporting the needed relationships can be accessed by the program defining the view to create the appropriate descriptive database of concepts pertaining to the document. The program defining the view will then select the appropriate icons and morphology sequentially and can develop all sixteen documents with the valve appearing in its different icon forms and in the different document formats.
Each view is comprised of a plurality of classes. Each class is comprised of a plurality of document types. All specific documents are instances of a view, class, and type. Views, classes and types are implemented as programmed means.
Views embody procedures for defining relationship icons and coordination with the means for user interaction.
Classes embody the definition format and icon placement (i.e. grammar).
Types embody procedures for identifying the concepts relevant to the document by means of reading concepts in networks of defining and auxiliary relationships and embody procedures for icon assignment (i.e. vocabulary).
The view documents are comprised of icons representing the concepts and relationships pertinent to the document. These icons are created by the view program. The icon definitions contain the reference numbers of the concepts or relationships in the knowledge representation which the icon represents. Each icon is thus associated with a plurality of distinct items in the Knowledge and Descriptive (discussed below) databases, each of which is potentially symbolized by the icon.
The (1e) means for user interface with the Knowledge Representation through the documents enables a plurality of behaviors for each icon based on interpretation implied by the context. A document is comprised of icons representing a small subset of the concepts and relationships present in the Knowledge Representation Database. An icon can be interpreted as representing the plurality of implied relationships in the network. Utilizing these implied meanings allows the invention to develop extraordinarily context sensitive interaction with the Knowledge Representation. This is achieved by means of decision trees of system responses designed for each view where the substance of the decision tree is the evaluation of the interpretation implied by the context of the interaction. This evaluation of context is without precedent in the art and enables the novel features of the means for user interaction of the invention.
The user interface modules integrate the principle characteristics of GUI, Hypertext, OLE, and context sensitive programming in a single integrated user environment. The icons may behave like Graphical User Interface (GUI) icons in that they can trigger the procedures appropriate to the manipulation of the icon. The icons may also behave like Hypertext links in that they are linked to procedures that can automatically derive all view documents of the concept and all concepts and relationships associated with the concept. The icons may also behave like Object Linking Embedding (OLE) systems in that the icon can be the launch point for an external program or file represented by the icon.
(1a) MEANS FOR KNOWLEDGE REPRESENTATION
FIG. 3 provides a schematic summary of the means for knowledge representation which is an expansion and annotation of the FIG. 1 (1a) Means for Knowledge Representation. Knowledge representation embodies knowledge as information stored in a plurality of records in a computer database. Each record is comprised of substructures (herein called relationships) which contain reference numbers to other records. Relationships are comprised of two constituents: a characterization of the relationship; and a value for the relationship. These relationships define the network of knowledge among the plurality of records.
On a micro level, the network is comprised of the records and relationships stored in the computer database. On a macro level, the essence of the invention is the totality of the network comprised of the plurality of records and relationships. The Knowledge Representation Database stores information in a plurality of records in a computer, and represents relationships between the records by storing record reference numbers within the records.
Record Operations (3b) are programmed basic operations for editing and interacting with the records comprising the Knowledge Representation Database. Both Input operations (3c) which store information in the records, and Output operations (3d) which retrieve stored information from the records are provided.
Network Operations (3e) are programmed basic operations for interacting with the network of concepts and relationships in the Knowledge Representation Database. The Network Operations transfer information between the Knowledge Representation Database and the Descriptive Database (3h). The Network Operations thus interpret and translate the structure of both databases. The "Save" operation (3f) saves information from the (3h) Descriptive Database in the Knowledge Representation Database, using the Input Record operation (3c). The Save operations are useful in situations where modification to the Knowledge Representation Database is to be buffered by allowing user modification first to the Descriptive Database. If the Descriptive Database (3h) is used to buffer the changes, then the Save operations are used to transfer the modified data from the Descriptive Database to the Knowledge Representation Database upon user invocation of the save operation.
The "Read" operation (3g) reads information from the Knowledge Representation Database by using the unit operations of the Output Record operation (3d). The Read operation is able to retrieve information in the Knowledge Representation Database network through rules of Relationship inheritance (further discussed below) by which records are retrieved according to reference numbers found within other records. The Read operation further provides the means for limiting the network traversal and deriving descriptions for "Active" concepts (further discussed below) in the Knowledge Representation Database, and for storing the descriptions in the Descriptive Database. The Read operations are described in further detail subsequently. The Read operations assemble a specific Descriptive Database from the general concepts and attributes in the Knowledge Representation Database.
The Descriptive Database (3h) is a database which stores the information relevant to the description of a specific concept or concepts that is distinct from the general concepts of the Knowledge Representation Database, while maintaining identification of the corresponding reference numbers in the Knowledge Representation Database of all components and relationships constituting the specific concept description.
The data structures of the Descriptive Database associate various record reference numbers of the relevant records in the Knowledge Representation Database with the information contained in the records to provide a plurality of associations for the information in a specific environment or perspective. The Descriptive Database is a "working" non-permanent database. The transfer of information to the Descriptive Database from the Knowledge Representation Database is made to consolidate the relationships in the concept records of the Knowledge Representation Database which are expressed as references to other concepts into descriptions of the concepts themselves. The description of the concepts facilitate the human-perceivable views, and consequently user interaction with the Knowledge Representation Database.
The Descriptive Database is called "descriptive" because it is an assembly of a set of relationships which describe a particular concept in the Knowledge Representation Database; and it serves as an intermediary between the Knowledge Representation Database and the (1d) Document module and (1e) View User Interface (FIG. 1) where the "views" provide the human understandable depictions of the knowledge in the Knowledge Representation Database in the form of documents such as tree diagrams, schematic diagrams, and text forms.
The Concept and Relationship Editor (3i) performs operations relevant to editing the concepts and relationships comprising the records of the Knowledge Representation Database. The Concept Editor may add and delete concepts to the Knowledge Representation Databasel including establishing fundamental relationships required to assure that all added concepts are linked to appropriate system concepts. The Relationship Editor performs operations relevant to editing relationships in the Knowledge Representation Database. The Relationship Editor is used to edit both the fundamental relationships and the relationship list of each concept record, including editing both the characterization of the relationships and the Values of the relationships.
(3a) KNOWLEDGE REPRESENTATION DATABASE
The Knowledge Representation Database will generally be implemented in a plurality of database files as illustrated in FIG. 10. The Knowledge Representation Database will always consist of at least one Environment Database (4a) and associated index(es) containing both the Attribute Property, Attribute and Component libraries common to all Projects. This database is referred to as the Environment Database, in that it provides the environment for the creation of specific projects. The Environment Database may be comprised of a plurality of databases with associated index(es). In such case, the plurality of databases will be comprised of databases containing the same information as identified above, wherein the information is divided and arranged within the plurality of files.
The Knowledge Representation Database will also generally consist of a plurality of Project libraries (4b). The projects are typically implemented as separate databases with associated index(es). These databases are referred to as "Project Databases", in that each project database contains the project library for a project. If the system is being implemented for a knowledge domain characterized by single project maintenance, then combining the Environment and Project libraries in a single database file may be preferable.
Most real world knowledge domain applications have an environment comprised of a set of Attributes and Components which are used to construct a variety of specific Projects. An organization working in such a knowledge domain will create Projects which are networks of specific instances of the components. The Projects embody the specific knowledge required to achieve an objective of the organization.
For the purposes of the following disclosure, and the preferred embodiment, a multi-project scheme as illustrated in FIG. 4 will be presented, wherein each project is contained in a separate file with all projects referencing a common Environment Database. The single database case is a simplification and easy adaptation of the multi-project scheme and therefor will not be discussed or presented further. The Values of the relationships are comprised of a plurality of domains which accommodate various data types which may be stored. Each of these domains potentially require distinct modes of editing and initiating values of that domain.
The relationship value editor is typically comprised of a plurality of editors, each of which is designed to facilitate the editing of a particular value domain.
Each of the constituent components mentioned above will now be discussed in detail.
Each record in the knowledge representation database corresponds to a concept. Concepts are named points in the network of relationships comprising the Knowledge Representation. Each record stores a plurality of relationships. Concepts can be visualized as points or nodes in a network. A large number of relationships radiate from each concept to other concepts within the knowledge representation.
Each record has a unique record reference number. This reference number is permanently assigned to the record. The reference number is used by the computer system to refer to the concept instead of the name of the concept because the reference number is unique whereas the name is often not unique. The reference numbers are always used in defining relationships.
In the simplest conceptualization, a record representing a concept in a computerized system is comprised of a list of data structures for storing relationships: the record is comprised of a list of relationships to other concepts. In its simplest form, knowledge is represented by a plurality of records, each of which stores a plurality of relationships to the other records.
Relationships provide the means for storing the cross references in the plurality of records comprising the network. A plurality of relationships are stored within each record in the Knowledge Representation. Relationships store the operating system reference numbers defining the connections between concepts in knowledge representation. Relationships are comprised of: 1) a Characterization or Attribute that is a reference number of a concept record that identifies the properties of the relationship; and 2) a value (or values) that is the object of the relationship.
The Characterization is the identification of the nature of the relationship between two concepts. For example, assume `Lynn` is a concept and `Wendy` is a concept. If it is true that `Lynn` and `Wendy` love each other, then a Characterization of a relationship between `Lynn` and `Wendy` is `love`. The Attribute or Characterization of their relationship is thus `love`.
Values store the object of the relationship. The Values may be either internal or external. For example, if `Lynn` has the Attribute of `love` and `Lynn` loves `Wendy`, then `Wendy` is the Value of the relationship characterized by the Attribute of `love`.
This relationship is formed in a record where the concept is `Lynn`; where the Characterization portion of the relationship contains the reference number of the record representing `love` and the Value portion of the relation either contains `Wendy` or a reference to the record representing `Wendy` as a concept.
Internal Values will typically be comprised of: 1) a reference number of the concept that is the object of the relationship; and 2) a reciprocal Characterization that is the reference number of the concept that characterizes the relationship from the point of view of the object concept.
External Values will typically be comprised of data types other than reference numbers. In some applications, a mixture of internal and external Values may be desired. These mixed values also may be accommodated under the provisions this invention.
In all real embodiments, some concepts will be external to the knowledge representation. Such concepts will be known by name only. The name of the external concept will be meaningful to a human user, but the relationships maintained by the named eternal concept will be unknown to the knowledge representation. External values will be stored as some standard data type. For example if `color` is the Characterization and the Value is an external concept `blue` then the ASCII characters `blue` would be stored as the valve.
Internal relationships are, in general, reciprocal, meaning that if A is related to B then B is also related to A. It is typically useful to record this reciprocal Characterization within the reciprocal relationships because in many cases the characterizations are different. The reciprocal relationship is the characterization within the object concept which is the characterization of the relationship whose object is the source concept.
For example, if `Lynn` and `Wendy` are both internal concepts and, if `Lynn's` relationship with `Wendy` is characterized by `wife` and `Wendy's` relationship with `Lynn` is characterized by `husband`, then `husband` is the reciprocal characterization for `Lynn's` relationship with `Wendy`. Storing `husband` as the reciprocal characterization within the relationship characterized by `wife` will provide important information concerning the relationship between `Lynn` and `Wendy`. Similarly, `wife` is a reciprocal characterization for `Wendy's` relationship with `Lynn`. Note that the record reference numbers of `wife` and `husband` would be stored in the `Wendy` and `Lynn` records.
FIG. 5 illustrates that references in values of reciprocal relationships must correlate. (5a) and (5b) represent Attribute concepts used in characterizing the relationships between (5c) and (5d) which represent related concepts. The dots illustrate the record. Below each dot a name for the concept and the record reference number (the reference numbers are always preceded by .about. (tilde) in the illustrations) are shown. Arrows between the dots illustrate the references between the records. Items (5e) and (5f) illustrate the relationships which would be stored in the records representing (5c) and (5d) respectively. Item (5e) is comprised of a (5g) characterization of the relationship which stores the reference number of (5a), and the internal (5h) value structure which is comprised of the reference number of the attribute of (5b) and the reference number of the concept (5d) which it is connected to. Item (5f) has the reciprocal structure with a val referencing (5a) and (5c).
FIG. 6 illustrates the organization of the Knowledge Representation Database. The system concepts of (6a) Properties, (6b) Strata, and (6c) Attribute Classes, fundamental relationships of Intrastratum, (6g) Taxonomy, (6h) Composition and (6i) Interstrata, and (6f) relationship characterizations provide the essential large scale structures for the knowledge representation. A result of the system concepts and the fundamental relationships is that the knowledge representation has a structure that may be visualized as a tree structured hierarchy.
This hierarchical structure is clear if (6i) Interstrata relationships are suppressed and examples of (6b) Strata, (6c) Attribute Classes, and (6e) User Concepts are provided as in FIG. 7. Note that the interstrata relationships in the tree structured hierarchies of FIG. 7 have specific meanings: the organizing principle of the Attribute and Component strata can be thought of as (7a) taxonomy (i.e. Class and Subclass); while the organizing principle of the Project stratum can be thought of as (7b) composition (i.e. structure and substructure).
FIG. 8 summarizes the occurrence of the fundamental relationships in the records of each of the four typical strata levels of abstraction. The (level of abstraction) system concepts characterize which of the relationships are present in the records of each library. There are two types of cross references between levels of abstraction: (8e) interstrata relationships are reciprocal relationships between concepts of different levels of abstraction (8d) relationship characterization reference numbers always belong to a level of abstraction higher than the level of the concept storing the relationship. This means that the characterizations of Attribute relationships reference only Attribute Properties, and the characterization of relationships of components and projects reference Attributes.
The use of reciprocal relationships in the fundamental relationships enables traversal through the network in either direction. This enables queries based on an objects Class or Subclass, Structure, or Substructure, Type, or Instances. In some implementations of the invention, the reciprocal relationships will not be expressed (e.g. a concept may have a class but it is not referred to as a subclass). However, this will seriously reduce the effectiveness of the Knowledge Representation Database and eliminate some important properties of the Natural Language Interface and the Plurality of views which may be implemented for the Knowledge Representation.
The intrastratum and interstrata relationships are called fundamental relationships herein. The intrastratum relationship is required for all strata. The interstrata relationship is required for all project concepts.
System concepts are those concepts which the programmed (code) portion of the system recognizes and requires in order to interpret the knowledge network. System concepts represent code defined interpretation in the knowledge network. All other concepts are user concepts. References to system concepts in the network are, in effect references to code interpretation. The code embodying the meaning of system concepts is distributed throughout the program portion of the system since these concepts have system wide implications.
FIG. 9 is an adaptation of FIG. 7 designed to highlight the system concepts included in FIG. 7. These are examples of system concept included in the preferred embodiment. FIG. 9 also indicates the intrastratum organization of these concepts as a tree structured diagram and associates examples of typical user concepts. There are three classes of system concepts which are recommended for any embodiment of the Knowledge Representation (see FIG. 9): (9b) Attribute Properties, (9a) Library or Strata of Abstraction, and (9c) Attribute Classes. Each of these classes of system concepts are comprised of a plurality of individual concepts which are recognized by the programmed code in order to interpret the meaning of the knowledge network. All (9b) Attribute property concepts are system concepts in that they comprise the highest level of abstraction and are the basis for the definition of all lower strata. The Attribute Properties must be implemented as system concepts in any embodiment of the invention. The (9a) Library or Strata of abstraction system concepts define which of characteristic types of fundamental relationships apply to the concepts on each level of abstraction. The (9A) Library System concepts embody the notion of the inter and intra strata relationships appropriate to each strata. There are four strata which will always be present: Attribute Properties, Attribute, Component, and Project.
The (9c) Attribute Class system concepts define which attribute properties will characterize the relationships of the descendants thereof. The descendants of the Attribute Classes are user defined attributes which characterize user defined relationships. Attribute classes could be defined by means of a plurality of relationships characterized by Attribute Properties. It is simpler and more convenient to explicitly identify the Attribute class concept as system concepts and embody system definition of the class behavior.
There are four characteristic levels of abstraction which are typical of knowledge and which are included as examples in the preferred embodiment and comprise the basis for the subsequent discussion. The concept of the invention comprises extension to additional strata and to pluralities of related strata within each type. Subsequent discussion will focus on the four examples in order to achieve an economy of exposition. The four strata are summarized in FIG. 8 as being comprised of 1) properties; 2) attributes; 3) components; and 4) projects. FIG. 8 summarizes the strata characteristics. Column A identifies each of the four strata. Column B provides a brief description of the strata in terms of the function of concepts in each strata within the knowledge representation. Column C identifies the intrastratum connectivity in terms of the significance of relationship used to connect all of concepts on a particular stratum. Column D of FIG. 8 shows the stratum used in the characterization of relationship for each of the stratum. And Column E shows the interstrata relationships maintained at each stratum.
The Attribute Properties are the most abstract level of knowledge represented in a knowledge representation. Properties are the concepts characterizing relationships required to define attributes. They can be thought of as the attributes of attributes in that they are the only class of concepts used as characterizations within the relationships of concepts comprising the attribute strata.
FIG. 10 summarizes some typical useful Attribute Properties which are implemented in the embodiment of the invention included in the Appendix. These are provided as a suggestion to a system designer implementing a derivative embodiment of the invention. The Attribute Properties comprise an unbounded set, which can be augmented as desired. Many useful Attribute Properties can be defined to achieve specific design objectives.
Attributes are the class of concepts most commonly thought of as attributes of characterization of relationships. For example, love, husband, wife, height, date, time, would all be attribute concepts. Attributes are the second highest level of abstraction in that they are comprised of a multiplicity of relationships the characterization of each of the relationships is always an incomplete property.
FIG. 9 illustrates an example set of Attribute Class System concepts in the dashed box. The number of Attribute Classes can be reduced or augmented within the spirit of the invention. The Attribute Class System Concepts are organized under the Attribute Library System Concept. Useful embodiments of the invention can be implemented using only one or two classes.
FIG. 11 summarizes typical Attribute Classes which have been found useful and most of which are included in the code set forth in the appendix. These Attribute Classes are provided as a suggestion to a system designer implementing the invention. The Attribute Classes comprise an unbounded set which may be augmented as desired. Many useful Attribute Classes can be defined to achieve specific design objectives in modeling knowledge domains.
The Attribute Classes define which characterizations of relationships apply to the user concepts of the class and limit the values that said relationships may assume. The Attribute Classes define or constrain any behaviors, properties, or values which apply to a class of user concepts. The Attribute Classes may be seen as the enabling means for user definition of concepts which can be used in the characterization of relationships maintained by Component and Project concepts.
1) Database Data Type Domains Declaration
FIG. 12 illustrates an example of a data type domain declaration that enables the creation of a plurality of records and relationships therebetween for storage of the information comprising the network of information in the Knowledge Representation Database. The record structures and substructures are used by the program to interpret the information stored in the records and substructures. The domain declaration is generally common to all records comprising the Knowledge Representation Database. However, derivative embodiments may include different record structures, depending on the library or class. The domain declaration of FIG. 12 is based on PROLOG language conventions, and can easily be adapted to the programming environment of choice.
The data domain declaration for the records is preferred for storing information in the Knowledge Representation Database. The specific characteristics of the domain declarations disclosed herein are unique to the invention and constitute a significant contribution to the state of the art. FIG. 12 illustrates optimizations for representing the fundamental relationships and for representing attribute properties in the database records. Both of these optimizations will be discussed in following subsections.
The discussion of the optimizations provides a convenient forum for discussing the principles of concept representation which are employed in the invention. In database domain declaration, the constituents must be declared prior to declaring the whole. In FIG. 12, the whole is the concept declaration (12r), which is the statement of the record structure.
A "Concept" is represented as a complex record structure comprised of a Name (12a), Parents (12o), Children (12a), Interstrata (12q), and a Relationship List (12n). The Name is the name of the represented concept. The fundamental relationships are embodied in the list of parents, children, and interstrata. The Relationship List stores the relationships maintained by the record. The order of these constituents within the record structure is arbitrary.
The data type declaration (or equivalent implementations) illustrated in the example of FIG. 12 will assure functional implementation of the invention. There are numerous acceptable variants for the declarations which can be implemented to optimize system performance (several of which are implemented in the embodiment included in the appendix). However, the key features of the domains declaration of FIG. 12 will persist in derivative works.
The Name is the designator for the Concept, and is usually a data string although other data types may be included as appropriate. Note that the segregation of the name is for convenience only. The name is also stored as an external value in the relationship list without appearing as a separate item in the declaration of the Concept.
The Characterization (12b) is a reference number of a Concept represented in the Knowledge Representation Database. The Characterization always references either a Concept in the Attribute Library or a Concept in the Properties of Attributes Library. Properties of attributes characterize only the relationships of Attribute concepts. Attribute concepts characterize all other relationships.
The Value (12g) is always either a reference number to a concept or concepts in the Knowledge Representation Database; to concepts external to the knowledge representation; or to a combination of both internal and external concepts. Internal Values (12c) are a class of Values containing only reference numbers of records in the Knowledge Representation Database. The form of Internal Values illustrated is comprised of two reference numbers. One of the reference numbers identifies the Concept record related to, while the second reference number identifies the characterization of the reciprocal relationship. The statement of (12c) Internal Values shown is the most common and characteristic type of Internal Value used in the Knowledge Representation Database, however, numerous additional structures derivative of the principles disclosed herein may be implemented at the system designer's discretion. External Values (12d) are a class of values which contain no reference numbers since they reference external concepts not represented as records in the Knowledge Representation Database. External values typically consist of standard data types of information. Since the domain declaration for values is complex in this invention, the standard domains must be embedded in a complex declaration which will provide structural cues to the data type of the external concept. A Val (12e) is either an Internal or External Value. It is an intermediate structure used to define Mixed Values (12f). Mixed Values are a class of values containing both reference numbers and standard data types. The Mixed Values can most easily be represented as a list of (12e) Vals. The notation "Val*" is a PROLOG notation signifying a list of Vals. The "*" indicates a list. This notation is similar to notation in many other languages and is used subsequently herein.
(12h) through (12k) are declarations of the standard data type for the attribute properties of Prompt, Data.sub.-- type, Field.sub.-- Length, and Location. This is an optimization of the implementation of Attribute Properties that will be subsequently discussed. Properties (12l) declares the properties structure to consist of: (12h) Prompt, (12i) Data.sub.-- type, (12j) Field.sub.-- length, and (12k) Location. The order of these elements within the structure is arbitrary. Relationship (12m) allows (12l) Properties as an acceptable relationship. (12m) Relationships are a complex data type associating a (12b) characterization, which is a reference number of an attribute or property characterizing the relationship, with a (12g) Value. The reason for this structure is that each relationship has a characterization or attribute and a value or qualitative measure of the relationship. The (12b) characterization in the relationship is the source of the relationship characterization (6f) illustrated in FIG. 6.
All concepts may have an unlimited number of relationships; therefore a (12n) Relationship List provides a structure for enumerating the relationships maintained by a record, as a list of relationships. The (12n) Relationship List structure must allow for the dynamic inclusion of relationships. This dynamic inclusion is a property of the development system and one of the reasons that the development environment should not restrict the record length.
The (12o) parents, (12p) children, and (12q) interstrata, are lists of reference numbers used to store the fundamental relationships of the Concept record. The (12o) Parents are used to store the reference numbers indicating the hierarchical progenitor within the abstraction stratum. The (12p) children are used to store the reference numbers indicating the hierarchical descendants within the abstraction stratum. The (12q) Interstrata is used to store either the Type classification or the Type instances of a concept.
FIG. 12 indicates only (12o) Parents, (12p) Children, and (12q) Interstrata, each of which is a reference list, instead of six relationships of the form of (12m). This variation is the optimization of the Representation of Fundamental Relationships the reasons for which are hereafter presented. The reason that the declarations are implemented as a reference list with no characterization is explained in detail in the following discussion.
Optimization of Means for Representing Fundamental Relationships
There are two classes of fundamental relationships which are used to assure network connectivity: intrastratum (intralevel) and interstrata (interlevel), as discussed previously. Each class of fundamental relationships is comprised of reciprocal relationships, so there should be four relationships of the type represented in the form of (12m) relationships, which should be part of the (12n) Relationships List. The optimization included in FIG. 12 enhances the operating speed of the system by: 1) segregating the fundamental relationships from the (12n) Relationship List; 2) eliminating the direct characterization in the fundamental relationships; and 3) explicitly allowing for a list of record reference numbers by declaring the domain as ref* (i.e. reference number list).
The segregation of these fundamental relationships allows the programmed functions requiring these relationships to "grab" a relationship from a record based on the structural cue of the segregation instead of extracting the relationship from the (12n) Relationship List. The reduction from four relationships to three is accomplished by recognizing that the interstrata relationship is not expressed as a reciprocal in any single record because it is a relationship between a project and component record (i.e. the component has an instance relationship with the project record and the project record has a classification (or Type) relationship with the component record) therefore a specific record never has both Type and instance so only one structure for the interstrata relationship need be present in any record. These segregated relationships could be represented with the structure indicated for (12m) relationships in FIG. 12. However, this would provide redundant information since both the characterization reference to an Attribute Library system concept and the structure imposed by the segregation would provide cues for the meaning of the relationships. Such redundancy takes more space in the database and requires more record reading in that each (12b) characterization would need to be read.
By relying only upon the structural cues provided by the segregation we eliminate the characterization, and the relationships can be simplified to a reference list (ref*) as indicated in FIG. 12 for (12o) Parents, (12p) Children, and (12q) interstrata. The use of the reference list instead of just a reference number enables the possibility of multiple relations of the segregated types. A consequence of this optimization is that the system concepts for the characterization of fundamental relationships do not need to be present in the Knowledge Representation since the structure of the record now cues the characterization of the relationship. The programmed code will use the structure for the characterization instead. In a particular embodiment the designer is free to provide additional segregation to distinguish particularly significant relationships; the presence or absence of such segregation is merely an adaptation of the invention. In a specific embodiment, the designer is free to use structural cues to eliminate representing some system concepts as records in the (3a) Knowledge Representation Database.
Optimization of Means for Representing Attribute Properties
The domains declaration illustrated FIG. 12 includes an optimization that allows structural representation of the basic attribute properties. The optimization has been implemented whereby standard Attribute Property system concepts are consolidated into a unique structure thereby eliminating the need for explicit representation of said Attribute Properties as records in the Knowledge Representation Database. This optimization is similar to that illustrated previously wherein the need for explicit representation of the characterization of the fundamental relationships as attribute records in the Knowledge Representation Database was eliminated by segregating the relationships to uniquely defined structures. This optimization is possible because so few attribute properties are essential (in this illustration only four) to successful systems. This optimization is suitable for many implementations of the system, in that useful knowledge representations can be constructed with very few Attribute Properties present as system concepts. Note that even if additional Attribute Property system concepts are added, this optimization would still be applicable and would merely be supplemented by suitable modification to the (12l) properties declaration or representing the additional attribute properties as system concepts for use as (12b) characterizations in (12m) relationships.
Notes on Additional Optimizations for Domains Declaration
Some of the additional optimizations include implementing: security; history logging (date and time stamping of last modification to record); explicit library identification within the record instead of implicitly through the network; and segregated identification of the characterization of the name of the record. Most of these optimizations are included in the preferred embodiment. They are not considered essential to the invention and therefor no claims are made with respect to these optimizations. They are representative of optimizations and extensions that will be present in any derivative embodiment of the principles of the invention.
Programmed Code Recognition of System Concepts
The programmed code of the invention uses the System Concepts and Fundamental Relationships in order to interpret the significance of the network. The System Concepts and Fundamental Relationships provide the cues for the interpretation of the network as a whole. The programmed code recognition of System Concepts is comprised of two procedures: steps for designating system concepts; and steps for recognizing a system concept. Both of these must be implemented by the system designer. The essence of the code for designating system concepts is to create a distinction for system concepts (as opposed to external or extrinsic concepts) whereby either the name or the reference number of all system concepts can be readily identified. Such code will readily be implementable by a skilled practitioner.
The preferred embodiment uses three procedures for designating system concepts. These three procedures are redundant, and illustrate the range of possible implementations. Any one of the procedures would be sufficient. The three procedures are: 1) to designate system concepts by means of a supplementary index of reference numbers and names of system concepts; 2) to use an internal database to designate system concepts wherein the system concept reference numbers and names are provided to the internal database at system start-up; and 3) to include a supplementary structure in the record statements whereby system concepts are designated.
FIG. 13 illustrates a Flow Diagram For Recognition of System Concepts. Two procedures are illustrated: 1) (13a) through (13d) illustrate steps for recognizing a concept as a system concept; 2) (13e) through (13h) illustrate steps for recognizing a concept as a specific system concept. Each of these procedures are used within the program to utilize system concepts in interpreting the network. Steps (13a) through (13d) illustrate programmed procedures for recognizing a concept as a system concept. The result of these steps will either be an outcome of (13c) No or (13d) Yes. The essence of this procedure is to test whether either the (13a) Name is distinguished for a system concept or the (13b) Reference Number is distinguished for a system concept. The input to step (13a) is either the name, the reference number, or both the name and the reference number of a concept record to be tested. Step (13a) then compares the name with all names of predesignated system concepts to determine if the name is that of a system concept. The program determines that the concept record is a system concept if either the name or the reference number has been designated as identifying a system concept. Note that the name of a concept is often ambiguous in that it is possible for several concepts to have the same name. The only unambiguous test is based on the reference number of the record, which is always unique. If the reference number is furnished at step (13a) then the test at step (13a) should fail (NO) so that the reference number can be tested instead of the name in Step (13b). This will eliminate the ambiguity inherent in testing only the name. If the name is recognized as a system concept in step (13a), then the (13d) outcome is "YES". If the name is not recognized as a system concept in step (13a) or a reference number was furnished to step (13a), then the (25a) outcome is "NO".
Step (13b) compares the reference number with all reference numbers of designated system concepts to determine if the reference number is that of a system concept. If the reference number is recognized as a system concept in step (13b) then the (13d) outcome is "YES". If the reference number is not recognized as a system concept in step (13b) then the (13c) outcome is "NO".
The second procedure shown in FIG. 13 determines whether a particular concept is a specific system concept. This procedure comprises steps (13e) through (13h). The input to step (13e) must be the reference number of the current concept to be identified. Step (13e) gets the reference number of the specific system concept record to be identified. The specific system concept to be identified must be programmed into the section of code either as the name or the reference number of a system concept. The reference number is obtained from the procedure for designating system concepts as explained above. Step (13f) then compares the current concept reference number with the system concept reference number. If the reference numbers are the same then the (13h) outcome is "YES". If the reference numbers are different then the (13g) outcome is "NO".
Assuring that System Concepts are Inviolate
The system concepts must be protected from the effects of inappropriate Record Operations. The Input Operations protect the system concepts by prohibiting any modification to the information in the structure of records designated as representing system concepts.
System concepts can be designated as such through many possible methods. The essential requirement is only that system concepts be distinguished from user concepts in a readily determinable fashion. Suitable methods for distinguishing system concepts from user concepts include: prefacing the name with an extended ASCII sequence; adding a designator within the record structure; adding a designator within the index files; and maintaining a separate file containing an index or list of system concepts.
FIG. 14 illustrates program steps for assuring that all system concepts are maintained as inviolate in the system. The steps must be implemented as a preface to each operation which potentially could improperly modify a system concept.
Operations which modify a record that are unacceptable for system concepts records are functions which will either: delete the record; change the name of the record; change the Parents reference; change the Type; and change the Relationship List. Whenever a call to these input operations is made (step 14a) the steps of FIG. 14 must be invoked. Each call to a modifying operation must immediately test to see if the target record of the input operation is a system concept (step 14b). This can be accomplished by steps (13a) through (13d) or (13e) through (13h) in FIG. 13. If the target record is not a system concept, then the input operation proceeds (step 14d). If the target record is a system concept a message is displayed to the user explaining that the requested operation can not be performed on a system concept (step 14c), followed by an exit of the called operation (step 14e).
A variation of this procedure that may be useful in some situations is to apply the test to a procedure that assembles a list of input operations which are applicable to a particular record so that the unacceptable operations are never presented as options to the user.
In the preferred embodiment both the steps illustrated in FIG. 14 and the above-described variation are used to provide redundancy for protecting the system concepts as inviolate.
(3b)Record Operations
The Record Operations (FIG. 3b) are basic operations for interaction with the records of the Knowledge Representation Database. Record operations are comprised of: Input operations (3c) whereby records or record declarations within records are created or replaced in the Knowledge Representation Database; and Output operations (3d) whereby records or record declarations within records in the Knowledge Representation Database are read out and reported to the user.
The Record Operations are implemented to handle the information contained within the structures of individual records in the Knowledge Representation Database. As such the significance of the structure of the records (name, relationships, etc.) must be programmed into the Record Operations.
The significance of the network structure of the Knowledge Representation Database is contained in the higher level functions of the Network Operations (3e), the Concept Editor and the Relationship Editor (3i), each of which uses the Record Operations as basic functions for the implementation of network-related functions. The attached microfiche appendix contains specific implementations of appropriate Record Operations.
(3e) Network Operations
The Network Operations (3e) comprise a plurality of steps for interaction with the network structure of the Knowledge Representation Database as embedded within the individual records constituting the Database. Network Operations are comprised of a plurality of functions which are programmed with an understanding of the network. There are two major classes of functions comprised of: Save operations (3f) whereby information stored in the Descriptive Database is saved in the network of records of the Knowledge Representation Database, and Read operations (3g) whereby a portion of the network of the Knowledge Representation Database is translated into the Descriptive Database. The Network Operations do not understand the record structure of the database in that all interactions with the records of the Knowledge Representation Database are conducted through the Record Operations. The Network operation procedures coordinate sequences of Record Operations, which sequences comprise network operations. The network resides in the relationships between a plurality of related records in the Database as found from the cross-reference record numbers embedded therein. The programmed sequence of Record Operations which defines Network Operations embodies the understanding of the network structure.
Many of the programmed functions for interpretation of the network have a characteristic of traversing some class or classes of relationships between concepts and assembling information about the concepts in the traverse path.
FIG. 15 illustrates a flow diagram of programmed means for assembling an ancestors list of records constituting progenitors of an individual record as an example of network traversal. Step (15a) sets the next reference number equal to the active reference number. The "Active" is the current record reference number for which the ancestor list is to be derived. Step (15b) reads the Parent and Child record names from the active record. The read operation of step (15b) is one of the functions of the Record Operations. Step (15c) tests to see whether the Parent list is nil. The only record in the network for which the parent list is nil is the root record. Thus, the presence of a nil Parent list means that the ancestry of the individual record has been traced clear to the root record. Step (15d) adds the name read from the record to a name list. This name list is an output of the ancestry of the individual record. The resulting output of the ancestry tracing process will be the name list and also an ancestor list, wherein the ancestor list is comprised of the list of reference numbers of the records corresponding to the names in the name list.
Step (15e) adds the parent record reference number to the ancestor list in the case where, in step (15c), the Parent list is not nil. Step (15f) adds the name of the record being read to the name list, followed by Step (15g) which sets the next reference number equal to the parent reference number from the parent list.
The process then cycles back to step (15b), with the next reference number equal to the parent record found in the previous record's parent list. Note that the name added to the list in steps (15d) and (15f) is the name of the record being read, whereas the parent added in step (15e) is the reference number of the parent record of the record being read. Thus, although the parent reference number is added in step (15e) and the name is added in step (15f), the final parent for the root name ultimately must be added in step (15d), when there are no more parents. Specific network operation code is included in the microfiche appendix.
(3f) Save Functions
The Save functions (3f) consists of programmed operations for assembling and structuring information stored in the Descriptive Database and storing the information in the appropriate records of the Knowledge Representation Database. Save is only required if the Descriptive Database is used to buffer editing operations so that these operations do not directly affect the Knowledge Representation Database, but rather are modifications to the Descriptive Database. If the Descriptive Database is used to buffer the Knowledge Representation from the editing operations, then save functions are required in order to transfer the changes made to the Descriptive Database into the Knowledge Representation Database. The transfer between databases occurs upon a user event requesting an update to the Knowledge Representation Database.
The Save operations are implemented as programmed code. Save translates the information in the Descriptive Database by applying a sequence of Record Operations required to store that information into the Knowledge Representation Database. The Save operation uses the record reference numbers of the Knowledge Representation Database which are associated with the information in the Descriptive Database to identify the record and record substructure where the updated information should be stored.
The Descriptive Database contains information from a plurality of records of the Knowledge Representation Database, together with view document-specific icon and locational data which is not part of the Knowledge Representation Database. The Save operation saves only the relevant information in the Descriptive Database at the appropriate location in the Knowledge Representation Database.
FIG. 16 illustrates a Flow Diagram of programmed means for Saving Information Stored in the Descriptive Database by storing it in the Knowledge Representation Database. The overall structure of the procedure illustrated in FIG. 16 is to process all active concepts in the Descriptive Database by getting the next active reference number in the database and cycling through the procedure for each active concept until all active concepts have been processed.
The Descriptive Database may include a plurality of Active concepts. The "Active" will be indicated in one of the fields of each of the plurality of records in the Descriptive Database comprising the description of the Active concept.
Step (16a) identifies a reference number of an active concept record in the Descriptive Database. Step (16b) assembles all of the relationships pertaining to the Active which are stored at the active record into a Relationship.sub.-- list (see FIG. 12n). The relationships pertaining to the Active which are stored at the Active record are identified by means of the Source field (23b) in the records of the Descriptive Database.
A consequence of the procedure for Relationship Inheritance is that the only Source for relationships in the description of the Active concept (for which all relationships in the relationships list are present as corresponding records in the Descriptive Database) is the record of the Active concept. This is the reason that Save applies only to the Active record.
Step (16c) replaces the relationship list in the Active record with the relationship list assembled in Step (16b) from the Descriptive Database.
Step (16d) tests to see if any other Active concepts are in the Descriptive Database which have not yet been saved. If "YES" (16e) then cycle back to Step (16a) to get the next active record reference number. If "NO" (16f) then the save is done.
The microfiche appendix contains specific code implementation of appropriate Save operations.
(3g) Read Functions
The Read functions (3g) reads information stored in the Knowledge Representation Database, appropriately formats the read information, and stores the formatted information in the Descriptive Database. The Descriptive Database is a working non-permanent database. The tran