A conceptual graph (CG) is a formalism for
knowledge representation
Knowledge representation and reasoning (KRR, KR&R, KR²) is the field of artificial intelligence (AI) dedicated to representing information about the world in a form that a computer system can use to solve complex tasks such as diagnosing a medic ...
. In the first published paper on CGs,
John F. Sowa
John Florian Sowa (born 1940) is an American computer scientist, an expert in artificial intelligence and computer design, and the inventor of conceptual graphs.
Biography
Sowa received a BS in mathematics from Massachusetts Institute of Techno ...
used them to represent the
conceptual schema
A conceptual schema is a high-level description of informational needs underlying the design of a database. It typically includes only the main concepts and the main relationships among them. Typically this is a first-cut model, with insufficient ...
s used in
database system
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases span ...
s. The first book on CGs applied them to a wide range of topics in
artificial intelligence
Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
,
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, and
cognitive science.
Research branches
Since 1984, the model has been developed along three main directions: a graphical interface for first-order logic, a diagrammatic calculus of logics, and a graph-based
knowledge representation and reasoning
Knowledge representation and reasoning (KRR, KR&R, KR²) is the field of artificial intelligence (AI) dedicated to representing information about the world in a form that a computer system can use to solve complex tasks such as Computer-aided diag ...
model.
Graphical interface for first-order logic
![Cat-on-mat](https://upload.wikimedia.org/wikipedia/commons/4/4b/Cat-on-mat.svg)
In this approach, a formula in
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
(predicate calculus) is represented by a labeled graph.
A linear notation, called the Conceptual Graph Interchange Format (CGIF), has been standardized in the
ISO standard
The International Organization for Standardization (ISO ) is an international standard development organization composed of representatives from the national standards organizations of member countries. Membership requirements are given in Ar ...
for
common logic
Common Logic (CL) is a framework for a family of logic languages, based on first-order logic, intended to facilitate the exchange and transmission of knowledge in computer-based systems.
The CL definition permits and encourages the development o ...
.
The diagram above is an example of the ''display form'' for a conceptual graph. Each box is called a ''concept node'', and each oval is called a ''relation node''. In CGIF, this CG would be represented by the following statement:
In CGIF, brackets enclose the information inside the concept nodes, and parentheses enclose the information inside the relation nodes. The letters x and y, which are called ''coreference labels'', show how the concept and relation nodes are connected. In CLIF, those letters are mapped to variables, as in the following statement:
As this example shows, the asterisks on the coreference labels and in CGIF map to existentially quantified variables in CLIF, and the question marks on and map to bound variables in CLIF. A universal quantifier, represented in CGIF, would be represented in CLIF.
Reasoning can be done by translating graphs into logical formulas, then applying a logical
inference engine
In the field of artificial intelligence, an inference engine is a component of the system that applies logical rules to the knowledge base to deduce new information. The first inference engines were components of expert systems. The typical expert ...
.
Diagrammatic calculus of logics
Another research branch continues the work on
existential graph
An existential graph is a type of diagrammatic or visual notation for logical expressions, proposed by Charles Sanders Peirce, who wrote on logical graph, graphical logic as early as 1882,Peirce, C. S., " n Junctures and Fractures in Logic (ed ...
s of
Charles Sanders Peirce
Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism".
Educated as a chemist and employed as a scientist for t ...
, which were one of the origins of conceptual graphs as proposed by Sowa. In this approach, developed in particular by Dau , conceptual graphs are conceptual
diagram
A diagram is a symbolic representation of information using visualization techniques. Diagrams have been used since prehistoric times on walls of caves, but became more prevalent during the Enlightenment. Sometimes, the technique uses a three- ...
s rather than graphs in the sense of
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, and reasoning operations are performed by operations on these diagrams.
Graph-based knowledge representation and reasoning model
Key features of GBKR, the graph-based knowledge representation and reasoning model developed by Chein and Mugnier and the Montpellier group , can be summarized as follows:
* All kinds of knowledge (ontology, rules, constraints and facts) are labeled graphs, which provide an intuitive and easily understandable means to represent knowledge.
* Reasoning mechanisms are based on graph notions, basically the classical notion of
graph homomorphism
In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent verti ...
; this allows, in particular, to link basic reasoning problems to other fundamental problems in computer science (e.g., problems concerning
conjunctive queries in
relational database
A relational database is a (most commonly digital) database based on the relational model of data, as proposed by E. F. Codd in 1970. A system used to maintain relational databases is a relational database management system (RDBMS). Many relatio ...
s, or
constraint satisfaction problems
Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constr ...
).
* The formalism is logically founded, i.e., it has a semantics in
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
and the inference mechanisms are sound and complete with respect to deduction in first-order logic.
* From a computational viewpoint, the graph homomorphism notion was recognized in the 1990s as a central notion, and complexity results and efficient algorithms have been obtained in several domains.
COGITANT and COGUI are tools that implement the GBKR model. COGITANT is a library of
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
classes that implement most of the GBKR notions and reasoning mechanisms. COGUI is a graphical user interface dedicated to the construction of a GBKR knowledge base (it integrates COGITANT and, among numerous functionalities, it contains a translator from GBKR to
RDF/S and conversely).
See also
*
Alphabet of human thought The alphabet of human thought ( la, alphabetum cogitationum humanarum) is a concept originally proposed by Gottfried Wilhelm Leibniz that provides a universal way to represent and analyze ideas and relationships by breaking down their component piec ...
*
Chunking (psychology)
In cognitive psychology, chunking is a process by which individual pieces of an information set are bound together into a meaningful whole. The chunks, by which the information is grouped, are meant to improve short-term retention of the material, ...
*
Resource Description Framework The Resource Description Framework (RDF) is a World Wide Web Consortium (W3C) standard originally designed as a data model for metadata. It has come to be used as a general method for description and exchange of graph data. RDF provides a variety of ...
(RDF)
*
SPARQL
SPARQL (pronounced "sparkle" , a recursive acronym for SPARQL Protocol and RDF Query Language) is an RDF query language—that is, a semantic query language for databases—able to retrieve and manipulate data stored in Resource Description F ...
(Graph Query Language)
*
Semantic network
A semantic network, or frame network is a knowledge base that represents semantic relations between concepts in a network. This is often used as a form of knowledge representation. It is a directed or undirected graph consisting of vertices, ...
References
*
*
*
*
* {{cite journal, title=Conceptual graphs for the analysis and generation of sentences
, first1=Paola , last1=Velardi , first2=Maria Teresa , last2=Pazienza , first3=Mario , last3=De' Giovanetti , journal=IBM Journal of Research and Development , volume=32 , number=2 , date=March 1988 , pages=251–267 , publisher=IBM Corp. Riverton, NJ, USA , doi=10.1147/rd.322.0251
External links
Conceptual Structures Home Page (Old site
Conceptual Graphs Home Page
Annual international conferences (ICCS)at
DBLP
DBLP is a computer science bibliography website. Starting in 1993 at Universität Trier in Germany, it grew from a small collection of HTML files and became an organization hosting a database and logic programming bibliography site. Since Nove ...
Conceptual Graphs on John F. Sowa's Website
Knowledge representation
Diagrams
Application-specific graphs