Knowledge representation in AI

Knowledge representation (KR) is the part of artificial intelligence that decides how a system’s knowledge is written down as symbols, what those symbols mean, and which conclusions may be drawn from them. Its main techniques are semantic networks, frames, scripts, description logics, ontologies, RDF, OWL and knowledge graphs.

1. What knowledge representation is

A symbolic AI system reasons by manipulating explicit symbols. Before it can do that, someone has to decide which symbols exist, how they combine, and what follows from what. That decision is knowledge representation, and the field usually pairs it with reasoning under the name knowledge representation and reasoning (KRR). Brachman and Levesque’s textbook treats the two as inseparable: a representation is only as useful as the inferences it supports [1].

Every scheme on this page answers four questions: what the basic unit of knowledge is (a link, a slot, a triple, an axiom); whether its meaning is fixed formally or only by convention; what a program can infer from it, and how fast; and what happens when a fact is missing. The last question separates the closed-world assumption, where what is not stated is false, from the open-world assumption, where it is merely unknown. For how knowledge representation fits into symbolic systems in general, see What is a symbolic system?; for where each technique sits among all symbolic methods, see the symbolic AI techniques hub.

2. Networks and structured objects

Semantic networks

What it is. A semantic network represents concepts as nodes and relations as labelled, directed links. The is-a link carries inheritance: a property stored on bird applies to every kind of bird unless overridden.

Who and when. M. Ross Quillian introduced the semantic network as a model of human semantic memory in 1968 [2]. In 1969 Allan Collins and Quillian tested it: people took longer to verify “a canary can fly” than “a canary can sing”, consistent with the idea that the flying fact is stored once on bird and reached by following a link [3].

Limits. Early networks had no agreed semantics. In “What’s in a Link” (1975) William Woods showed that the same drawing could mean different things, for example whether a link describes one individual, every member of a class, or a typical member [4]. Ronald Brachman’s “What IS-A Is and Isn’t” (1983) catalogued the incompatible readings of the is-a link in use [5]. Those critiques led directly to KL-ONE and description logics (§3). Today the idea lives on in every knowledge graph and in the class hierarchies of ontologies.

Frames

What it is. Marvin Minsky proposed the frame in 1974 as “a data-structure for representing a stereotyped situation” [6]. A frame has slots, each with possible fillers, default values and constraints, and frames are arranged in a hierarchy so that slots and defaults are inherited.

How it works. A Room frame might have slots walls (default 4), ceiling, door; a Kitchen frame inherits them and adds stove. On entering an unfamiliar kitchen, a system fills the slots it observes and assumes the defaults for the rest until evidence overrides them. Frame systems also attached procedures to slots, computing a value when it was needed or checking one when it was added.

Where it is used today. The class-with-attributes pattern passed into object-oriented programming and ontology languages. Limits. Defaults are overridable, so conclusions drawn from them can be withdrawn later; frame reasoning is therefore nonmonotonic, and early frame languages gave no precise account of what could be concluded.

Scripts

What it is. A script is a frame for a sequence of events: a stereotyped episode with roles, props, entry conditions, an ordered set of scenes and typical results. Roger Schank and Robert Abelson, both at Yale, set out the theory in Scripts, Plans, Goals and Understanding (1977) [7].

Worked example. The restaurant script has roles (customer, waiter, cook, cashier), props (tables, menu, food, bill) and scenes (entering, ordering, eating, exiting). Given “Ann went to a restaurant. She ordered lobster. She paid and left”, a script-based reader can answer “Did Ann eat?” with yes, although no sentence says so: eating is the scene between ordering and paying. The program SAM (Script Applier Mechanism), described in the same book, drew this kind of inference automatically.

Today and limits. Scripts are a direct ancestor of case-based reasoning and of the event-schema knowledge that language-understanding research still studies. They fail when a story leaves the script: every deviation has to be anticipated by hand.

Conceptual dependency

What it is. Conceptual dependency (CD) is Roger Schank’s theory of language-independent meaning, introduced in 1969 at Stanford and published in full in Cognitive Psychology in 1972 [8]. The idea: sentences that mean the same thing should map to the same structure, whatever their wording or language.

