Enumerating answers to first-order queries over databases of low degree. (English) Zbl 07566063
Summary: A class of relational databases has low degree if for all \(\delta>0\), all but finitely many databases in the class have degree at most \(n^\delta\), where \(n\) is the size of the database. Typical examples are databases of bounded degree or of degree bounded by \(\log n\).
It is known that over a class of databases having low degree, first-order Boolean queries can be checked in pseudo-linear time, i.e. for all \(\epsilon>0\) in time bounded by \(n^{1+\epsilon}\). We generalize this result by considering query evaluation.
We show that counting the number of answers to a query can be done in pseudo-linear time and that after a pseudo-linear time preprocessing we can test in constant time whether a given tuple is a solution to a query or enumerate the answers to a query with constant delay.
It is known that over a class of databases having low degree, first-order Boolean queries can be checked in pseudo-linear time, i.e. for all \(\epsilon>0\) in time bounded by \(n^{1+\epsilon}\). We generalize this result by considering query evaluation.
We show that counting the number of answers to a query can be done in pseudo-linear time and that after a pseudo-linear time preprocessing we can test in constant time whether a given tuple is a solution to a query or enumerate the answers to a query with constant delay.
References:
| [1] | Guillaume Bagan. MSO queries on tree decomposable structures are computable with linear delay. InProc. of Computer Science Logic (CSL’06), pages 167-181, 2006. · Zbl 1225.68268 |
| [2] | Johann Brault-Baron. A negative conjunctive query is easy if and only if it is beta-acyclic. In Proc. of Computer Science Logic (CSL’12), 2012. · Zbl 1252.68092 |
| [3] | Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On acyclic conjunctive queries and constant delay enumeration. InProc. of Computer Science Logic (CSL’07), pages 208-222, 2007. · Zbl 1179.68047 |
| [4] | Bruno Courcelle. Linear delay enumeration and monadic second-order logic.Discrete Applied Mathematics, 157(12):2675-2700, 2009. · Zbl 1217.03024 |
| [5] | Arnaud Durand and Etienne Grandjean. First-order queries on structures of bounded degree are computable with constant delay.ACM Transactions on Computational Logic, 8(4), 2007. · Zbl 1367.68086 |
| [6] | Anuj Dawar, Martin Grohe, Stephan Kreutzer, and Nicole Schweikardt. Model theory makes formulas large. InAutomata, Languages and Programming, 34th International Colloquium, ICALP · Zbl 1171.03324 |
| [7] | Zdenek Dvor´ak, Daniel Kr´al, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs.J. ACM, 60(5):36:1-36:24, 2013. · Zbl 1281.05114 |
| [8] | Arnaud Durand, Nicole Schweikardt, and Luc Segoufin. Enumerating answers to first-order queries over databases of low degree. InProc. Symp. on Principles of Database Systems (PODS’14), 2014. doi:10.1145/2594538.2594539. |
| [9] | Markus Frick and Martin Grohe. The complexity of first-order and monadic second-order logic revisited.Annals of Pure and Applied Logic, 130(1-3):3-31, 2004. · Zbl 1062.03032 |
| [10] | J¨org Flum and Martin Grohe.Parameterized Complexity Theory. Springer-Verlag, 2006. · Zbl 1143.68016 |
| [11] | Haim Gaifman. On local and nonlocal properties. In J. Stern, editor,Logic Colloquium’81, pages 105-135. North-Holland, 1982. · Zbl 0518.03008 |
| [12] | Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs.J. ACM, 64(3):17:1-17:32, 2017.doi:10.1145/3051095. · Zbl 1426.68172 |
| [13] | Etienne Grandjean and Fr´ed´eric Olive. Graph properties checkable in linear time in the number of vertices.Journal of Computer and System Sciences, 68(3):546-597, 2004. · Zbl 1069.68079 |
| [14] | Martin Grohe. Generalized model-checking problems for first-order logic. InProc. Symp. on Theoretical Aspects of Computer Science (STACS’01), 2001. · Zbl 0976.68077 |
| [15] | Stephan Kreutzer and Anuj Dawar. Parameterized complexity of first-order logic.Electronic Colloquium on Computational Complexity (ECCC), 16:131, 2009. · Zbl 1248.68241 |
| [16] | Wojciech Kazana and Luc Segoufin. First-order query evaluation on structures of bounded degree. Logical Methods in Computer Science, 7(2), 2011. · Zbl 1353.68068 |
| [17] | Wojciech Kazana and Luc Segoufin. Enumeration of monadic second-order queries on trees.ACM Transactions on Computational Logic, 14(4), 2013. · Zbl 1353.68068 |
| [18] | Wojciech Kazana and Luc Segoufin. Enumeration of first-order queries on classes of structures with bounded expansion.Logical Methods in Computer Science, 16(1), 2020. · Zbl 1353.68068 |
| [19] | Johann A. Makowsky. Algorithmic uses of the Feferman-Vaught Theorem.Annals of Pure and Applied Logic, 126(1-3):159-213, 2004. · Zbl 1099.03009 |
| [20] | Nicole Schweikardt, Luc Segoufin, and Alexandre Vigny. Enumeration for FO queries over nowhere dense graphs. InProc. of Symp. on Principles of Database Systems (PODS), 2018. doi:10.1145/3196959.3196971. |
| [21] | Nicole Schweikardt, Luc Segoufin, and Alexandre Vigny. Enumeration for FO queries over nowhere dense graphs.Journal version of[SSV18], submitted, 2020. |
| [22] | Alexandre Vigny. Dynamic query evaluation over structures with low degree.CoRR, abs/2010.02982, 2020. URL:https://arxiv.org/abs/2010.02982,arXiv:2010.02982. |
| [23] | Mihalis Yannakakis. Algorithms for acyclic database schemes. InProc. Intl. Conf. on Very Large Data Bases (VLDB’81), 1981. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
