research-article

Answering FO+MOD Queries under Updates on Bounded Degree Databases

Authors:

Christoph Berkholz,

Nicole SchweikardtAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 43, Issue 2

Article No.: 7, Pages 1 - 32

https://doi.org/10.1145/3232056

Published: 22 August 2018 Publication History

Abstract

We investigate the query evaluation problem for fixed queries over fully dynamic databases, where tuples can be inserted or deleted. The task is to design a dynamic algorithm that immediately reports the new result of a fixed query after every database update.

We consider queries in first-order logic (FO) and its extension with modulo-counting quantifiers (FO+MOD) and show that they can be efficiently evaluated under updates, provided that the dynamic database does not exceed a certain degree bound.

In particular, we construct a data structure that allows us to answer a Boolean FO+MOD query and to compute the size of the result of a non-Boolean query within constant time after every database update. Furthermore, after every database update, we can update the data structure in constant time such that afterwards we are able to test within constant time for a given tuple whether or not it belongs to the query result, to enumerate all tuples in the new query result, and to enumerate the difference between the old and the new query result with constant delay between the output tuples. The preprocessing time needed to build the data structure is linear in the size of the database.

Our results extend earlier work on the evaluation of first-order queries on static databases of bounded degree and rely on an effective Hanf normal form for FO+MOD recently obtained by Heimberg, Kuske, and Schweikardt (LICS 2016).

References

[1]

Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley.

Digital Library

[2]

Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2017. Answering conjunctive queries under updates. In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, (PODS’17), Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts (Eds.). ACM, 303--318.

Digital Library

[3]

Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2017. Answering FO+MOD queries under updates on bounded degree databases. In Proceedings of the 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy (LIPIcs), Michael Benedikt and Giorgio Orsi (Eds.), Vol. 68. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 8:1--8:18.

[4]

Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2018. Answering UCQs under Updates and in the presence of integrity constraints. In Proceedings of the 21st International Conference on Database Theory (ICDT’18). 8:1--8:19.

[5]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press.

Digital Library

[6]

Arnaud Durand and Etienne Grandjean. 2007. First-order queries on structures of bounded degree are computable with constant delay. ACM Trans. Comput. Log. 8, 4 (2007).

Digital Library

[7]

Arnaud Durand, Nicole Schweikardt, and Luc Segoufin. 2014. Enumerating answers to first-order queries over databases of low degree. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’14). 121--131.

Digital Library

[8]

Markus Frick and Martin Grohe. 2004. The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic 130, 1--3 (2004), 3--31.

[9]

Martin Grohe. 2017. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Lecture Notes in Logic, Vol. 47. Association for Symbolic Logic in conjunction with Cambridge University Press.

[10]

Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. 2017. Deciding first-order properties of nowhere dense graphs. J. ACM 64, 3 (2017), 17:1--17:32. Conference version: in Proceedings of the 46th ACM Symposium on Theory of Computing (STOC’14), pp. 89--98, 2014.

Digital Library

[11]

Martin Grohe and Nicole Schweikardt. 2018. First-order query evaluation with cardinality conditions. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’18).

Digital Library

[12]

Lucas Heimberg, Dietrich Kuske, and Nicole Schweikardt. 2016. Hanf normal form for first-order logic with unary counting quantifiers. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’16). 277--286.

Digital Library

[13]

Wojciech Kazana and Luc Segoufin. 2011. First-order query evaluation on structures of bounded degree. Logic. Methods Comput. Sci. 7, 2 (2011).

[14]

Wojciech Kazana and Luc Segoufin. 2013. Enumeration of first-order queries on classes of structures with bounded expansion. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’13). 297--308.

Digital Library

[15]

Dietrich Kuske and Nicole Schweikardt. 2017. First-order logic with counting: At least, weak Hanf normal forms always exist and can be computed&excl; In Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’17). Full version available at CoRR abs/1703.01122.

[16]

Leonid Libkin. 2004. Elements of Finite Model Theory. Springer.

Digital Library

[17]

Eugene M. Luks. 1982. Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25, 1 (1982), 42--65.

[18]

Bernard M. E. Moret and Henry D. Shapiro. 1991. Algorithms from P to NP: Volume 1: Design 8 Efficiency. Benjamin-Cummings.

Digital Library

[19]

Sushant Patnaik and Neil Immerman. 1997. Dyn-FO: A parallel, dynamic complexity class. J. Comput. Syst. Sci. 55, 2 (1997), 199--209.

Digital Library

[20]

Nicole Schweikardt, Luc Segoufin, and Alexandre Vigny. 2018. Enumeration for FO queries over nowhere dense graphs. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’18).

