zbMATH — the first resource for mathematics

Queries with arithmetical constraints. (English) Zbl 0902.68044
Summary: In this paper, we study the expressive power and the complexity of first-order logic with arithmetic, as a query language over relational and constraint databases. We consider constraints over various domains $$({\mathbb{N}}$$, $${\mathbb{Z}}$$, $${\mathbb{Q}}$$, and $${\mathbb{R}})$$, and with various arithmetical operations $$(<,+,\times$$, etc.). We first consider the data complexity of first-order queries. We prove in particular that linear queries can be evaluated in AC$$^{0}$$ over finite integer databases, and in NC over linear constraint databases. This improves previously known bounds. We also show that over all domains, enough arithmetic lead to arithmetical queries, therefore, showing the frontiers of constraints for database purposes. We then tackle the problem of the expressive power, with the definability of the parity and the connectivity, which are the most classical examples of queries not expressible in first-order logic over finite structures. We prove that these two queries are first-order definable in the presence of (enough) arithmetic. Nevertheless, we show that they are not definable with constraints of interest for constraint databases such as linear constraints for instance. Finally, we develop reduction techniques for queries over constraint databases, that allow us to draw conclusions with respect to their undefinability in various constraint query languages.

MSC:
 68P15 Database theory
Keywords:
first-order logic; query language
Full Text:
References:
 [1] Abiteboul, S.; Hull, R.; Vianu, V., Foundations of databases, (1995), Addison-Wesley Reading, MA [2] Afrati, F.; Cosmadakis, S.; Grumbach, S.; Kuper, G., Expressiveness of linear vs. polynomial constraints in database query languages, () [3] Benedikt, M.; Dong, G.; Libkin, L.; Wong, L., Relational expressive power of constraint query languages, (1995), manuscript [4] Benedikt, M.; Libkin, L., On the structure of queries in constraint query languages, () [5] Ben-Or, M.; Kozen, D.; Reif, J., The complexity of elementary algebra and geometry, J. comput. system sci., 32, 2, 251-264, (1986) · Zbl 0634.03031 [6] Blum, L.; Shub, M.; Smale, S., On a theory of computation and complexity over the real numbers, Bull. amer. math. soc., 21, 1-46, (1989) · Zbl 0681.03020 [7] Chandra, A.K.; Harel, D., Computable queries for relational data bases, J. comput. system. sci., 21, 156-178, (1980) · Zbl 0456.68128 [8] Chandra, A.K.; Harel, D., Structure and complexity of relational queries, J. comput. system sci., 25, 99-128, (1982) · Zbl 0511.68073 [9] Chandra, A.K.; Stockmeyer, L.; Vishkin, U., Constant depth reducibility, SIAM J. comput., 13, 423-439, (1984) · Zbl 0538.68038 [10] Chang, C.C.; Keisler, H.J., Model theory, () · Zbl 0697.03022 [11] Chomicki, J.; Kuper, G., Measuring infinite relations, () [12] Codd, E.F., A relational model of data for large shared data banks, Comm. ACM, 13, 377-387, (1970) · Zbl 0207.18003 [13] Collins, G.E., Quantifier elimination for real closed fields by cylindric decompositions, (), 134-183 [14] Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fund. math., 49, (1961) · Zbl 0096.24303 [15] Enderton, H.B., A mathematical introduction to logic, (1972), Academic Press New York · Zbl 0298.02002 [16] Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, (), 43-73 [17] Fagin, R., Probabilities on finite models, J. symbol. logic, 41, 50-58, (1976) · Zbl 0341.02044 [18] Fagin, R., Finite model theory — a personal perspective, Theoret. comput. sci., 116, 3-31, (1993) · Zbl 0788.03037 [19] Ferrante, J.; Rackoff, C.W., The computational complexity of logical theories, () · Zbl 0404.03028 [20] Fraïssé, R., Sur LES classifications des systèmes de relations, publ. sci. univ. alger.{\bfi}, 1, (1954) [21] Furst, M.; Saxe, J.B.; Sipser, M., Parity, circuits, and polynomial-time hierarchy, Math. system theory, 17, 13-27, (1984) · Zbl 0534.94008 [22] Gaifman, H., On local and nonlocal properties, (), 105-135 [23] Grädel, E.; Gurevich, Y., Metafinite model theory, () · Zbl 0892.68033 [24] Grädel, E.; Meer, K., Descriptive complexity theory over the real numbers, () · Zbl 0968.68517 [25] Grumbach, S.; Lacroix, Z., Computing queries on linear constraint databases, () [26] Grumbach, S.; Su, J., Finitely representable databases (extended abstract), () · Zbl 0887.68023 [27] Grumbach, S.; Su, J., Dense order constraint databases, () [28] Grumbach, S.; Su, J.; Tollu, C., Linear constraint query languages: expressive power and complexity, () [29] Gurevich, Y., Logic and the challenge of computer science, (), 1-57 [30] Hull, R., Relative information capacity of simple relational schemata, SIAM J. comput., 15, 856-886, (1986) · Zbl 0612.68085 [31] Immerman, N., Languages that capture complexity classes, SIAM J. comput., 16, 760-778, (1987) · Zbl 0634.68034 [32] Johnson, D.S., A catalog of complexity classes, (), 67-162, Ch. 2 · Zbl 0900.68246 [33] Kanellakis, P.C.; Goldin, D.Q., Constraint programming and database query languages, () · Zbl 0942.68555 [34] Kanellakis, P.; Kuper, G.; Revesz, P., Constraint query languages, (), 299-313 [35] Karp, R.; Ramachandran, V., Parallel algorithms for shared memory machines, (), 869-941 · Zbl 0900.68267 [36] Ko, Ker-I; Weihrauch, K., Computability and complexity in analysis, () · Zbl 0919.00028 [37] Kuper, G.M., Aggregation in constraint databases, (), 176-183 [38] Paredaens, J.; Van den Bussche, J.; Van Gucht, D., Towards a theory of spatial database queries, (), 279-288 [39] Paredaens, J.; Van den Bussche, J.; Van Gucht, D., First-order queries on finite structures over the reals, () · Zbl 0907.68062 [40] Presburger, M., Über die vollständigkeit eines gewissen systems der arithmetik ganzer zahlen, in welchem die addition als einzige operation hervortrit, (), 92-101 · JFM 56.0825.04 [41] Renegar, J., On the computational complexity and geometry of the first-order theory of the real, J. symbol. comput., 13, 255-352, (1992) · Zbl 0798.68073 [42] Revesz, P.Z., A closed form for Datalog queries with integer (gap)-order constraints, Theoret. comput. sci., 116, 117-149, (1993) · Zbl 0785.68026 [43] Revesz, P., Datalog queries over set constraint databases, () [44] Robinson, J., Decidability and decision problems in arithmetic, J. symbol. logic, 14, 98-114, (1949) · Zbl 0034.00801 [45] Schönhage, A.; Strassen, V., Schnelle multiplikation grosser zahlen, Comp., 7, 281-292, (1971) · Zbl 0223.68007 [46] Schrijver, A., Theory of linear and integer programming, (1986), Wiley New York · Zbl 0665.90063 [47] Tarski, A., A decision method for elementary algebra and geometry, (1951), University of California Press Berkeley, California · Zbl 0044.25102 [48] Trakhtenbrot, B.A., The impossibility of an algorithm for the decision problem for finite models, Doklady akademii nauk SSR, 70, 569-572, (1950) · Zbl 0038.15001 [49] Ullman, J.D., () [50] Van den Dries, L., Remarks on Tarski’s problem concerning (r, +, ×, exp), () · Zbl 0585.03006 [51] Yao, F.F., Computational geometry, (), 343-389, Ch. 7 · Zbl 0900.68254
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.