How it works. Actions are decomposed into a small set of primitive acts, in the usual list eleven: ATRANS (transfer of possession), PTRANS (physical transfer), MTRANS (transfer of information), MBUILD (building new information), PROPEL, MOVE, GRASP, INGEST, EXPEL, SPEAK and ATTEND. “John gave Mary a book” and “Mary received a book from John” both become an ATRANS with actor John, object book, from John, to Mary. “John told Mary” is an MTRANS. Inference rules attach to the primitives: after any ATRANS, the recipient has the object.

Limits. The fixed primitive set loses distinctions (giving, lending and selling differ in ways a single ATRANS does not record), and the choice of primitives was never settled. CD became the internal language of Schank’s script programs.

Conceptual graphs

What it is. John Sowa introduced conceptual graphs in 1976, in the IBM Journal of Research and Development, as a formalism for describing data in the user’s terms [9], and developed them in Conceptual Structures (1984) [10]. The 1984 version took Charles Sanders Peirce’s existential graphs as its logical foundation.

How it works. A conceptual graph is bipartite: concept nodes (a type and optionally a referent) connect only to relation nodes. “A cat is on a mat” is written in the linear form [Cat] → (On) → [Mat], and its logical reading is

Today and limits. Conceptual graphs gave semantic networks a direct translation into first-order logic, and they remain in use in research on natural-language semantics and graph-based reasoning. That expressiveness has the usual price: full first-order reasoning over them is undecidable.

3. Logic-based representation

KL-ONE

What it is. KL-ONE is the knowledge representation system that turned the critiques of semantic networks into a disciplined language. Its best-known description is Brachman and Schmolze’s 1985 overview in Cognitive Science, which notes that it had been developed and refined over a long period and used in a number of research and applied systems [11].

How it works. Knowledge is built from concepts (frame-like descriptions) and roles (relations with restrictions on their fillers). Concepts are either primitive, with necessary conditions only, or defined, with necessary and sufficient conditions. A classifier places each new defined concept at the correct point in the taxonomy automatically, by computing which concepts subsume it.

Why it mattered. Automatic classification needs a precise meaning for every construct, which forced the question of how expensive it is. Brachman and Levesque showed in 1984 that the cost of computing subsumption is extremely sensitive to small changes in the description language: adding one innocent-looking construct can make it intractable [12]. That result defined the research programme of description logics.

Description logics

What it is. Description logics (DLs) are a family of decidable fragments of first-order logic for describing classes (concepts), binary relations (roles) and individuals [13]. A knowledge base has a TBox of terminological axioms and an ABox of assertions about individuals.

Worked example. A TBox axiom defining a mother, and its first-order reading:

Given the ABox assertions $\mathrm{Woman}\left(\mathrm{ann}\right)$, $\mathrm{hasChild}(\mathrm{ann},\mathrm{bill})$ and $\mathrm{Person}\left(\mathrm{bill}\right)$, a reasoner concludes $\mathrm{Mother}\left(\mathrm{ann}\right)$ (instance checking) and that $\mathrm{Mother}$ is subsumed by $\mathrm{Woman}$ (classification). The standard reasoning tasks are concept satisfiability, subsumption, knowledge-base consistency and instance checking.

Complexity. ALC was introduced by Schmidt-Schauß and Smolka in 1991, who showed that deciding satisfiability and subsumption of ALC concept descriptions is PSPACE-complete [14]. At the other end, the small logic EL (conjunction and existential restriction) keeps subsumption polynomial even with general TBox axioms, and Baader, Brandt and Lutz (2005) mapped how far it can be extended without losing that property [15]. Choosing a description logic is choosing a point on this curve.

Limits. DLs reason under the open-world assumption: if the knowledge base does not say that Bill has a child, a DL reasoner does not conclude that he has none. That is correct for incomplete data and surprising to anyone used to databases.

Ontologies

What it is. In AI an ontology is, in Thomas Gruber’s 1993 definition, “an explicit specification of a conceptualization”: a shared, formal vocabulary of classes, relations and constraints for a domain, so that different systems mean the same thing by the same term [16].

How it works. An ontology fixes class hierarchies (Aspirin is a Drug), relation signatures (treats links a drug to a disease), and constraints (every Prescription has exactly one patient). Written in a logic such as OWL, it can be checked mechanically for contradictions and used to classify new data.

