Querying Circumscribed Description Logic Knowledge Bases

Carsten Lutz, Quentin Manière, Robin Nolte
6/7/2023
cs.AIcs.CCcs.LO

No confident code implementation found for this paper.

Abstract

Circumscription is one of the main approaches for defining non-monotonic description logics (DLs). While the decidability and complexity of traditional reasoning tasks such as satisfiability of circumscribed DL knowledge bases (KBs) is well understood, for evaluating conjunctive queries (CQs) and unions thereof (UCQs), not even decidability had been established. In this paper, we prove decidability of (U)CQ evaluation on circumscribed DL KBs and obtain a rather complete picture of both the combined complexity and the data complexity, for DLs ranging from ALCHIO via EL to various versions of DL-Lite. We also study the much simpler atomic queries (AQs).

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Description Logics with Abstraction and Refinement

83% match2023

Exploring Non-Regular Extensions of Propositional Dynamic Logic with Description-Logics Features

78% match2023

Decidability of Querying First-Order Theories via Countermodels of Finite Width

78% match2023

Queries With Exact Truth Values in Paraconsistent Description Logics

77% match2024

Data Complexity in Expressive Description Logics With Path Expressions

77% match2024

The Equivalence Theorem: First-Class Relationships for Structurally Complete Database Systems

75% match2026

Cite this paper

@article{lutz2023querying,
  title  = {Querying Circumscribed Description Logic Knowledge Bases},
  author = {Carsten Lutz and Quentin Manière and Robin Nolte},
  year   = {2023},
  eprint = {2306.04546},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2306.04546v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2306.04546.svg)](https://codeofpaper.com/paper/2306.04546)

Discussion