Query answering for static databases ,
,
, , p.33
,
40 Nowhere dense and somewhere dense classes of graphs ,
,
,
Query answering for databases subject to local updates ,
, Counting FO queries Contents 7.1 Introduction
,
, 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 ?
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
? 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 #
Foundations of Databases, 1995. ,
The Design and Analysis of Computer Algorithms, 1974. ,
Enumeration on trees under relabelings, Intl. Conf. on Database Theory (ICDT), 2018. ,
Easy problems for treedecomposable graphs, J. Algorithms, vol.12, issue.2, pp.308-340, 1991. ,
Reverse search for enumeration, Discrete Applied Mathematics, vol.65, issue.1-3, pp.21-46, 1996. ,
MSO queries on tree decomposable structures are computable with linear delay, Conf. on Computer Science Logic (CSL), 2006. ,
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. ,
EEcient enumeration for conjunctive queries over x-underbar structures, Conf. on Computer Science Logic (CSL), 2010. ,
On acyclic conjunctive queries and constant delay enumeration, Conf. on Computer Science Logic (CSL), 2007. ,
URL : https://hal.archives-ouvertes.fr/hal-00195010
Computing the jth solution of a rst-order query, ITA, vol.42, issue.1, pp.147-164, 2008. ,
Incremental validation of XML documents, ACM Trans. Database Syst, vol.29, issue.4, pp.710-751, 2004. ,
Answering conjunctive queries under updates, Symp. on Principles of Database Systems (PODS), 2017. ,
Answering FO + MOD queries under updates on bounded degree databases, Intl. Conf. on Database Theory (ICDT), 2017. ,
Answering ucqs under updates and in the presence of integrity constraints, Intl. Conf. on Database Theory (ICDT), 2018. ,
Generating all the minimal separators of a graph, Int. J. Found. Comput. Sci, vol.11, issue.3, pp.397-403, 2000. ,
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. ,
On the complexity of enumeration, 2017. ,
Matrix multiplication via arithmetic progressions, J. Symb. Comput, vol.9, issue.3, pp.251-280, 1990. ,
Graph rewriting: An algebraic and logic approach, Formal Models and Sematics (B), vol.B, pp.193-242, 1990. ,
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
On generating all solutions of generalized satissability problems, ITA, vol.31, issue.6, pp.499-511, 1997. ,
Reachability is in dynfo, Intl. Coll. on Automata, Languages and Programming (ICALP), 2015. ,
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
The complexity of weighted counting for acyclic conjunctive queries, J. Comput. Syst. Sci, vol.80, issue.1, pp.277-296, 2014. ,
Enumerating answers to rst-order queries over databases of low degree, Symp. on Principles of Database Systems (PODS), 2014. ,
Enumeration complexity of logical query problems with second-order variables, Conf. on Computer Science Logic (CSL), 2011. ,
Testing rst-order properties for subclasses of sparse graphs, J. ACM, vol.60, issue.5, p.36, 2013. ,
Document spanners: A formal approach to information extraction, J. ACM, vol.62, issue.2, 2015. ,
Stijn Vansummeren, and Domagoj Vrgoc. Constant delay algorithms for regular document spanners, Symp. on Principles of Database Systems (PODS), 2018. ,
, Parameterized Complexity Theory, 2006.
Joining extractions of regular expressions, Symp. on Principles of Database Systems (PODS), 2018. ,
Generalized model-checking over locally tree-decomposable classes, Theory Comput. Syst, vol.37, issue.1, pp.157-191, 2004. ,
Deciding rst-order properties of locally treedecomposable structures, J. ACM, vol.48, issue.6, pp.1184-1206, 2001. ,
The complexity of rst-order and monadic secondorder logic revisited, Ann. Pure Appl. Logic, vol.130, issue.1-3, pp.3-31, 2004. ,
On local and non-local properties, Proceedings of the Herbrand Symposium, 1982. ,
A new perspective on FO model checking of dense graph classes, Symp. on Logic in Computer Science (LICS), 2016. ,
First-order interpretations of bounded expansion classes, Intl. Coll. on Automata, Languages and Programming (ICALP), 2018. ,
Powers of tensors and fast matrix multiplication, Intl. Symp. on Symbolic and Algebraic Computation (ISSAC), 2014. ,
The dynamic complexity of formal languages, ACM Trans. Comput. Log, vol.13, issue.3, 2012. ,
Sorting, linear time and the satissability problem, Ann. Math. Artif. Intell, vol.16, pp.183-236, 1996. ,
Generalized model-checking problems for rst-order logic, Symp. on Theoretical Aspects in Computer Science (STACS), 2001. ,
Logic, graphs, and algorithms, Logic and Automata, 2008. ,
Deciding rst-order properties of nowhere dense graphs, Symp. on Theory of Computing (STOC), 2014. ,
Deciding rst-order properties of nowhere dense graphs, J. ACM, vol.64, issue.3, 2017. ,
First-order query evaluation with cardinality conditions, Symp. on Principles of Database Systems (PODS), 2018. ,
Hanf normal form for rst-order logic with unary counting quantiiers, Symp. on Logic in Computer Science (LICS), 2016. ,
On generating all maximal independent sets, Inf. Process. Lett, vol.27, issue.3, pp.119-123, 1988. ,
Query evaluation with constant delay. (L'évaluation de requêtes avec un délai constant), 2013. ,
URL : https://hal.archives-ouvertes.fr/tel-00919786
First-order query evaluation on structures of bounded degree, Logical Methods in Computer Science, vol.7, issue.2, 2011. ,
Enumeration of rst-order queries on classes of structures with bounded expansion, Symp. on Principles of Database Systems (PODS), 2013. ,
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
On the complexity of some enumeration problems for matroids, SIAM J. Discrete Math, vol.19, issue.4, pp.966-984, 2005. ,
Orderings on graphs and game coloring number, Order, vol.20, issue.3, pp.255-264, 2003. ,
On the parameterised intractability of monadic second-order logic, Conf. on Computer Science Logic (CSL), 2009. ,
Parameterized complexity of rst-order logic, Electronic Colloquium on Computational Complexity (ECCC), vol.16, p.131, 2009. ,
Elements of Finite Model Theory, 2004. ,
MSO queries on trees: enumerating answers under updates, Conf. on Computer Science Logic & Symp. on Logic in Computer Science (CSL-LICS), 2014. ,
Grad and classes with bounded expansion I. decompositions, Eur. J. Comb, vol.29, issue.3, pp.760-776, 2008. ,
Grad and classes with bounded expansion II. algorithmic aspects, Eur. J. Comb, vol.29, issue.3, pp.777-791, 2008. ,
First order properties on nowhere dense structures, J. Symb. Log, vol.75, issue.3, pp.868-887, 2010. ,
On nowhere dense graphs, Eur. J. Comb, vol.32, issue.4, pp.600-617, 2011. ,
, , 2012.
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
On the complexity of database queries, J. Comput. Syst. Sci, vol.58, issue.3, pp.407-427, 1999. ,
Tractable counting of the answers to conjunctive queries, J. Comput. Syst. Sci, vol.79, issue.6, pp.984-1001, 2013. ,
Linear time computable problems and rst-order descriptions, Mathematical Structures in Computer Science, vol.6, issue.6, pp.505-526, 1996. ,
Enumerating with constant delay the answers to a query, Intl. Conf. on Database Theory (ICDT), 2013. ,
Constant delay enumeration for FO queries over databases with local bounded expansion, Intl. Conf. on Database Theory (ICDT, 2017. ,
EEcient enumeration of all minimal separators in a graph, Theor. Comput. Sci, vol.180, issue.1-2, pp.169-180, 1997. ,
Enumeration complexity and matroid decomposition, 2010. ,
Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph, Discrete Applied Mathematics, vol.158, issue.15, pp.1660-1667, 2010. ,
Storing a sparse table, Commun. ACM, vol.22, issue.11, pp.606-611, 1979. ,
Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs, In Intl. Symp. Algorithms and Computation, 1997. ,
Algorithms for acyclic database schemes, Very Large Data Bases (VLDB), 1981. ,
Small dynamic complexity classes, 2015. ,