Where it is used today. Biomedicine is the largest user: clinical terminologies such as SNOMED CT and the Gene Ontology are ontologies. Limits. Agreement is expensive, domains drift, and a large ontology is software that needs versioning and maintenance like any other.

RDF

What it is. The Resource Description Framework is the W3C’s data model for exchanging graph data. The first RDF Model and Syntax Specification became a W3C Recommendation on 22 February 1999 [17]; RDF 1.1 followed on 25 February 2014 [18]. It was a foundation of the Semantic Web programme described by Berners-Lee, Hendler and Lassila in 2001 [19].

How it works. An RDF graph is a set of triples, subject–predicate–object, in which subjects and predicates are IRIs (global identifiers) and objects are IRIs, literals or blank nodes. Two triples in the Turtle syntax:

ex:aspirin rdf:type ex:Drug .
ex:aspirin ex:inhibits ex:COX1 .

Because identifiers are global, graphs from different sources merge by set union. SPARQL, the query language for RDF, became a W3C Recommendation on 15 January 2008 [20]. RDF Schema adds a light vocabulary for classes and properties. Limits. RDF on its own says what is asserted, not what follows; inference needs RDFS or OWL on top, and data quality is only as good as each publisher.

OWL

What it is. OWL, the Web Ontology Language, is the W3C standard for ontologies, with formal semantics taken from description logics. OWL became a W3C Recommendation on 10 February 2004, and OWL 2 on 27 October 2009 [21]. The first OWL DL corresponded to the description logic SHOIN; OWL 2 DL is based on SROIQ, introduced by Horrocks, Kutz and Sattler in 2006 [22].

How it works. The definition of Mother above is one OWL class axiom. OWL 2 also defines three profiles, each giving up expressiveness for speed: OWL 2 EL, where reasoning is polynomial in the size of the ontology and which is sufficient to express the very large biomedical ontology SNOMED CT; OWL 2 QL, where query answering is in LOGSPACE in the size of the data and can be delegated to a relational database; and OWL 2 RL, designed for rule engines [23].

Limits. Full OWL 2 DL reasoning is decidable but of very high worst-case complexity; OWL makes neither the closed-world nor the unique-name assumption, so two different names may denote the same individual unless the ontology says otherwise.

4. Large knowledge bases

Cyc

What it is. Cyc is the longest-running attempt to write down common sense by hand. Douglas Lenat began it in 1984 at the Microelectronics and Computer Technology Corporation (MCC) in Austin; from 1995 it continued at Cycorp, which Lenat founded and led until his death on 31 August 2023 [24]. See the history of symbolic AI for its place in the 1980s.

How it works. Knowledge is written in CycL, a logical language based on predicate calculus that was extended to higher-order constructs. Assertions are grouped into microtheories, contexts that must each be free of contradictions but may disagree with one another, so that, for example, a fictional context and a real-world context can hold incompatible facts without making the whole knowledge base inconsistent. According to figures reported for 2017, the ontology held about 1.5 million terms and about 24.5 million assertions. An open subset, OpenCyc, was released from 2002 and withdrawn in 2017.

Limits. Cyc is the clearest measurement of the knowledge-acquisition bottleneck: decades of expert effort produced a very large knowledge base and still did not cover everyday common sense. Its reasoning is, however, explainable in a way statistical models are not.

WordNet

What it is. WordNet is a lexical database of English begun in 1985 by the psychologist George A. Miller and his team at Princeton [25]. It groups words into synsets, sets of synonyms that express one concept, and links synsets by relations such as hypernymy (dog is a kind of canine) and meronymy (wheel is part of car).

Today and limits. WordNet became a standard resource in natural language processing and was reproduced for many other languages. It is a lexicon, not a theory of the world: it records that words are related, not the facts that follow.

Knowledge graphs

What it is. A knowledge graph is a large graph of entities and typed relations, used as a store of facts. The term became widespread after Google introduced its Knowledge Graph on 16 May 2012 under the slogan “things, not strings” [26]. Earlier public graphs included DBpedia and Freebase, both founded in 2007; Wikidata launched on 29 October 2012, and much of Freebase moved into it after Freebase became read-only in 2015 [27].

