. , Query answering for static databases

. .. Arbitrary-relational-structures,

. .. Acyclic-conjunctive-queries, , p.33

.. .. Free,

X. .. , 40 Nowhere dense and somewhere dense classes of graphs

. .. Discussions,

.. .. Pseudo-linear-time,

M. ). , Query answering for databases subject to local updates

. , Counting FO queries Contents 7.1 Introduction

. .. Conclusion,

, We recall what the counting problem is: Given a structure A and a query q(x) in FO we want, to compute |q(A)| the size of the set q(A). The result that we are going to prove in details is that rst-order queries can be

, Let q(x) be a rst-order query and C a nowhere dense class of undirected colored graphs. For every > 0, there is an algorithm which on input a graph G = (V, E) ? C computes in time O(|V | 1+ ) the size |q(G)| of the set q(G). Furthermore, if C is eeectively nowhere dense, there is an algorithm which on input > 0, a colored graph G = (V, E) ? C and a rst-order query q(x)

, This results has already been proved in [45], where "counting terms" are added in rst-order logic, increasing its expressive power enough to express the counting problem as deened above. Here, we use some of their ideas (mainly the Rank-Preserving Normal Form, Here, the constants in the O(·) may depend on q, C and

, If n ? f C (2kr, ?), where n := |V |, we use a brute-force algorithm to compute the result |?(G)|. From now on, consider the case where n > f C (2kr, ?)

, Using the algorithm provided by Theorem 4.2.6, we compute a (kr, 2kr)-neighborhood cover X of G with degree at most n ?

. Furthermore, we also compute for each X ? X a list of all b ? V satisfying X (b) = X, and we compute a node c X, the same way as in

, We use the algorithm provided by the Counting Normal Form Theorem

G. and G. , ? new r-local queries ? 1 (x 1 ), ? 2 (x 2 ),. . ., ? ? (x ? ) of q-rank at most and arities at most k, ? and an arithmetic function F of arity ?

, What remains to compute is, for every i ? ?, the number #(G , X , ? i )

, Since G ? C ? , we know that Splitter wins the (?, 2kr)-Splitter game on G. For every X ? X we now compute a node s X that is Splitter's answer if Connector plays c X in the rst round of the (?, 2kr)-splitter game on G

, For a xed i ? ?, let k i be the arity of ? i and x i = (x i,1 ,. .. , x i,k i ) its variables. We want to restrict our attention to bags of the cover. The diiculty is that #

S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases, 1995.

A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, 1974.

A. Amarilli, P. Bourhis, and S. Mengel, Enumeration on trees under relabelings, Intl. Conf. on Database Theory (ICDT), 2018.

S. Arnborg, J. Lagergren, and D. Seese, Easy problems for treedecomposable graphs, J. Algorithms, vol.12, issue.2, pp.308-340, 1991.

D. Avis and K. Fukuda, Reverse search for enumeration, Discrete Applied Mathematics, vol.65, issue.1-3, pp.21-46, 1996.

G. Bagan, MSO queries on tree decomposable structures are computable with linear delay, Conf. on Computer Science Logic (CSL), 2006.

G. Bagan, Algorithmes et complexité des problèmes d'énumération pour l'évaluation de requêtes logiques. (Algorithms and complexity of enumeration problems for the evaluation of logical queries), 2009.

G. Bagan, A. Durand, E. Filiot, and O. Gauwin, EEcient enumeration for conjunctive queries over x-underbar structures, Conf. on Computer Science Logic (CSL), 2010.

G. Bagan, A. Durand, and E. Grandjean, On acyclic conjunctive queries and constant delay enumeration, Conf. on Computer Science Logic (CSL), 2007.
URL : https://hal.archives-ouvertes.fr/hal-00195010

G. Bagan, A. Durand, E. Grandjean, and F. Olive, Computing the jth solution of a rst-order query, ITA, vol.42, issue.1, pp.147-164, 2008.

A. Balmin, Y. Papakonstantinou, and V. Vianu, Incremental validation of XML documents, ACM Trans. Database Syst, vol.29, issue.4, pp.710-751, 2004.

C. Berkholz, J. Keppeler, and N. Schweikardt, Answering conjunctive queries under updates, Symp. on Principles of Database Systems (PODS), 2017.

C. Berkholz, J. Keppeler, and N. Schweikardt, Answering FO + MOD queries under updates on bounded degree databases, Intl. Conf. on Database Theory (ICDT), 2017.

C. Berkholz, J. Keppeler, and N. Schweikardt, Answering ucqs under updates and in the presence of integrity constraints, Intl. Conf. on Database Theory (ICDT), 2018.

A. Berry, J. P. Bordat, and O. Cogis, Generating all the minimal separators of a graph, Int. J. Found. Comput. Sci, vol.11, issue.3, pp.397-403, 2000.

J. Brault-baron, De la pertinence de l'énumération : complexité en logiques propositionnelle et du premier ordre. (The relevance of the list: propositional logic and complexity of the rst order), 2013.

F. Capelli and Y. Strozecki, On the complexity of enumeration, 2017.

D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, J. Symb. Comput, vol.9, issue.3, pp.251-280, 1990.

B. Courcelle, Graph rewriting: An algebraic and logic approach, Formal Models and Sematics (B), vol.B, pp.193-242, 1990.

B. Courcelle, Linear delay enumeration and monadic second-order logic, Discrete Applied Mathematics, vol.157, issue.12, pp.2675-2700, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00333846

N. Creignou and J. Hébrard, On generating all solutions of generalized satissability problems, ITA, vol.31, issue.6, pp.499-511, 1997.

S. Datta, R. Kulkarni, A. Mukherjee, T. Schwentick, and T. Zeume, Reachability is in dynfo, Intl. Coll. on Automata, Languages and Programming (ICALP), 2015.

A. Durand and E. Grandjean, First-order queries on structures of bounded degree are computable with constant delay, ACM Trans. Comput. Log, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00195016

A. Durand and S. Mengel, The complexity of weighted counting for acyclic conjunctive queries, J. Comput. Syst. Sci, vol.80, issue.1, pp.277-296, 2014.

A. Durand, N. Schweikardt, and L. Segouun, Enumerating answers to rst-order queries over databases of low degree, Symp. on Principles of Database Systems (PODS), 2014.

A. Durand and Y. Strozecki, Enumeration complexity of logical query problems with second-order variables, Conf. on Computer Science Logic (CSL), 2011.

Z. Dvorak, D. Král, and R. Thomas, Testing rst-order properties for subclasses of sparse graphs, J. ACM, vol.60, issue.5, p.36, 2013.

R. Fagin, B. Kimelfeld, F. Reiss, and S. Vansummeren, Document spanners: A formal approach to information extraction, J. ACM, vol.62, issue.2, 2015.

F. Florenzano, C. Riveros, and M. Ugarte, Stijn Vansummeren, and Domagoj Vrgoc. Constant delay algorithms for regular document spanners, Symp. on Principles of Database Systems (PODS), 2018.

J. Flum and M. Grohe, Parameterized Complexity Theory, 2006.

D. Dominik, B. Freydenberger, L. Kimelfeld, and . Peterfreund, Joining extractions of regular expressions, Symp. on Principles of Database Systems (PODS), 2018.

M. Frick, Generalized model-checking over locally tree-decomposable classes, Theory Comput. Syst, vol.37, issue.1, pp.157-191, 2004.

M. Frick and M. Grohe, Deciding rst-order properties of locally treedecomposable structures, J. ACM, vol.48, issue.6, pp.1184-1206, 2001.

M. Frick and M. Grohe, The complexity of rst-order and monadic secondorder logic revisited, Ann. Pure Appl. Logic, vol.130, issue.1-3, pp.3-31, 2004.

H. Gaifman, On local and non-local properties, Proceedings of the Herbrand Symposium, 1982.

J. Gajarský, P. Hlinený, J. Obdrzálek, D. Lokshtanov, and M. S. Ramanujan, A new perspective on FO model checking of dense graph classes, Symp. on Logic in Computer Science (LICS), 2016.

J. Gajarský, S. Kreutzer, J. Ne?et?il, P. Ossona-de-mendez, M. Pilipczuk et al., First-order interpretations of bounded expansion classes, Intl. Coll. on Automata, Languages and Programming (ICALP), 2018.

F. Gall, Powers of tensors and fast matrix multiplication, Intl. Symp. on Symbolic and Algebraic Computation (ISSAC), 2014.

M. Wouter-gelade, T. Marquardt, and . Schwentick, The dynamic complexity of formal languages, ACM Trans. Comput. Log, vol.13, issue.3, 2012.

E. Grandjean, Sorting, linear time and the satissability problem, Ann. Math. Artif. Intell, vol.16, pp.183-236, 1996.

M. Grohe, Generalized model-checking problems for rst-order logic, Symp. on Theoretical Aspects in Computer Science (STACS), 2001.

M. Grohe, Logic, graphs, and algorithms, Logic and Automata, 2008.

M. Grohe, S. Kreutzer, and S. Siebertz, Deciding rst-order properties of nowhere dense graphs, Symp. on Theory of Computing (STOC), 2014.

M. Grohe, S. Kreutzer, and S. Siebertz, Deciding rst-order properties of nowhere dense graphs, J. ACM, vol.64, issue.3, 2017.

M. Grohe and N. Schweikardt, First-order query evaluation with cardinality conditions, Symp. on Principles of Database Systems (PODS), 2018.

L. Heimberg, D. Kuske, and N. Schweikardt, Hanf normal form for rst-order logic with unary counting quantiiers, Symp. on Logic in Computer Science (LICS), 2016.

D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis, On generating all maximal independent sets, Inf. Process. Lett, vol.27, issue.3, pp.119-123, 1988.

W. Kazana, Query evaluation with constant delay. (L'évaluation de requêtes avec un délai constant), 2013.
URL : https://hal.archives-ouvertes.fr/tel-00919786

W. Kazana and L. Segouun, First-order query evaluation on structures of bounded degree, Logical Methods in Computer Science, vol.7, issue.2, 2011.

W. Kazana and L. Segouun, Enumeration of rst-order queries on classes of structures with bounded expansion, Symp. on Principles of Database Systems (PODS), 2013.

W. Kazana and L. Segouun, Enumeration of monadic second-order queries on trees, ACM Trans. Comput. Log, vol.14, issue.4, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00916400

L. G. Khachiyan, E. Boros, K. M. Elbassioni, V. Gurvich, and K. Makino, On the complexity of some enumeration problems for matroids, SIAM J. Discrete Math, vol.19, issue.4, pp.966-984, 2005.

H. A. Kierstead and D. Yang, Orderings on graphs and game coloring number, Order, vol.20, issue.3, pp.255-264, 2003.

S. Kreutzer, On the parameterised intractability of monadic second-order logic, Conf. on Computer Science Logic (CSL), 2009.

S. Kreutzer and A. Dawar, Parameterized complexity of rst-order logic, Electronic Colloquium on Computational Complexity (ECCC), vol.16, p.131, 2009.

L. Libkin, Elements of Finite Model Theory, 2004.

K. Losemann and W. Martens, MSO queries on trees: enumerating answers under updates, Conf. on Computer Science Logic & Symp. on Logic in Computer Science (CSL-LICS), 2014.

J. Ne?et?il and P. Ossona-de-mendez, Grad and classes with bounded expansion I. decompositions, Eur. J. Comb, vol.29, issue.3, pp.760-776, 2008.

J. Ne?et?il and P. Ossona-de-mendez, Grad and classes with bounded expansion II. algorithmic aspects, Eur. J. Comb, vol.29, issue.3, pp.777-791, 2008.

J. Ne?et?il and P. Ossona-de-mendez, First order properties on nowhere dense structures, J. Symb. Log, vol.75, issue.3, pp.868-887, 2010.

J. Ne?et?il and P. Ossona-de-mendez, On nowhere dense graphs, Eur. J. Comb, vol.32, issue.4, pp.600-617, 2011.

J. Ne?et?il, P. Ossona-de-mendez, and . Sparsity, , 2012.

M. Niewerth and L. Segouun, Enumeration of MSO queries on strings with constant delay and logarithmic updates, Symp. on Principles of Database Systems (PODS), 2018.
URL : https://hal.archives-ouvertes.fr/hal-01895796

C. H. Papadimitriou and M. Yannakakis, On the complexity of database queries, J. Comput. Syst. Sci, vol.58, issue.3, pp.407-427, 1999.

R. Pichler and S. Skritek, Tractable counting of the answers to conjunctive queries, J. Comput. Syst. Sci, vol.79, issue.6, pp.984-1001, 2013.

D. Seese, Linear time computable problems and rst-order descriptions, Mathematical Structures in Computer Science, vol.6, issue.6, pp.505-526, 1996.

L. Segouun, Enumerating with constant delay the answers to a query, Intl. Conf. on Database Theory (ICDT), 2013.

L. Segouun and A. Vigny, Constant delay enumeration for FO queries over databases with local bounded expansion, Intl. Conf. on Database Theory (ICDT, 2017.

H. Shen and W. Liang, EEcient enumeration of all minimal separators in a graph, Theor. Comput. Sci, vol.180, issue.1-2, pp.169-180, 1997.

Y. Strozecki, Enumeration complexity and matroid decomposition, 2010.

K. Takata, Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph, Discrete Applied Mathematics, vol.158, issue.15, pp.1660-1667, 2010.

A. Robert-endre-tarjan and . Yao, Storing a sparse table, Commun. ACM, vol.22, issue.11, pp.606-611, 1979.

T. Uno, Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs, In Intl. Symp. Algorithms and Computation, 1997.

M. Yannakakis, Algorithms for acyclic database schemes, Very Large Data Bases (VLDB), 1981.

T. Zeume, Small dynamic complexity classes, 2015.