Digital Library

[21]

Thomas Schwentick and Thomas Zeume. 2016. Dynamic complexity: Recent updates. SIGLOG News 3, 2 (2016), 30--52.

Digital Library

[22]

Detlef Seese. 1996. Linear time computable problems and first-order descriptions. Math. Struct. Comput. Sci. 6, 6 (1996), 505--526.

[23]

Luc Segoufin and Alexandre Vigny. 2017. Constant delay enumeration for FO queries over databases with local bounded expansion. In Proceedings of the 20th International Conference on Database Theory (ICDT’17). 20:1--20:16.

Cited By

Schirrmacher NSiebertz SStamoulis GThilikos DVigny ASobocinski PLago UEsparza J(2024)Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph ClassesProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662089(1-12)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662089
Nešetřil JOssona de Mendez PSiebertz S(2024)Modulo-counting first-order logic on bounded expansion classesDiscrete Mathematics10.1016/j.disc.2023.113700347:8(113700)Online publication date: Aug-2024
https://doi.org/10.1016/j.disc.2023.113700
Berkholz CMerz MLibkin LPichler RGuagliardo P(2021)Probabilistic Databases under UpdatesProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3452021.3458326(402-415)Online publication date: 20-Jun-2021
https://dl.acm.org/doi/10.1145/3452021.3458326
Show More Cited By

Index Terms

Answering FO+MOD Queries under Updates on Bounded Degree Databases
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Learning latent representations
      2. Logical and relational learning
        Statistical relational learning
2. Human-centered computing
  1. Visualization
    1. Empirical studies in visualization

Recommendations

Answering Conjunctive Queries under Updates
PODS '17: Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

We consider the task of enumerating and counting answers to k-ary conjunctive queries against relational databases that may be updated by inserting or deleting tuples. We exhibit a new notion of q-hierarchical conjunctive queries and show that these can ...
Answering Queries over Inconsistent Databases Using SAT Solvers
Answering Queries Using Views

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 43, Issue 2

Best of ICDT 2017 and Regular Papers

June 2018

154 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/3243648

Editor:
Christian S. Jensen
Aalborg University, Denmark

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 August 2018

Accepted: 01 June 2018

Revised: 01 April 2018

Received: 01 July 2017

Published in TODS Volume 43, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

German Research Foundation DFG

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
197
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Schirrmacher NSiebertz SStamoulis GThilikos DVigny ASobocinski PLago UEsparza J(2024)Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph ClassesProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662089(1-12)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662089
Nešetřil JOssona de Mendez PSiebertz S(2024)Modulo-counting first-order logic on bounded expansion classesDiscrete Mathematics10.1016/j.disc.2023.113700347:8(113700)Online publication date: Aug-2024
https://doi.org/10.1016/j.disc.2023.113700
Berkholz CMerz MLibkin LPichler RGuagliardo P(2021)Probabilistic Databases under UpdatesProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3452021.3458326(402-415)Online publication date: 20-Jun-2021
https://dl.acm.org/doi/10.1145/3452021.3458326
Tao YYi K(2021)Intersection Joins under UpdatesJournal of Computer and System Sciences10.1016/j.jcss.2021.09.004Online publication date: Sep-2021
https://doi.org/10.1016/j.jcss.2021.09.004
Berkholz CGerhardt FSchweikardt N(2020)Constant delay enumeration for conjunctive queriesACM SIGLOG News10.1145/3385634.33856367:1(4-33)Online publication date: 24-Feb-2020
https://dl.acm.org/doi/10.1145/3385634.3385636
Schweikardt NBouyer P(2019)Local normal forms and their use in algorithmic meta theoremsProceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3470152.3470195(1-3)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.5555/3470152.3470195
Schweikardt N(2019)Local normal forms and their use in algorithmic meta theorems (Invited Talk)2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)10.1109/LICS.2019.8785748(1-3)Online publication date: Jun-2019
https://doi.org/10.1109/LICS.2019.8785748
Elghandour IKara AOlteanu DVansummeren SCuzzocrea AAllan JPaton NSrivastava DAgrawal RBroder AZaki MCandan SLabrinidis ASchuster AWang H(2018)Incremental Techniques for Large-Scale Dynamic Query ProcessingProceedings of the 27th ACM International Conference on Information and Knowledge Management10.1145/3269206.3274271(2297-2298)Online publication date: 17-Oct-2018
https://dl.acm.org/doi/10.1145/3269206.3274271
Niewerth M(2018)MSO Queries on TreesProceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3209108.3209144(769-778)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.1145/3209108.3209144

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents