On problems of databases over a fixed infinite universe

Oleg Belegradek; Alexei Stolboushkin; Michael Taitslin

Banach Center Publications (1999)

  • Volume: 46, Issue: 1, page 23-62
  • ISSN: 0137-6934

Abstract

top
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 D a t a l o g ¬ , < z -programs do not have any effective syntax.

How to cite

top

Belegradek, Oleg, Stolboushkin, Alexei, and Taitslin, Michael. "On problems of databases over a fixed infinite universe." Banach Center Publications 46.1 (1999): 23-62. <http://eudml.org/doc/208923>.

@article{Belegradek1999,
abstract = {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.},
author = {Belegradek, Oleg, Stolboushkin, Alexei, Taitslin, Michael},
journal = {Banach Center Publications},
keywords = {relational database; infinite domain; recursive domain; decidable theory; state-safety problem; ordered domain; order queries; finitely representable database states},
language = {eng},
number = {1},
pages = {23-62},
title = {On problems of databases over a fixed infinite universe},
url = {http://eudml.org/doc/208923},
volume = {46},
year = {1999},
}

TY - JOUR
AU - Belegradek, Oleg
AU - Stolboushkin, Alexei
AU - Taitslin, Michael
TI - On problems of databases over a fixed infinite universe
JO - Banach Center Publications
PY - 1999
VL - 46
IS - 1
SP - 23
EP - 62
AB - 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.
LA - eng
KW - relational database; infinite domain; recursive domain; decidable theory; state-safety problem; ordered domain; order queries; finitely representable database states
UR - http://eudml.org/doc/208923
ER -

References

top
  1. [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. 
  2. [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. 
  3. [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. 
  4. [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. 
  5. [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. 
  6. [BST96] O. V. Belegradek, A. P. Stolboushkin, and M. A. Taitslin, phOn order-generic queries, Technical report 96-01, DIMACS, 1996. 
  7. [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. 
  8. [BST97b] O. V. Belegradek, A. P. Stolboushkin, and M. A. Taitslin, phGeneric queries over quasi-o-minimal domains, LFCS'97, 1997. Zbl0892.68026
  9. [CH80] A. Chandra and D. Harel, phComputable queries for relational databases, Journal of Computer and System Sciences 21 (1980), 156-178. 
  10. [CH82] A. Chandra and D. Harel, phStructure and complexity of relational queries, Journal of Computer and System Sciences 25 (1982), 99-128. Zbl0511.68073
  11. [CK90] C. C. Chang and H. J. Keisler, phModel theory, 3rd ed., North Holland, 1990. 
  12. [Cod70] E. F. Codd, phA relational model for large shared data banks, Communications of the ACM 13 (1970), 377-387. Zbl0207.18003
  13. [Cod72] E. F. Codd, phRelational completeness of data base sublanguages, Database Systems (R. Rustin, ed.), Prentice-Hall, 1972, pp. 33-64. 
  14. [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. Zbl0182.33202
  15. [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. 
  16. [End72] H. B. Enderton, phA mathematical introduction to logic, Academic Press, New York, 1972. 
  17. [GS94] S. Grumbach and J. Su, phFinitely representable databases, Proc. 13th ACM Symp. on Principles of Database Systems, 1994. 
  18. [GS95] S. Grumbach and J. Su, phDense-order constraint databases, Proc. 14th ACM Symp. on Principles of Database Systems, 1995, pp. 66-77. 
  19. [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. 
  20. [GST95] S. Grumbach, J. Su, and C. Tollu, phLinear constraint databases, Proc. Logic and Computational Complexity (LCC'94), LNCS, Springer-Verlag, 1995. 
  21. [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. 
  22. [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. 
  23. [Gur90] Yu. Gurevich, Private communication, 1990. 
  24. [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. 
  25. [JL87] J. Jaffar and J.-L. Lassez, phConstraint logic programming, Proc. 14th ACM Symp. on Principles of Programming Languages, 1987, pp. 111-119. 
  26. [JM94] J. Jaffar and M. J. Maher, phConstraint logic programming: A survey, Journal of Logic Programming 19-20 (1994), 503-581. 
  27. [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. 
  28. [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. 
  29. [Kif88] M. Kifer, phOn safety, domain independence, and capturability of database queries, Proc. Third International Conference on Data and Knowledge Bases, 1988. 
  30. [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. 
  31. [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. 
  32. [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. Zbl0662.03024
  33. [OV95] M. Otto and J. Van den Bussche, phFirst-order queries on databases embedded in an infinite structure, Manuscript, 1995. 
  34. [PS86] A. Pillay and C. Steinhorn, phDefinable sets in ordered structures, I, Transactions of American Mathematical Society 295 (1986), no. 2, 565-592. Zbl0662.03023
  35. [PS88] A. Pillay and C. Steinhorn, phDefinable sets in ordered structures, III, Transactions of American Mathematical Society 309 (1988), no. 2, 469-476. Zbl0707.03024
  36. [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. 
  37. [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. 
  38. [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. Zbl0789.68042
  39. [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. Zbl0785.68026
  40. [Rev95] P. Z. Revesz, phSafe stratified Datalog with integer order programs, Manuscript, August 1995. 
  41. [Rob49] Julia Robinson, phDefinability and decision problems in arithmetic, Journal of Symbolic Logic 14 (1949), 98-114. 
  42. [Rog67] H. Rogers, phTheory of recursive functions and effective computability, McGaw-Hill, 1967. 
  43. [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. 
  44. [Sac72] G. E. Sacks, phSaturated model theory, W.A. Benjammin, Inc., Reading, Massachusetts, 1972. 
  45. [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. 
  46. [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. 
  47. [ST95c] A. P. Stolboushkin and M. A. Taitslin, phSafe stratified datalog with integer order does not have syntax, Manuscript, October 1995. 
  48. [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. 
  49. [Ull82] J. D. Ullman, phPrinciples of database systems, 2 ed., Computer Science Press, 1982. 
  50. [Ull88] J. D. Ullman, phPrinciples of database and knowledge-base systems, volumes I and II, Computer Science Press, 1988. 
  51. [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. 
  52. [Var81] M. Y. Vardi, phThe decision problem for database dependencies, Information Processing Letters (1981), 251-254. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.