Dependently Typed Knowledge Graphs

Zhangsheng Lai, Aik Beng Ng, Liang Ze Wong, Simon See, Shaowei LinarXiv 2020 · arXiv

Introduction

Traditional Knowledge Graphs (KGs) are built upon the "Semantic Web Stack," a layered architecture of distinct languages and formalisms. While powerful, this stack is fragmented: RDF handles data interchange, RDFS defines taxonomies, OWL provides complex logic, and SPARQL serves as the query language. This paper proposes a radical simplification: replacing this heterogeneous stack with a single, unified logical framework based on Dependent Type Theory (DTT). By implementing a Dependently Typed Knowledge Graph (DTKG) within the Coq proof assistant, the authors demonstrate how data, schema, and reasoning can be integrated into a single type-safe environment.

The Fragmented Semantic Web Stack

The current state of Knowledge Graph technology faces three primary challenges stemming from its architectural fragmentation. First, provenance and trust are difficult to maintain; it is often unclear whether a fact is a direct assertion or an inference. Second, standard RDF lacks type safety, allowing logically inconsistent triples (e.g., a city as a "father") to exist without system-level errors. Finally, reasoning gaps persist because moving between simple retrieval and complex deduction requires switching between different formalisms.

The traditional Semantic Web Stack, illustrating the fragmentation between data, logic, and querying layers.

Methodology: DTKG in Coq

The proposed DTKG leverages the Curry-Howard correspondence, which treats mathematical proofs as computer programs and logical propositions as types. In this framework, a KG query is represented as a type, and the answer to that query is a term (or "witness") belonging to that type.

Key technical components include:

  • Queries-as-Types: Complex queries are modeled as record types. For instance, a query for "Sasha's father" is a record containing a field for a "Person" and a "Proof" field justifying the relationship.
  • Enumerated and Dependent Types: Entities are defined as terms of enumerated types (e.g., Person), while relationships are dependent types that enforce valid connections at the type level.
  • Ltac Automation: A custom tactic, dqt, was developed to automate the search for witnesses, effectively "proving" the answer to a query.
  • Coercion and Compositionality: Coq’s coercion features allow query results to be treated as base entities, enabling the output of one query to serve as the input for another seamlessly.

Proof-of-Concept: The Obama Family Tree

To validate the DTKG approach, the authors utilized a small, hand-coded dataset representing the Obama family relationships. This dataset serves to demonstrate both direct fact retrieval and composite inference.

A graphical representation of the Obama family tree dataset used for direct and composite query testing.

By using this dataset, the authors showed that the system could infer Malia’s father by composing "MotherOf" and "HusbandOf" relationships, automatically generating the logical witness for the inference.

Key Insights and Results

The DTKG approach offers several advantages over traditional systems:

  1. Built-in Explainability: Because every answer is accompanied by a symbolic proof (witness), the system provides inherent provenance.
  2. Proof Relevance: DTT allows the system to distinguish between different ways of proving the same fact (e.g., DNA test vs. birth certificate), which is crucial for trust.
  3. Unified Universe: The entire Semantic Web Stack—RDF, RDFS, and SPARQL—is collapsed into a single Coq environment.
  4. Type-Safe Knowledge: Nonsensical data is caught during type-checking, preventing data corruption at the source.

Limitations and Future Directions

While promising, the DTKG framework currently faces scalability issues. Coq is optimized for theorem proving rather than high-speed database operations, making it challenging to scale to billions of triples. Additionally, the complexity of writing queries as record types presents a steep learning curve for non-experts. Future work will explore mapping more complex ontologies (OWL) and rule formats (RIF) into this framework and improving performance for larger datasets.

Summary updated

BibTeX
@misc{lai2020dependently,
  author = {Zhangsheng Lai and Aik Beng Ng and Liang Ze Wong and Simon See and Shaowei Lin},
  title = {{Dependently Typed Knowledge Graphs}},
  year = {2020},
  eprint = {2003.03785},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2003.03785},
}
Figure