How it works. Facts are edges, usually RDF triples or property-graph edges, sometimes with qualifiers and sources. Reasoning ranges from graph queries and traversal to OWL or rule inference over a schema. A typed traversal returns the path that connects two entities, and that path is the justification; our paper Traversing Data in Symbolic Systems makes this precise.

Today and limits. Knowledge graphs back search engines, product catalogues and biomedical databases, and they are now a common way to ground language models (see neuro-symbolic AI). Most carry light schemas and little formal reasoning; their quality depends on extraction and curation, and embedding a graph into vectors trades its exactness for similarity.

5. The techniques compared

6. Timeline

7. What knowledge representation cannot do

• Expressiveness costs tractability. This is not an engineering accident but a theorem-level fact, from Brachman and Levesque’s 1984 result to the complexity map of description logics. Every KR language is a chosen compromise.
• The knowledge-acquisition bottleneck. Somebody has to write the axioms. Cyc shows how far hand-authoring scales and where it stops; see expert systems for the same problem in rule bases.
• Symbol grounding. A representation relates symbols to other symbols. Nothing inside it connects ex:aspirin to aspirin; that link comes from people or from perception.
• Defaults and exceptions. Classical logics cannot withdraw a conclusion when new facts arrive; frames and scripts need to. That is the subject of nonmonotonic reasoning.

8. How this connects to fail-safe models

A fail-safe model is an AI model built so that failure drives it to a safe, controlled state: it abstains when evidence is missing, and learning can narrow what it does but never widen what it is authorised to do. Whether that is possible depends first on a knowledge representation question: what counts as a fact, and what the system does when a fact is absent. A representation in which every fact is typed and carries its source lets a system answer “unknown” instead of guessing, and lets a refusal point at the exact facts behind it.

Peel, by Perslis Research, is to our knowledge the first fail-safe model. Its knowledge is typed, sourced cards; learning is readable counts; there is no neural network in the loop that decides. A language model may propose; only the floor admits a fact. Peel is a research prototype, not a certified safety system. For how Perslis uses symbolic AI more broadly, see Symbolic AI at Perslis.

9. Questions

What is knowledge representation in AI?

Knowledge representation is the part of AI that decides how a system’s knowledge is written down as symbols, what those symbols mean, and which conclusions can be drawn from them. Its main techniques are semantic networks, frames, scripts, description logics, ontologies, RDF, OWL and knowledge graphs.

What are the main types of knowledge representation?

The main families are logical representations such as first-order logic and description logics; network representations such as semantic networks, conceptual graphs and knowledge graphs; structured-object representations such as frames and scripts; and rule-based representations such as production rules. Most real systems combine several.

What is the difference between a semantic network and a knowledge graph?

A semantic network is the older idea of drawing concepts as nodes and relations as labelled links, introduced for AI by Quillian in 1968. A knowledge graph applies the same idea at very large scale to facts about entities, usually with global identifiers, a schema and sources. Knowledge graphs are semantic networks at web scale, typically with lighter reasoning.

What is a frame in AI?

A frame, proposed by Marvin Minsky in 1974, is a data structure for a stereotyped situation or object. It has slots with default values and constraints, frames inherit from more general frames, and defaults hold until evidence overrides them.

What is the difference between an ontology and OWL?

An ontology is a formal, shared vocabulary for a domain: its classes, relations and constraints. OWL, the Web Ontology Language, is a W3C standard language for writing ontologies, with formal semantics based on description logics, so that a reasoner can check an OWL ontology for consistency and classify its classes.

Why are description logics decidable when first-order logic is not?

Description logics restrict what can be said: they talk about classes and binary relations with a fixed set of constructors, without arbitrary quantification over many variables. Those restrictions keep reasoning problems such as subsumption decidable, at costs that range from polynomial time for EL to much higher for expressive logics such as SROIQ.

Is Cyc still active?

Cyc began in 1984 at MCC and continued from 1995 at Cycorp, the company founded by Douglas Lenat, who died on 31 August 2023. Its open subset, OpenCyc, was withdrawn in 2017. Cyc remains the largest example of hand-encoded common-sense knowledge and the clearest measure of the knowledge-acquisition bottleneck.

How does knowledge representation relate to fail-safe AI?

A fail-safe model must know which facts it may rely on and must abstain when a fact is missing. That depends on a representation in which facts are explicit, typed and sourced, so that absence can be detected and every refusal can cite the facts behind it.

