×
Schweikardt, Nicole; Segoufin, Luc; Vigny, Alexandre

Enumeration for FO queries over nowhere dense graphs. (English) Zbl 07679918

J. ACM 69, No. 3, Article No. 22, 37 p. (2022).

Cited in 3 Documents

MSC:

68-XX Computer science

Keywords:

constant-delay enumeration; sparse graphs; query evaluation
Cite Review PDF
Full Text: DOI HAL

References:

[1] Abiteboul, Serge, Hull, Richard, and Vianu, Victor. 1995. Foundations of Databases. Addison-Wesley. · Zbl 0848.68031
[2] Amarilli, Antoine, Bourhis, Pierre, Mengel, Stefan, and Niewerth, Matthias. 2019. Enumeration on trees with tractable combined complexity and efficient updates. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS’19), Suciu, Dan, Skritek, Sebastian, and Koch, Christoph (Eds.). ACM, 89-103. · Zbl 07561482
[3] Bagan, Guillaume. 2006. MSO queries on tree decomposable structures are computable with linear delay. In Proceedings of the 20th International Conference of the Computer Science Logic (CSL’06), Ésik, Zoltán (Ed.), Vol. 4207. Springer, 167-181. · Zbl 1225.68268
[4] Bagan, Guillaume, Durand, Arnaud, and Grandjean, Etienne. 2007. On acyclic conjunctive queries and constant delay enumeration. In Proceedings of the International Conference of the Computer Science Logic (CSL’07), Duparc, Jacques and Henzinger, Thomas A. (Eds.), Vol. 4646. Springer, 208-222. · Zbl 1179.68047
[5] Balmin, Andrey, Papakonstantinou, Yannis, and Vianu, Victor. 2004. Incremental validation of XML documents. ACM Trans. Database Syst.29, 4 (2004), 710-751. · Zbl 1022.68521
[6] Berkholz, Christoph, Keppeler, Jens, and Schweikardt, Nicole. 2017. Answering conjunctive queries under updates. In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS’17), Sallinger, Emanuel, Bussche, Jan Van den, and Geerts, Floris (Eds.). ACM, 303-318.
[7] Berkholz, Christoph, Keppeler, Jens, and Schweikardt, Nicole. 2018. Answering FO+MOD queries under updates on bounded degree databases. ACM Trans. Database Syst.43, 2 (2018), 7:1-7:32. · Zbl 1474.68080
[8] Berkholz, Christoph, Keppeler, Jens, and Schweikardt, Nicole. 2018. Answering UCQs under Updates and in the presence of integrity constraints. In Proceedings of the 21st International Conference on Database Theory (ICDT’18), Kimelfeld, Benny and Amsterdamer, Yael (Eds.), Vol. 98. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 8:1-8:19. · Zbl 1489.68069
[9] Downey, Rodney G., Fellows, Michael R., and Taylor, Udayan. 1996. The parameterized complexity of relational database queries and an improved characterization of W[1]. In Proceedings of the 1st Conference of the Centre for Discrete Mathematics and Theoretical Computer Science (DMTCS’96), Bridges, Douglas S., Calude, Cristian S., Gibbons, Jeremy, Reeves, Steve, and Witten, Ian H. (Eds.). Springer-Verlag, Singapore, 194-213. · Zbl 0918.68018
[10] Durand, Arnaud and Grandjean, Etienne. 2007. First-order queries on structures of bounded degree are computable with constant delay. ACM Trans. Comput. Log.8, 4 (2007), 21. · Zbl 1367.68086
[11] Durand, Arnaud, Schweikardt, Nicole, and Segoufin, Luc. 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), Hull, Richard and Grohe, Martin (Eds.). ACM, 121-131. · Zbl 07566063
[12] Frick, Markus. 2004. Generalized model-checking over locally tree-decomposable classes. Theory Comput. Syst.37, 1 (2004), 157-191. · Zbl 1101.68727
[13] Frick, Markus and Grohe, Martin. 2001. Deciding first-order properties of locally tree-decomposable structures. J. ACM48, 6 (2001), 1184-1206. · Zbl 1323.03014
[14] Frick, Markus and Grohe, Martin. 2004. The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic130, 1-3 (2004), 3-31. · Zbl 1062.03032
[15] Gaifman, Haim. 1982. On local and non-local properties. In Proceedings of the Herbrand Symposium. , Vol. 107. Elsevier, 105-135. · Zbl 0518.03008
[16] Grohe, Martin, Kreutzer, Stephan, and Siebertz, Sebastian. 2014. Deciding first-order properties of nowhere dense graphs. In Proceedings of the Symposium on Theory of Computing (STOC’14), Shmoys, David B. (Ed.). ACM, 89-98. · Zbl 1315.05118
[17] Grohe, Martin, Kreutzer, Stephan, and Siebertz, Sebastian. 2017. Deciding first-order properties of nowhere dense graphs. J. ACM64, 3 (2017), 17:1-17:32. · Zbl 1426.68172
[18] Grohe, Martin and Schweikardt, Nicole. 2018. First-order query evaluation with cardinality conditions. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS’18). ACM. Full version available at CoRR, http://arxiv.org/abs/1707.05945, 2017. · Zbl 1125.03024
[19] Kazana, Wojciech. 2013. Query evaluation with constant delay. (L’évaluation de requêtes avec un délai constant). . École normale supérieure de Cachan, Paris, France.
[20] Kazana, Wojciech and Segoufin, Luc. 2011. First-order query evaluation on structures of bounded degree. Logic. Methods Comput. Sci.7, 2 (2011). · Zbl 1353.68068
[21] Kazana, Wojciech and Segoufin, Luc. 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), Hull, Richard and Fan, Wenfei (Eds.). ACM, 297-308. · Zbl 1353.68068
[22] Kazana, Wojciech and Segoufin, Luc. 2013. Enumeration of monadic second-order queries on trees. ACM Trans. Comput. Log.14, 4 (2013), 25:1-25:12. · Zbl 1353.68068
[23] Knuth, Donald Ervin. 1998. The Art of Computer Programming, Volume III (2nd ed.). Addison-Wesley. · Zbl 1170.68411
[24] Kreutzer, Stephan and Dawar, Anuj. 2009. Parameterized complexity of first-order logic. Electr. Colloq. Comput. Complex.16 (2009), 131. · Zbl 1248.68241
[25] Libkin, Leonid. 2004. Elements of Finite Model Theory. Springer. · Zbl 1060.03002
[26] Nesetril, Jaroslav and Mendez, Patrice Ossona de. 2010. First order properties on nowhere dense structures. J. Symb. Log.75, 3 (2010), 868-887. · Zbl 1206.03033
[27] Nesetril, Jaroslav and Mendez, Patrice Ossona de. 2011. On nowhere dense graphs. Eur. J. Comb.32, 4 (2011), 600-617. · Zbl 1226.05102
[28] Niewerth, Matthias and Segoufin, Luc. 2018. Enumeration of MSO queries on strings with constant delay and logarithmic updates. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS’18). ACM.
[29] Schweikardt, Nicole, Segoufin, Luc, and Vigny, Alexandre. 2018. Enumeration for FO queries over nowhere dense graphs. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Bussche, Jan Van den and Arenas, Marcelo (Eds.). ACM, 151-163. · Zbl 07679918
[30] Segoufin, Luc and Vigny, Alexandre. 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), Benedikt, Michael and Orsi, Giorgio (Eds.), Vol. 68. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 20:1-20:16. · Zbl 1402.68052
[31] Siebertz, Sebastian. 2016. Nowhere Dense Classes of Graphs: Characterisations and Algorithmic Meta-Theorems. . Technical University of Berlin, Germany.
[32] Tarjan, Robert Endre and Yao, Andrew Chi-Chih. 1979. Storing a sparse table. Commun. ACM22, 11 (1979), 606-611. · Zbl 0414.68038
[33] Vardi, Moshe Y.. 1982. The complexity of relational query languages (Extended Abstract). In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, Lewis, Harry R., Simons, Barbara B., Burkhard, Walter A., and Landweber, Lawrence H. (Eds.). ACM, 137-146.
[34] Vigny, Alexandre. 2018. Query enumeration and nowhere dense graphs. (Énumération des requêtes et graphes nulle-part denses). . Paris Diderot University, France.
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.