A complete logic for non-deterministic database transformations

Q. Wang, F. Ferrarotti, K. Schewe, L. Tec. A complete logic for non-deterministic database transformations. cs.LO - Logic in Computer Science, arXiv:1602.07486 [cs.LO], 2, 2016.

  • Qing Wang
  • Flavio Ferrarotti
  • Klaus-Dieter Schewe
  • Loredana Tec
Journalcs.LO - Logic in Computer Science, arXiv:1602.07486 [cs.LO]

Database transformations provide a unifying framework for database queries and updates. Recently, it was shown that non-deterministic database transformations can be captured exactly by a variant of ASMs, the so-called Database Abstract StateMachines (DB-ASMs). In this article we present a logic for DB-ASMs, extending the logic of Nanchen and Stärk for ASMs. In particular, we develop a rigorous proof system for the logic for DB-ASMs, which is proven to be sound and complete. The most difficult challenge to be handled by the extension is a proper formalisation capturing non-determinism of database transformations and all its related features such as consistency, update sets or multisets associated with DB-ASM rules. As the database part of a state of database transformations is a finite structure and DB-ASMs are restricted by allowing quantifiers only over the database part of a state, we resolve this problem by taking update sets explicitly into the logic, i.e. by using an additional modal operator [X], where X is interpreted as an update set _ generated by a DB-ASM rule. The DB-ASM logic provides a powerful verification tool to study properties of database transformations.