Foundations of Knowledge Representation

Knowledge representation is the formal encoding of information about the world, enabling machines to store, reason, and infer beyond raw data. At the heart of modern artificial intelligence and data-intensive systems lies the knowledge graph (KG), a structured semantic network that interconnects entities via typed relationships, embedding human knowledge in a machine-readable form. This chapter establishes the formal and philosophical bedrock upon which all subsequent discussions are built. We begin by rigorously defining what constitutes a knowledge graph, distinguishing it from generic graph structures and traditional databases. We then review the essential theoretical pillars: graph theory, which provides the structural skeleton, and mathematical logic, which supplies the semantic muscle. Tracing the historical evolution from early semantic networks through the Semantic Web stack (RDF, OWL) to modern property graphs and industry-scale implementations reveals the converging forces that shaped today’s KG paradigms. A precise analysis of core components—entities, relations, attributes, and contexts—follows, alongside a critical examination of key quality dimensions (accuracy, coverage, consistency, freshness) that separate research prototypes from production systems. The chapter concludes with a taxonomy of KG applications and a comparative case study of Google's Knowledge Graph and Wikidata, illustrating how foundational choices manifest in real-world systems. This foundation is not merely academic; it dictates the expressivity, scalability, and utility of every KG built thereafter.

1.1 Defining the Knowledge Graph: Beyond Nodes and Edges

A knowledge graph is often mistakenly reduced to "a labeled directed multigraph." While such a graph is a necessary substrate, it is insufficient. The defining characteristic of a KG is its semantic richness and formal semantics. A generic graph $G = (V, E)$ consists of vertices $V$ and edges $E \subseteq V \times V$. A KG augments this with:

1. Explicit Typing: Both nodes (entities) and edges (relations) belong to classes or types from a predefined ontology or schema. An entity is not just a string "Paris"; it is an instance of type `City` (or `Place`, `Capital`). A relation is not just an arrow; it is an instance of a property like `capitalOf` or `locatedIn`. 2. Attribute-Value Pairs: Entities can have an arbitrary set of attributes (also called properties or features) with values of specific data types (strings, numbers, dates, geocoordinates). For example, the entity `Paris` might have `population: 2161000` (integer) and `coordinates: 48.8566° N, 2.3522° E` (geospatial literal). 3. Contextualization: Facts (entity-relation-entity triples or entity-attribute-value pairs) can be qualified with context—provenance (who stated it), temporal validity (when it was true), confidence score, or source. This moves from a simple triple store to a *quad store* or *n-ary relation* model. 4. Logical Inference: The schema (the set of types and their interrelationships) is designed to support logical reasoning. If the schema defines that `CapitalOf` is a sub-relation of `LocatedIn` and `Paris` `capitalOf` `France`, a reasoner can infer that `Paris` `locatedIn` `France` without this fact being explicitly stored.

This distinction can be formalized. Let a Knowledge Graph be a tuple $KG = (E, R, A, T, I)$, where:

• $E$ is a set of **entities** (unique identifiers for real-world or abstract objects).
• $R$ is a set of **relations** (binary predicates connecting two entities).
• $A$ is a set of **attributes** (properties directly associated with a single entity).
• $T$ is a **schema** or **ontology**, a formal specification of types (classes) $C$ and their hierarchies ($C_i \sqsubseteq C_j$), relation domains and ranges ($dom(r) \subseteq C$, $ran(r) \subseteq C$), and constraints (cardinality, disjointness).
• $I$ is a set of **interpretations** or **contexts** that qualify facts.

Contrast this with a property graph model (used by Neo4j, Amazon Neptune), which emphasizes flexible schema-on-read, where properties are key-value maps on nodes and relationships. While property graphs are powerful for pattern matching and traversal, their semantics are often implicit and application-specific. A RDF-based KG (used by Wikidata, DBpedia) uses the rigid triple subject-predicate-object model, where everything—including attribute values—is a resource or a literal, and meaning is derived from shared ontologies and inference engines. The line blurs in practice (e.g., Neo4j supports full-text search and constraints), but the philosophical commitment to formal semantics remains the KG's hallmark.

> 📖 Sidebar for Digital Edition: The Schema Spectrum > *KGs exist on a spectrum from "schema-optional" to "schema-mandatory." Google's Knowledge Graph uses a tightly controlled internal schema for precision. Wikidata uses a flexible, community-driven schema (via properties and constraints) that evolves. Understanding where your use case falls on this spectrum is the first architectural decision.*

1.2 Theoretical Pillars: Graph Theory and Logic

1.2.1 Graph Theory: The Structural Backbone

Knowledge graphs are fundamentally graphs, and graph theory provides the language for their structure and algorithmic analysis.

• **Directed vs. Undirected:** KGs are inherently **directed multigraphs** (allowing multiple edges between nodes). The direction of a relation is semantically significant (`parentOf` ≠ `childOf`). However, some relationships are symmetric (`siblingOf`), which can be modeled either by two directed edges or an undirected edge abstraction.
• **Hypergraphs:** Traditional graphs have binary edges. Many real-world relationships are n-ary: `Employment(Person, Company, Role, StartDate, EndDate)`. This can be modeled in a standard KG by creating a "reification" node for the employment event, connecting it to the person, company, role, etc. This transforms an n-ary relation into a set of binary relations centered on a new node. Formally, a **hypergraph** $H = (V, E)$ where $E \subseteq \mathcal{P}(V) \setminus \{\emptyset\}$ (edges are subsets of vertices) can be a more natural model, but most KG systems implement n-ary relations via reification due to their binary-triple foundation.
• **Key Graph Properties:**
• **Connectedness:** Is the graph weakly connected (ignoring direction) or fragmented? Enterprise KGs are often highly connected, integrating data from multiple silos.
• **Degree Distribution:** The number of edges per node (degree) often follows a **power-law** (scale-free) distribution: a few hubs (e.g., `United States`, `Barack Obama`) have thousands of connections, while most entities have few. This impacts storage (compression for hubs) and query optimization (starting from hubs).
• **Diameter:** The longest shortest path between any two nodes. In a well-connected KG, the diameter is small ("small-world" phenomenon), enabling efficient traversal.
• **Clustering Coefficient:** Measures the degree to which nodes cluster together. High clustering indicates strong communities (e.g., all actors in a film, all cities in a country).

```mermaid graph TD A[Knowledge Graph] --> B[Graph Theory Foundation] A --> C[Logic Foundation] B --> B1[Directed Multigraph] B --> B2[Hypergraph / Reification] B --> B3[Scale-Free Structure] B --> B4[Small-World Property] C --> C1[First-Order Logic FOL] C --> C2[Description Logic DL] C --> C3[Rule-Based Logic] C1 --> C2 C2 --> C4[OWL 2 DL Profiles] ```

1.2.2 Mathematical Logic: The Semantic Foundation

Logic provides the formal semantics that make a KG more than a database. It defines what statements *mean* and what *follows* from them.

• **First-Order Logic (FOL):** The standard logic for mathematics. It allows quantification over individuals ($\exists x, \forall x$), predicates (relation