×

Extended order-generic queries. (English) Zbl 0956.03035

The authors consider (finite) relational databases over an ordered domain \(U\) with some additional relations. They study first-order queries that are invariant under order-preserving partial functions, so-called locally generic queries. They introduce various model-theoretic conditions on the first-order theory \(\text{Th}(U)\) of \(U\) that ensure that every locally generic query is equivalent to a pure order query in models of \(\text{Th}(U)\). The homogeneity property and the stronger property of quasi-o-minimality are among these conditions; they have turned out to be interesting notions from the model-theoretic point of view. The authors show how the results can be generalized to finitely presented databases.

MSC:

03C13 Model theory of finite structures
68P15 Database theory
03C40 Interpolation, preservation, definability
03C50 Models with special properties (saturated, rigid, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baldwin, J. T.; Benedikt, M., Stability theory, permutations of indiscernibles, and embedded finite models (1997), Preprint
[2] Belegradek, O.; Peterzil, Y.; Wagner, F., Quasi-\(o\)-minimal structures (1997), Preprint
[3] Belegradek, O. V.; Stolboushkin, A. P.; Taitslin, M. A., On order-generic queries, (Technical report 96-01 (1996), DIMACS) · Zbl 0536.03015
[4] Belegradek, O. V.; Stolboushkin, A. P.; Taitslin, M. A., Generic queries over quasi-\(o\)-minimal domains, (Logical Foundation of Computer Science, Proc. 4th Internat. Symp., LFCS’97. Logical Foundation of Computer Science, Proc. 4th Internat. Symp., LFCS’97, Yaroslavl, Russia, July 1997. Logical Foundation of Computer Science, Proc. 4th Internat. Symp., LFCS’97. Logical Foundation of Computer Science, Proc. 4th Internat. Symp., LFCS’97, Yaroslavl, Russia, July 1997, Lecture Notes in Computer Science, vol. 1234 (1997), Springer: Springer Berlin), 21-32 · Zbl 0892.68026
[5] Benedikt, M.; Dong, G.; Libkin, L.; Wong, L., Relational expressive power of constraint query languages, (Proc. 15th ACM Symp. on Principles of Database Systems (1996)), 5-16
[6] Chandra, A.; Harel, D., Computable queries for relational databases, J. Comput. System Sci., 21, 156-178 (1980) · Zbl 0456.68128
[7] Chang, C. C.; Keisler, H. J., Model Theory (1990), North-Holland: North-Holland Amsterdam · Zbl 0697.03022
[8] Flum, J.; Ziegler, M., Pseudo-finite homogeneity and saturation (1997), Preprint
[9] Grumbach, S.; Su, J., Finitely representable databases, (Proc. 13th ACM Symp. on Principles of Database Systems (1994)) · Zbl 0887.68023
[10] Grumbach, S.; Su, J., Dense-order constraint databases, (Proc. 14th ACM Symp. on Principles of Database Systems (1995)), 66-77
[11] Grumbach, S.; Su, J.; Tollu, C., Linear constraint databases, (Proc. Logic and Computational Complexity (LCC’94). Proc. Logic and Computational Complexity (LCC’94), Lecture Notes in Computer Science (1995), Springer: Springer Berlin)
[12] Yu. Gurevich, Private communication, 1990.; Yu. Gurevich, Private communication, 1990.
[13] Hodges, W., Model Theory (1993), Cambridge University Press: Cambridge University Press Cambridge
[14] Kanellakis, P. C.; Goldin, D. Q., Constraint programming and database query languages, (Proc. Internat. Symp. on Theoretical Aspects of Computer Software (TACS’94) (1994)), 96-120 · Zbl 0942.68555
[15] Kanellakis, P. C.; Kuper, G. M.; Revesz, P. Z., Constraint query languages, (Proc. 9th ACM Symp. on Principles of Database Systems (1990)), 299-313
[16] Kanellakis, P. C.; Kuper, G. M.; Revesz, P. Z., Constraint query languages, J. Comput. System Sci., 51, 1, 26-52 (1995)
[17] Knight, J. F.; Pillay, A.; Steinhorn, C., Definable sets in ordered structures, II, Trans. Amer. Math. Soc., 295, 2, 593-605 (1986) · Zbl 0662.03024
[18] Otto, M.; Van den Bussche, J., First-order queries on databases embedded in an infinite structure, Inform. Process. Lett., 60, 37-41 (1996) · Zbl 0875.68356
[19] Paradaens, J.; Van den Bussche, J.; Van Gucht, D., Toward a theory of spatial database queries, (Proc. 13th ACM Symp. on Principles of Database Systems (1994), ACM Press: ACM Press New York), 279-288
[20] Paradaens, J.; Van den Bussche, J.; Van Gucht, D., First-order queries on finite structures over reals, (Proc. 10th IEEE Symp. on Logic in Computer Science (1995), IEEE Computer Society Press: IEEE Computer Society Press Silver Spring, MD), 79-87
[21] Pillay, A.; Steinhorn, C., Definable sets in ordered structures, I, Trans. Amer. Math. Soc., 295, 2, 565-592 (1986) · Zbl 0662.03023
[22] Pillay, A.; Steinhorn, C., Definable sets in ordered structures. III, Trans. Amer. Math. Soc, 309, 2, 469-476 (1988) · Zbl 0707.03024
[23] Robinson, J., Definability and decision problems in arithmetic, J. Symbolic Logic, 14, 98-114 (1949) · Zbl 0034.00801
[24] Rose, B. I.; Woodrow, R. E., Ultrahomogeneous structures, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 27, 1, 23-30 (1981) · Zbl 0481.03017
[25] Sacks, G. E., Saturated Model Theory (1972), Benjammin: Benjammin Reading, MA · Zbl 0242.02054
[26] Shelah, S., Classification Theory and the Number of Non-isomorphic Models (1990), North-Holland: North-Holland Amsterdam · Zbl 0713.03013
[27] Stolboushkin, A. P.; Taitslin, M. A., Linear vs. order constraint queries over rational databases, (Proc. 15th ACM Symp. on Principles of Database Systems (1996)), 17-27
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.