Publications in Scientific Journals:
S. Ahmetaj, M. Ortiz de la Fuente, D. Calvanese, M. Simkus:
"Managing Change in Graph-Structured Data Using Description Logics";
ACM Transactions on Computational Logic,
In this article, we consider the setting of graph-structured data that evolves as a result of operations carried out by users or applications. We study different reasoning problems, which range from deciding whether a given sequence of actions preserves the satisfaction of a given set of integrity constraints, for every possible initial data instance, to deciding the (non)existence of a sequence of actions that would take the data to an (un)desirable state, starting either from a specific data instance or from an incomplete description of it. For describing states of the data instances and expressing integrity constraints on them, we use description logics (DLs) closely related to the two-variable fragment of first-order logic with counting quantifiers. The updates are defined as actions in a simple yet flexible language, as finite sequences of conditional insertions and deletions, which allow one to use complex DL formulas to select the (pairs of) nodes for which (node or arc) labels are added or deleted. We formalize the preceding data management problems as a static verification problem and several planning problems and show that, due to the adequate choice of formalisms for describing actions and states of the data, most of these data management problems can be effectively reduced to the (un)satisfiability of suitable formulas in decidable logical formalisms. Leveraging this, we provide algorithms and tight complexity bounds for the formalized problems, both for expressive DLs and for a variant of the popular DL-Lite, advocated for data management in recent years.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Created from the Publication Database of the Vienna University of Technology.