On problems of databases over a fixed infinite universe

Belegradek, Oleg ; Stolboushkin, Alexei ; Taitslin, Michael

Banach Center Publications, Tome 50 (1999), p. 23-62 / Harvested from The Polish Digital Mathematics Library

Résumé

In the relational model of databases a database state is thought of as a finite collection of relations between elements. For many applications it is convenient to pre-fix an infinite domain where the finite relations are going to be defined. Often, we also fix a set of domain functions and/or relations. These functions/relations are infinite by their nature. Some special problems arise if we use such an approach. In the paper we discuss some of the problems. We show that there exists a recursive domain with decidable theory in which (1) there is no recursive syntax for finite queries, and in which (2) the state-safety problem is undecidable. We provide very general conditions on the FO theory of an ordered domain that ensure collapse of order-generic extended FO queries to pure order queries over this domain: the Pseudo-finite Homogeneity Property and a stronger Isolation Property. We further distinguish one broad class of ordered domains satisfying the Isolation Property, the so-called quasi-o-minimal domains. This class includes all o-minimal domains, but also the ordered group of integer numbers and the ordered semigroup of natural numbers, and some other domains. We generalize all the notions to the case of finitely representable database states - as opposed to finite states - and develop a general lifting technique that, essentially, allows us to extend any result of the kind we are interested in, from finite to finitely-representable states. We show, however, that these results cannot be transferred to arbitrary infinite states. We prove that safe $Datalog^{¬,<_z}$-programs do not have any effective syntax.

Détail

Publié le : 1999-01-01

Zbl 0978.68056

EUDML-ID : urn:eudml:doc:208923

Bibliographie

[000] [AGSS86] A. K. Ailamazian, M. M. Gilula, A. P. Stolboushkin, and G. F. Schwarz, phReduction of the relational model with infinite domains to the case of finite domains, Doklady Akademii nauk SSSR 286 (1986), no. 2, 308-311, Russian.

[001] [AH91] A. Avron and J. Hirshfeld, phOn first order database query languages, Proc. 6th IEEE Symp. on Logic in Computer Science, 1991, pp. 226-231.

[002] [AU79] A. V. Aho and J. D. Ullman, phUniversality of data retrieval languages, Proc. 6th ACM Symp. on Principles of Programming Languages, 1979, pp. 110-117.

[003] [BDLW96] M. Benedikt, G. Dong, L. Libkin, and L. Wong, phRelational expressive power of constraint query languages, Proc. 15th ACM Symp. on Principles of Database Systems, 1996, pp. 5-16.

[004] [BL96] M. Benedikt and L. Libkin, phOn the structure of queries in constraint query languages, Proc. 11th IEEE Symp. on Logic in Computer Science (Los Alamitos, CA), IEEE Computer Society Press, 1996.

[005] [BST96] O. V. Belegradek, A. P. Stolboushkin, and M. A. Taitslin, phOn order-generic queries, Technical report 96-01, DIMACS, 1996.

[006] [BST97a] O. V. Belegradek, A. P. Stolboushkin, and M. A. Taitslin, phExtended order-generic queries, Tver University, manuscript submitted to Annals of Pure and Applied Logic, 1997.

[007] [BST97b] O. V. Belegradek, A. P. Stolboushkin, and M. A. Taitslin, phGeneric queries over quasi-o-minimal domains, LFCS'97, 1997. | Zbl 0892.68026

[008] [CH80] A. Chandra and D. Harel, phComputable queries for relational databases, Journal of Computer and System Sciences 21 (1980), 156-178.

[009] [CH82] A. Chandra and D. Harel, phStructure and complexity of relational queries, Journal of Computer and System Sciences 25 (1982), 99-128. | Zbl 0511.68073

[010] [CK90] C. C. Chang and H. J. Keisler, phModel theory, 3rd ed., North Holland, 1990.

