Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-12-15
2002-08-27
Mizrahi, Diane D. (Department: 2775)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06442566
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to information management systems. More particularly, it relates to a frame-based knowledge representation system built using a relational database.
BACKGROUND ART
One of the growing problems facing scientific researchers is how to integrate and process the enormous amount of data being produced daily. While a great deal of data is available on the World Wide Web, simply having access to the data is useless without robust methods for searching, organizing, and analyzing the data. Various data models have been developed for storing information that can be categorized using ontologies. An ontology is a system that specifies the classes and relations among classes within a domain of discourse. As ontologies become more complex, existing tools for representing data are no longer able to sufficiently represent the data.
Relational database management systems (RDBMS) are by far the most dependable and widely used architectures for building large databases. They contain a few tables of data in which one or a few dependent values are associated with a set of useful independent features that can be searched quickly. An example of a RDBMS table is shown in FIG.
1
. By searching on the names, address and telephone numbers for each person can be retrieved quickly. In general, relational databases are most effective to use and easy to maintain when there are a limited number of tables of information, linked together logically, and with a very large number of records in each table. They are also an ideal solution when the structure of the data model is very well understood, not subject to change, and in routine use. Changes to queries and data fields are difficult to implement without completely taking the system out of use and restructuring the model. For example, adding an email address for each person in the database containing the table of
FIG. 1
requires redesign of the table structure (either a new column or table) and existing queries. Furthermore, for many data sets, the structure is too complex to be represented effectively by a relational database. Straightforward relational representations can leave out important dependencies of interest, and effectively fit the data to the capabilities of the database structure, instead of fitting the structure to the data. When the data model becomes a large network of interacting tables, queries are also much more difficult to write.
More flexible data structures, known as knowledge bases, have been developed to more closely model the entities in the system of interest and the interactions among them. The key distinction between a knowledge base and a relational database is the manner of organization of the data. In a relational database, data is organized into tables that are accessed by specifying rows and columns of the table—the tables do not reflect conceptual knowledge of the data. In contrast, design and organization of knowledge bases requires conceptual knowledge and representation of the data. In a knowledge representation system, all of the concepts in the domain of discourse are organized into a hierarchical tree of classes, with instances of classes located at the leaves of each branch. Further, the attributes associated with instances are stored with the instance, and not distributed throughout all of the tables of a relational data model.
The two primary innovations in knowledge bases have been object oriented databases and frame-based representation systems. Object oriented approaches allow more modular modeling than relational databases. Each piece of data in the system is considered an object, and the properties of an object are stored locally with the object, along with pointers to related objects. Complex data models are easier to implement, and hierarchies of objects can be created to help organize the large amounts of information. These systems typically provide benefits over relational database systems in the richness of available queries over more complex data types. However, object oriented databases have significant drawbacks that have prevented their acquiring a broad base of established users. They require not only that a researcher specify the properties of entities, but also that they map them onto programming language and database structures. Users interested in the stored information often have neither time for nor interest in learning about the underlying database structure. In addition, object oriented databases suffer from the lack of a universally agreed upon query language.
Frame-based representation systems can be considered object oriented architectures that provide built-in support for dynamic and hierarchical data modeling, for distinguishing between general concepts and particular instances of these concepts, for associating particular attributes with each concept, for inheriting attribute values from parent concepts, and for linking concepts with named relationships. They allow modification of the data model without the need to rebuild the structure, and have a common communication protocol for reading to and writing from the knowledge bases. Developers have created several frame-based knowledge representation tools, including Ontolingua (A. Farquhar, R. Fikes, and J. Rice, “The Ontolingua Server: A Tool for Collaborative Ontology Construction,” Tech. Report KSL-96-26, Knowledge Systems Laboratory, Stanford University, Stanford, Calif., 1996); Protégé (M. A. Musen et al., “Protégé-II: An Environment for Reusable Problem-Solving Methods and Domain Ontologies,”
Proc. IJCAI
'93 1993
Int'l Joint Conf. Artificial Intelligence
, Morgan Kaufmann, San Francisco, 1993); and Theo (T. Mitchell et al., “THEO: A Framework for Self-Improving Systems,”
Architectures for Intelligence
, K. Van Lehn, ed., Lawrence Erlbaum, Hillsdale, N.J., 1989). Such tools have an array of features, default reasoning strategies, and knowledge-representation constraints. However, some require users to install special software, and others lack important features, such as a persistent back-end storage system for scalability, facilities for controlling access based on user permissions, an API for prototype development, or easy compatibility with Web protocols.
Several existing frame-based systems map a knowledge model into a relational database, thereby solving the above-described problem of requiring specialized software to implement knowledge representation systems. These systems instead allow developers to use well-known and widely available databases along with their existing tools, providing systems that that are easy to use and access through a variety of interfaces. For example, the PERK database back-end to the GKB-Editor (P. D. Karp, K. L. Myers, and T. Gruber, “The Generic Frame Protocol,”
Proc. IJCAI
-95. 1995
Int'l. Joint Conf. Artificial Intelligence
, Morgan Kaufmann, San Francisco, 1995, pp. 768-774) and EcoCyc frame based knowledge-base tool (P. D. Karp et al., “EcoCyc: Electronic Encyclopedia of
Escherichia Coli
Genes and Metabolism,”
Nucleic Acids Research,
27(1), pp. 55-58, 1999) both use a relational database for storage. The PERK storage system is discussed in detail in P. D. Karp, V. K. Chaudhri, and S. M. Paley, “A Collaborative Environment for Authoring Large Knowledge Bases, 1997. In the PERK system, individual frames (objects and associated attributes) are stored in a RDBMS as compressed ASCII text and are unpacked into memory on demand. Frames must be loaded from the flat file in order to be queried, leading to a start-up delay and limits on scalability. More importantly, the client machine accessing the information stored on PERK must have special software to unwrap the objects and put them in temporary storage.
A knowledge representation model built on a relational database is disclosed in P. M. Nadkarni, “QAV: querying entity-attribute-value metadata in a biomedical database,”
Computer Methods and Programs in Biomedicine
, 53, pp. 93-103, 1997. However, the database structure cannot fully support a frame-based knowledge repre
Abernethy Neil F.
Atman Russ B.
Board of Trustees of the Leland Stanford Junior University
Lumen Intellectual Property Services Inc.
Mizrahi Diane D.
LandOfFree
Frame-based knowledge representation system and methods does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Frame-based knowledge representation system and methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Frame-based knowledge representation system and methods will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2960294