Adding Weight to DL-Lite

Proc. of the 22nd Int. Workshop on Description Logics (DL 2009). Volume 477 of CEUR Workshop Proceedings, https://ceur-ws.org/. 2009.

In this paper we extend the logic DL-LiteNbool and its fragments with (i) role inclusions, (ii) qualified number restrictions and (iii) role disjointness, symmetry, asymmetry, reflexivity and irreflexivity constraints. We show that if the interaction of (qualified) number restrictions with role inclusions is restricted in a way similar to DL-LiteA then the resulting logics enjoy the same computational properties as the respective fragments of DL-LiteNbool: for combined complexity, satisfiability in the full language is NP-complete and it is tractable in the Horn fragment; for data complexity, answering positive existential queries over the Horn fragment is in AC0 (and thus, FO rewritable). Our main tool for dealing with DL-Lite logics is embedding into the one-variable fragment of first-order logic without equality and function symbols, which seems to be a natural logic-based characterization of the DL-Lite logics. This embedding provides us with upper combined complexity bounds for all fragments. We also use it to obtains explicit FO rewritings of positive existential queries for the Horn fragment.

@inproceedings{DL-2009-qr,
   title = "Adding Weight to DL-Lite",
   year = "2009",
   author = "Alessandro Artale and Diego Calvanese and Roman Kontchakov
and Michael Zakharyaschev",
   booktitle = "Proc. of the 22nd Int. Workshop on Description Logics
(DL 2009)",
   volume = "477",
   publisher = "CEUR-WS.org",
   series = "CEUR Workshop Proceedings, https://ceur-ws.org/",
}