[011] [Cod70] E. F. Codd, phA relational model for large shared data banks, Communications of the ACM 13 (1970), 377-387. | Zbl 0207.18003

[012] [Cod72] E. F. Codd, phRelational completeness of data base sublanguages, Database Systems (R. Rustin, ed.), Prentice-Hall, 1972, pp. 33-64.

[013] [Di69] R. A. Di Paola, phThe recursive unsolvability of the decision problem for the class of definite formulas, Journal of the ACM 16 (1969), no. 2, 324-327. | Zbl 0182.33202

[014] [ELTT65] Yu. L. Ershov, I. A. Lavrov, A. D. Taimanov, and M. A. Taitslin, phElementary theories, Russian Mathematical Surveys 20 (1965), no. 4, 35-105.

[015] [End72] H. B. Enderton, phA mathematical introduction to logic, Academic Press, New York, 1972.

[016] [GS94] S. Grumbach and J. Su, phFinitely representable databases, Proc. 13th ACM Symp. on Principles of Database Systems, 1994.

[017] [GS95] S. Grumbach and J. Su, phDense-order constraint databases, Proc. 14th ACM Symp. on Principles of Database Systems, 1995, pp. 66-77.

[018] [GSSS86] M. M. Gilula, A. P. Stolboushkin, G. F. Schwarz, and K. V. Shvachko, phSome algorithmic problems in the theory of relational databases, Problem-Oriented Computational Systems (Moscow, USSR) (A.K. Ailamazian, ed.), Problems in Cybernetics, vol. 125, USSR Academy of Sciences, Moscow, USSR, 1986, Russian, pp. 81-91.

