LIPIcs.ICDT.2017.20.pdf
- Filesize: 0.5 MB
- 16 pages
Document
Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion
Authors
-
Part of:
Volume:
20th International Conference on Database Theory (ICDT 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Database Theory (ICDT) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-03-17
Cite AsGet BibTex
Luc Segoufin and Alexandre Vigny. Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICDT.2017.20
https://doi.org/10.4230/LIPIcs.ICDT.2017.20
Abstract
We consider the evaluation of first-order queries over classes of databases with local bounded expansion. This class was introduced by Nesetril and Ossona de Mendez and generalizes many well known classes of databases, such as bounded degree, bounded tree width or bounded expansion. It is known that over classes of databases with local bounded expansion, first-order sentences can be evaluated in pseudo-linear time (pseudo-linear time means that for all \epsilon there exists an algorithm working in time O(n^{1+\epsilon})). Here, we investigate other scenarios, where queries are not sentences. We show that first-order queries can be enumerated with constant delay after a pseudo-linear preprocessing over any class of databases having locally bounded expansion. We also show that, in this context, counting the number of solutions can be done in pseudo-linear time.
Keywords
- enumeration
- first-order queries
- local bounded expansion.
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/.
-
Guillaume Bagan. MSO queries on tree decomposable structures are computable with linear delay. In Computer Science Logic (CSL'06), 2006.
- Arnaud Durand and Etienne Grandjean. First-order queries on structures of bounded degree are computable with constant delay. ACM Trans. Comput. Log., 8(4), 2007. URL: http://dx.doi.org/10.1145/1276920.1276923.
- Arnaud Durand, Nicole Schweikardt, and Luc Segoufin. Enumerating answers to first-order queries over databases of low degree. In Symp. on Principles of Database Systems (PODS'14), 2014. URL: http://dx.doi.org/10.1145/2594538.2594539.
- Zdenek Dvorak, Daniel Král, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. J. ACM, 60(5):36, 2013. URL: http://dx.doi.org/10.1145/2499483.
- Markus Frick. Generalized model-checking over locally tree-decomposable classes. Theory Comput. Syst., 37(1):157-191, 2004. URL: http://dx.doi.org/10.1007/s00224-003-1111-9.
- Markus Frick and Martin Grohe. Deciding first-order properties of locally tree-decomposable structures. J. ACM, 48(6):1184-1206, 2001. URL: http://dx.doi.org/10.1145/504794.504798.
- Markus Frick and Martin Grohe. The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic, 130(1-3):3-31, 2004. URL: http://dx.doi.org/10.1016/j.apal.2004.01.007.
- Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. In Symp. on Theory of Computing (STOC), 2014. URL: http://dx.doi.org/10.1145/2591796.2591851.
- Mamadou Moustapha Kanté. Graph Structurings: Some Algorithmic Applications. (Structurations de Graphes: Quelques Applications Algorithmiques). PhD thesis, University of Bordeaux, France, 2008. URL: https://tel.archives-ouvertes.fr/tel-00419301.
- Wojciech Kazana and Luc Segoufin. First-order query evaluation on structures of bounded degree. Logical Methods in Computer Science, 7(2), 2011. URL: http://dx.doi.org/10.2168/LMCS-7(2:20)2011.
- Wojciech Kazana and Luc Segoufin. Enumeration of first-order queries on classes of structures with bounded expansion. In Symp. on Principles of Database Systems (PODS), 2013. URL: http://dx.doi.org/10.1145/2463664.2463667.
- Wojciech Kazana and Luc Segoufin. Enumeration of monadic second-order queries on trees. ACM Trans. Comput. Log., 14(4), 2013. URL: http://dx.doi.org/10.1145/2528928.
- Stephan Kreutzer and Anuj Dawar. Parameterized complexity of first-order logic. Electronic Colloquium on Computational Complexity (ECCC), 16:131, 2009. URL: http://eccc.hpi-web.de/report/2009/131.
- Leonid Libkin. Elements of Finite Model Theory. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-662-07003-1.
- Jaroslav Nešetřil and Patrice Ossona de Mendez. On nowhere dense graphs. Eur. J. Comb., 32(4):600-617, 2011. URL: http://dx.doi.org/10.1016/j.ejc.2011.01.006.