10. References

1. R. J. Brachman, H. J. Levesque. Knowledge Representation and Reasoning. Morgan Kaufmann, 2004.
2. M. R. Quillian. Semantic Memory. In M. Minsky (ed.), Semantic Information Processing. MIT Press, 1968.
3. A. M. Collins, M. R. Quillian. Retrieval time from semantic memory. Journal of Verbal Learning and Verbal Behavior 8(2):240–247, 1969. doi:10.1016/S0022-5371(69)80069-1.
4. W. A. Woods. What’s in a Link: Foundations for Semantic Networks. In D. G. Bobrow, A. Collins (eds.), Representation and Understanding: Studies in Cognitive Science. Academic Press, 1975.
5. R. J. Brachman. What IS-A Is and Isn’t: An Analysis of Taxonomic Links in Semantic Networks. IEEE Computer 16(10):30–36, 1983. doi:10.1109/MC.1983.1654194.
6. M. Minsky. A Framework for Representing Knowledge. MIT AI Laboratory Memo 306, 1974.
7. R. C. Schank, R. P. Abelson. Scripts, Plans, Goals and Understanding: An Inquiry into Human Knowledge Structures. Lawrence Erlbaum Associates, 1977.
8. R. C. Schank. Conceptual dependency: A theory of natural language understanding. Cognitive Psychology 3(4):552–631, 1972. doi:10.1016/0010-0285(72)90022-9.
9. J. F. Sowa. Conceptual Graphs for a Data Base Interface. IBM Journal of Research and Development 20(4):336–357, 1976.
10. J. F. Sowa. Conceptual Structures: Information Processing in Mind and Machine. Addison-Wesley, 1984.
11. R. J. Brachman, J. G. Schmolze. An Overview of the KL-ONE Knowledge Representation System. Cognitive Science 9(2):171–216, 1985. doi:10.1207/s15516709cog0902_1.
12. R. J. Brachman, H. J. Levesque. The Tractability of Subsumption in Frame-Based Description Languages. Proceedings of AAAI-84, 34–37, 1984.
13. F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider (eds.). The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, 2003.
14. M. Schmidt-Schauß, G. Smolka. Attributive concept descriptions with complements. Artificial Intelligence 48(1):1–26, 1991. doi:10.1016/0004-3702(91)90078-X.
15. F. Baader, S. Brandt, C. Lutz. Pushing the EL Envelope. Proceedings of IJCAI 2005, 364–369, 2005.
16. T. R. Gruber. A translation approach to portable ontology specifications. Knowledge Acquisition 5(2):199–220, 1993. doi:10.1006/knac.1993.1008.
17. O. Lassila, R. R. Swick (eds.). Resource Description Framework (RDF) Model and Syntax Specification. W3C Recommendation, 22 February 1999.
18. R. Cyganiak, D. Wood, M. Lanthaler (eds.). RDF 1.1 Concepts and Abstract Syntax. W3C Recommendation, 25 February 2014.
19. T. Berners-Lee, J. Hendler, O. Lassila. The Semantic Web. Scientific American 284(5):34–43, May 2001.
20. E. Prud’hommeaux, A. Seaborne (eds.). SPARQL Query Language for RDF. W3C Recommendation, 15 January 2008.
21. W3C OWL Working Group. OWL 2 Web Ontology Language Document Overview. W3C Recommendation, 27 October 2009 (second edition 2012). The first OWL became a W3C Recommendation on 10 February 2004.
22. I. Horrocks, O. Kutz, U. Sattler. The Even More Irresistible SROIQ. Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR 2006), 2006.
23. W3C. OWL 2 Web Ontology Language Profiles (Second Edition). W3C Recommendation, 11 December 2012.
24. D. B. Lenat. CYC: A Large-Scale Investment in Knowledge Infrastructure. Communications of the ACM 38(11), 1995.
25. G. A. Miller. WordNet: A Lexical Database for English. Communications of the ACM 38(11), 1995. doi:10.1145/219717.219748.
26. A. Singhal. Introducing the Knowledge Graph: things, not strings. The Official Google Blog, 16 May 2012.
27. A. Hogan et al. Knowledge Graphs. ACM Computing Surveys 54(4), Article 71, 2021. doi:10.1145/3447772. arXiv:2003.02320.