[019] [GST95] S. Grumbach, J. Su, and C. Tollu, phLinear constraint databases, Proc. Logic and Computational Complexity (LCC'94), LNCS, Springer-Verlag, 1995.

[020] [GT91] S. Grumbach and C. Tollu, phThe generic complexity of query languages with counters, Proceedings of 3rd Workshop on Foundations of Models and Languages for Data and Objects,Aigen (Austria), 1991.

[021] [Gur88] Y. Gurevich, phLogic and the challenge of computer science, Current trends in theoretical computer science (E. Börger, ed.), Computer Science Press, 1988, pp. 1-57.

[022] [Gur90] Yu. Gurevich, Private communication, 1990.

[023] [Hir91] J. Hirshfeld, phSafe queries in relational databases with functions, CSL '91: 5th Workshop on Computer Science Logic, LNCS, Springer-Verlag, 1991, pp. 173-183.

[024] [JL87] J. Jaffar and J.-L. Lassez, phConstraint logic programming, Proc. 14th ACM Symp. on Principles of Programming Languages, 1987, pp. 111-119.

[025] [JM94] J. Jaffar and M. J. Maher, phConstraint logic programming: A survey, Journal of Logic Programming 19-20 (1994), 503-581.

[026] [Kan88] P. C. Kanellakis, phLogic programming and parallel complexity, Foundations of Deductive Databases and Logic Programming (J. Minker, ed.), Morgan Kaufmann, 1988, pp. 547-586.

[027] [KG94] P. C. Kanellakis and D. Q. Goldin, phConstraint programming and database query languages, Proc. International Symposium on Theoretical Aspects of Computer Software (TACS'94), 1994, pp. 96-120.

[028] [Kif88] M. Kifer, phOn safety, domain independence, and capturability of database queries, Proc. Third International Conference on Data and Knowledge Bases, 1988.

[029] [KKR90] P. C. Kanellakis, G. M. Kuper, and P. Z. Revesz, phConstraint query languages, Proc. 9th ACM Symp. on Principles of Database Systems, 1990, pp. 299-313.

[030] [KKR95] P. C. Kanellakis, G. M. Kuper, and P. Z. Revesz, phConstraint query languages, Journal of Computer and System Sciences 51 (1995), no. 1, 26-52.

[031] [KPS86] J. F. Knight, A. Pillay, and C. Steinhorn, phDefinable sets in ordered structures, II, Transactions of American Mathematical Society 295 (1986), no. 2, 593-605. | Zbl 0662.03024

[032] [OV95] M. Otto and J. Van den Bussche, phFirst-order queries on databases embedded in an infinite structure, Manuscript, 1995.

[033] [PS86] A. Pillay and C. Steinhorn, phDefinable sets in ordered structures, I, Transactions of American Mathematical Society 295 (1986), no. 2, 565-592. | Zbl 0662.03023

[034] [PS88] A. Pillay and C. Steinhorn, phDefinable sets in ordered structures, III, Transactions of American Mathematical Society 309 (1988), no. 2, 469-476. | Zbl 0707.03024

[035] [PVV95] J. Paradaens, J. Van den Bussche, and D. Van Gucht, phFirst-order queries on finite structures over reals, Proc. 10th IEEE Symp. on Logic in Computer Science, IEEE Computer Society Press, 1995, pp. 79-87.

[036] [Rab77] M. O. Rabin, phDecidable theories, Handbook of Mathematical Logic (Amsterdam, New York, Oxford) (J. Barwise, ed.), vol. 3, North-Holland, Amsterdam, New York, Oxford, 1977.

[037] [Rev90] P. Z. Revesz, phA closed form for Datalog queries with integer order, 3rd Int'l. Conf. on Database Theory, Springer-Verlag, 1990, pp. 187-201. | Zbl 0789.68042

[038] [Rev93] P. Z. Revesz, phA closed form evaluation for Datalog queries with integer (gap)-order constraints, Theoretical Computer Science 116 (1993), no. 1, 117-149. | Zbl 0785.68026

[039] [Rev95] P. Z. Revesz, phSafe stratified Datalog with integer order programs, Manuscript, August 1995.

[040] [Rob49] Julia Robinson, phDefinability and decision problems in arithmetic, Journal of Symbolic Logic 14 (1949), 98-114.

[041] [Rog67] H. Rogers, phTheory of recursive functions and effective computability, McGaw-Hill, 1967.

[042] [RW81] B. I. Rose and R. E. Woodrow, phUltrahomogeneous structures, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 27 (1981), no. 1, 23-30.

[043] [Sac72] G. E. Sacks, phSaturated model theory, W.A. Benjammin, Inc., Reading, Massachusetts, 1972.

[044] [ST95a] A. P. Stolboushkin and M. A. Taitslin, phFinite queries do not have effective syntax, Proc. 14th ACM Symp. on Principles of Database Systems, 1995, pp. 277-285.

[045] [ST95b] A. P. Stolboushkin and M. A. Taitslin, phIs first order contained in an initial segment of PTIME?, Selected Papers, 8th EATCS Conference on Computer Science Logic (CSL'94), LNCS, vol. 933, Springer-Verlag, 1995, pp. 242-248.

[046] [ST95c] A. P. Stolboushkin and M. A. Taitslin, phSafe stratified datalog with integer order does not have syntax, Manuscript, October 1995.

[047] [ST96] A. P. Stolboushkin and M. A. Taitslin, phLinear vs. order constraint queries over rational databases, Proc. 15th ACM Symp. on Principles of Database Systems, 1996, pp. 17-27.

[048] [Ull82] J. D. Ullman, phPrinciples of database systems, 2 ed., Computer Science Press, 1982.

[049] [Ull88] J. D. Ullman, phPrinciples of database and knowledge-base systems, volumes I and II, Computer Science Press, 1988.

[050] [Van91] A. Van Gelder and R. W. Topor, phSafety and translation of relational calculus queries, ACM Trans. on Database Systems 16 (1991), no. 2, 235-278.

[051] [Var81] M. Y. Vardi, phThe decision problem for database dependencies, Information Processing Letters (1981), 251-254.