# Satisfiability and Query Answering in Description Logics with Global and Local Cardinality Constraints

arXiv: https://arxiv.org/abs/2002.06072 · HTML: https://mlsanity.com/paper/2002.06072/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2020.

## Built on by (most cited first, 5 of 5)

- [A Logic for Reasoning About Aggregate-Combine Graph Neural Networks](https://mlsanity.com/paper/2405.00205/) (2024)
- [Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases](https://mlsanity.com/paper/2407.20754/) (2024)
- [The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard](https://mlsanity.com/paper/2106.15150/) (2021)
- [Lutz's Spoiler Technique Revisited: A Unified Approach to Worst-Case Optimal Entailment of Unions of Conjunctive Queries in Locally-Forward Description Logics](https://mlsanity.com/paper/2108.05680/) (2021)
- [Spectra of Cardinality Queries over Description Logic Knowledge Bases](https://mlsanity.com/paper/2412.12929/) (2024)

## Abstract (arXiv)

We introduce and investigate the expressive description logic (DL) ALCSCC++, in which the global and local cardinality constraints introduced in previous papers can be mixed. On the one hand, we prove that this does not increase the complexity of satisfiability checking and other standard inference problems. On the other hand, the satisfiability problem becomes undecidable if inverse roles are added to the languages. In addition, even without inverse roles, conjunctive query entailment in this DL turns out to be undecidable. We prove that decidability of querying can be regained if global and local constraints are not mixed and the global constraints are appropriately restricted. The latter result is based on a locally-acyclic model construction, and it reduces query entailment to ABox consistency in the restricted setting, i.e., to ABox consistency w.r.t. restricted cardinality constraints in ALCSCC, for which we can show an ExpTime upper bound.