uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Reachability in database-driven systems with numerical attributes under recency bounding
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.ORCID iD: 0000-0001-6832-6611
Chennai Mathematical Institute, Chennai, India.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.ORCID iD: 0000-0001-8229-3481
Free University of Bozen-Bolzano, Bolzano, Italy.
2019 (English)In: PODS '19: Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, New York: ACM Press, 2019, p. 335-352Conference paper, Published paper (Refereed)
Abstract [en]

A prominent research direction of the database theory community is to develop techniques for verification of database-driven systems operating over relational and numerical data. Along this line, we lift the framework of database manipulating systems [3] which handle relational data to also accommodate numerical data and the natural order on them. We study an under-approximation called recency bounding under which the most basic verification problem-reachability, is decidable. Even under this under-approximation the reachability space is infinite in multiple dimensions - owing to the unbounded sizes of the active domain, the unbounded numerical domain it has access to, and the unbounded length of the executions. We show that, nevertheless, reachability is ExpTime complete. Going beyond reachability to LTL model checking renders verification undecidable.

Place, publisher, year, edition, pages
New York: ACM Press, 2019. p. 335-352
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:uu:diva-398249DOI: 10.1145/3294052.3319705ISI: 000502009600024ISBN: 978-1-4503-6227-6 (electronic)OAI: oai:DiVA.org:uu-398249DiVA, id: diva2:1375101
Conference
38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), Amsterdam, Netherlands, July 1-3, 2019
Available from: 2019-06-25 Created: 2019-12-04 Last updated: 2020-01-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Abdulla, Parosh AzizAtig, Mohamed Faouzi

Search in DiVA

By author/editor
Abdulla, Parosh AzizAtig, Mohamed Faouzi
By organisation
Computer Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 21 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf