Managing Change in Graph-Structured Data Using Description Logics

DOI10.1145/3143803MaRDI QIDQ4608716zbMATH OpenOpenAlexWikidataFDO

Authors Shqiponja Ahmetaj, Diego Calvanese, Magdalena Ortiz, Mantas Šimkus

Publication date 22 March 2018

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.4274

zbMATH Keywords

planningstatic analysisintegrity constraintsgraph-structured data

Mathematics Subject Classification ID

Knowledge representation (68T30) Database theory (68P15) Logic in artificial intelligence (68T27)

Abstract: In this paper, 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 ensuring the satisfaction of a given set of integrity constraints after a given sequence of updates, 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. We consider an action language in which actions are finite sequences of conditional insertions and deletions of nodes and labels, and use Description Logics for describing integrity constraints and (partial) states of the data. We then formalize the above data management problems as a static verification problem and several planning problems. We provide algorithms and tight complexity bounds for the formalized problems, both for an expressive DL and for a variant of DL-Lite.

Recommendations

• scientific article; zbMATH DE number 1182733
• Representing ontologies using description logics, description graphs, and rules
• Datalog revisited for reasoning in linked data
• Datalog and Its Extensions for Semantic Web Databases

Cited in

(6)

• Ensuring correctness of model transformations while remaining decidable
• Verification of evolving graph-structured data under expressive path constraints
• Actions over core-closed knowledge bases
• Management of Change in Declarative Languages
• Certified Graph View Maintenance with Regular Datalog
• Reasoning formally about database queries and updates

This page was built for publication: Managing Change in Graph-Structured Data Using Description Logics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608716)