Abstract
This paper investigates the complexity of query problem for first-order formulas on quasi-unary signatures, that is, on vocabularies made of a single unary function and any number of monadic predicates.
We first prove a form of quantifier elimination result: any query defined by a quasi-unary first-order formula can be equivalently defined, up to a suitable linear-time reduction, by a quantifier-free formula. We then strengthen this result by showing that first-order queries on quasi-unary signatures can be computed with constant delay i.e. by an algorithm that has a precomputation part whose complexity is linear in the size of the structure followed by an enumeration of all solutions (i.e. the tuples that satisfy the formula) with a constant delay (i.e. depending on the formula size only) between each solution. Among other things, this reproves (see[7]) that such queries can be computed in total time f(|φ|).(|S|+|φ(S)|) where S is the structure, φ is the formula, φ(S) is the result of the query and f is some fixed function.
The main method of this paper involves basic combinatorics and can be easily automatized. Also, since a forest of (colored) unranked tree is a quasi-unary structure, all our results apply immediately to queries over that later kind of structures.
Finally, we investigate the special case of conjunctive queries over quasi-unary structures and show that their combined complexity is not prohibitive, even from a dynamical (enumeration) point of view.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bagan, G.: MSO queries on tree decomposable structures are computable with linear delay. In: Ésik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 167–181. Springer, Heidelberg (2006)
Courcelle, B.: Linear delay enumeration and monadic second-order logic (submitted, 2006)
Durand, A., Fagin, R., Loescher, B.: Spectra with only unary function symbols. In: Nielsen, M., Thomas, W. (eds.) CSL 1997. LNCS, vol. 1414, pp. 111–126. Springer, Heidelberg (1998)
Durand, A., Grandjean, E.: The complexity of acyclic conjunctive queries revisited. Draft (2005)
Durand, A., Grandjean, E.: First-order queries on structures of bounded degree are computable with constant delay. ACM Transactions on Computational Logic (to appear, 2006)
Durand, A., Grandjean, E., Olive, F.: New results on arity vs. number of variables. Research report 20-2004, LIF, Marseille, France (April 2004)
Flum, J., Frick, M., Grohe, M.: Query evaluation via tree decompositions. Journal of the ACM 49(6), 716–752 (2002)
Frick, M., Grohe, M.: Deciding first-order properties of locally tree decomposable structures. Journal of the ACM 48, 1184–1206 (2001)
Gurevich, Y.: The decision problem for standard classes. J. Symb. Logic 41(2), 460–464 (1976)
Gurevich, Y., Shelah, S.: On spectra of one unary function. In: 18th IEEE Conference in Logic in Computer Science, pp. 291–300. IEEE Computer Society Press, Los Alamitos (2003)
Libkin, L.: Elements of finite model theory. EATCS Series. Springer, Heidelberg (2004)
Lindell, S.: A normal form for first-order logic over doubly-linked data structures (submitted, 2006)
Papadimitriou, C., Yannakakis, M.: On the complexity of database queries. Journal of Computer and System Sciences 58(3), 407–427 (1999)
Seese, D.: Linear time computable problems and first-order descriptions. Mathematical Structures in Computer Science 6(6), 505–526 (1996)
Vardi, M.Y.: On the complexity of bounded-variable queries. In: ACM Symposium on Principles of Database Systems, pp. 266–276. ACM Press, New York (1995)
Yannakakis, M.: Algorithms for acyclic database schemes. In: Proceedings of the 7th International Conference on Very Large Databases, pp. 82–94 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Durand, A., Olive, F. (2006). First-Order Queries over One Unary Function. In: Ésik, Z. (eds) Computer Science Logic. CSL 2006. Lecture Notes in Computer Science, vol 4207. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11874683_22
Download citation
DOI: https://doi.org/10.1007/11874683_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-45458-8
Online ISBN: 978-3-540-45459-5
eBook Packages: Computer ScienceComputer Science (R0)