Abstract:
Constraint databases that can be described by boolean combinations of polynomial inequalities over the reals have received ample research attention. In particular, the expressive power of first - order logic over the reals, as a constraint database query language, has been studied extensively. The difficulty of the effective evaluation of first - order queries, usually involving some form of quantifier elimination, has been largely neglected. The contribution of this paper is a discussion of various aspects that influence the efficiency of the evaluation of queries expressible in first - order logic over the reals. We emphasize the importance of data structures and their effect on the complexity of quantifier-elimination. We also propose a novel data model that supports data exploration and visualization as well as efficient query evaluation. In this context, we introduce the concept of sample point query. Finally, we show that a particular kind of sample point query cannot be evaluated in polynomial sequential time by means of branching - parsimonious procedures. © Springer - Verlag 2004.
Registro:
Documento: |
Artículo
|
Título: | Constraint Databases, Data Structures and Efficient Query Evaluation |
Autor: | Heintz, J.; Kuijpers, B. |
Filiación: | Universitad de Buenos Aires, Departamento de Computación Ciudad Universitaria, Pabellón I, 1428 Buenos Aires, Argentina Consejo Nacional de Investigaciones Científicas y Tecnoĺgicas (CONICET), Argentina Universidad de Cantabria Facultad de Ciencias Departamento de Matemáticas, Estadística y Comptación, Avda. de los Castros s/n, E-39005 Santander, Spain Limburgs Universitair Centrum, Department WNI Universitaire Campus, 3590 Diepenbeek, Belgium
|
Palabras clave: | Data structures; Data visualization; Formal logic; Query languages; Boolean combinations; Constraint Databases; Data exploration; Efficient query evaluation; Expressive power; First order logic; Polynomial inequalities; Quantifier elimination; Query processing |
Año: | 2004
|
Volumen: | 3074
|
Página de inicio: | 1
|
Página de fin: | 24
|
Título revista: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
|
Título revista abreviado: | Lect. Notes Comput. Sci.
|
ISSN: | 03029743
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v3074_n_p1_Heintz |
Referencias:
- Atiyah, M.F., Macdonald, I.G., (1969) Introduction to Commutative Algebra, , AddisonWesley
- Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties, real equation solving and data structures: The hypersurface case (1997) Journal of Complexity, 13, pp. 5-27. , Best Paper Award Journal of Complexity 1997
- Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties and efficient real elimination (2001) Mathematische Zeitschrift, 238, pp. 115-144
- Bank, B., Giusti, M., Heintz, J., Pardo, L.M., Generalized polar varieties and an efficient real elimination procedure (2003) Submitted to Kibernetika
- Bank, B., Guddat, J., Klatte, D., Kummer, B., Tammer, K., (1983) Non - Linear Parametric Optimization, , Birkhauser Verlag, Basel
- Basu, S., Pollack, R., Roy, M.-F., On the combinatorial and algebraic complexity of quantifier elimination (1996) Journal of the ACM, 43, pp. 1002-1045
- Berkowitz, S., On computing the determinant in small parallel time using a small number of processors (1984) Information Processing Letters, 18, pp. 147-150
- Blum, L., Cucker, F., Shub, M., Smale, S., (1998) Complexity and Real Computation., , Springer-Verlag, New York
- Bochnak, J., Coste, M., Roy, M.-F., (1998) Real Algebraic Geometry, Volume 36 of Ergebenisse der Mathematik und Ihrer Grenzgebiete, 36. , Folge 3. Springer - Verlag
- Bürgisser, P., Clausen, M., Shokrollahi, M.A., (1997) Algebraic Complexity Theory, , Springer - Verlag
- Castro, D., Giusti, M., Heintz, J., Matera, G., Pardo, L.M., The hardness of polynomial solving (2003) Foundations of Computational Mathematics, 3, pp. 347-420
- Collins, G.E., Quantifier elimination for real closed fields by cylindrical algebraic decomposition (1975) Automata Theory and Formal Languages, Volume 33 of Lecture Notes in Computer Science, 33, pp. 134-183. , Springer - Verlag
- Giusti, M., Hägele, K., Heintz, J., Morais, J.E., Montaña, J.L., Pardo, L.M., Lower bounds for diophantine approximation (1997) Journal of Pure and Applied Algebra, 117-118, pp. 277-317
- Of Computational Mathematics, pp. 69-104. , M. Giusti and J. Heintz. Kronecker's smart, little black boxes. In R. DeVore, Iserles A., and E. Suli, editors, Foundations Cambridge, 2001. Cambridge University Press
- Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M., Straight - Line programs in geometric elimination theory (1998) Journal of Pure and Applied Algebra, 124, pp. 101-146
- Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M., Le rôle des structures des données dans les problèmes d'élimination (1997) Comptes Rendues de L'Académie des Sciences, 325, pp. 1223-1228
- Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) Journal of Complexity, 17 (1), pp. 154-211
- Grigor'Ev, D., Vorobjov, N.N., Solving systems of polynomial inequalities in subexponential time (1988) Journal of Symbolic Computation, 5, pp. 37-64
- Gyssens, M., Van Den Bussche, J., Van Gucht, D., Complete geometrical query languages (1999) Journal of Computer and System Sciences, 58 (3), pp. 483-511. , A preliminary report appeared in the Proceedings 16th ACM Symposium on Principles of Database Systems (PODS'97)
- Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) Journal of Complexity, 16, pp. 70-109
- Heintz, J., Matera, G., Weissbein, A., On the time-space complexity of geometric elimination procedures (2001) Applicable Algebra in Engineering, Communication and Computing, (4), pp. 239-296
- Heintz, J., Morgenstern, J., On the intrinsic complexity of elimination theory (1993) Journal of Complexity, 9, pp. 471-498
- Heintz, J., Roy, M.-F., Solernó, P., Sur la complexité du principe de TarskiSeidenberg (1990) Bulletin de la Société Mathématique de France, 118, pp. 101-126
- Jeronimo, G., Krick, T., Sabia, J., Sombra, M., The computational complexity of the Chow form (2004) Foundations of Computational Mathematics, 4, pp. 41-117
- Jeronimo, G., Sabia, J., On the number of sets definable by polynomials (2000) Journal Algebra, 227 (2), pp. 633-644
- Kanellakis, P.C., Kuper, G.M., Revesz, P.Z., Constraint query languages (1995) Journal of Computer and System Science, 51 (50), pp. 26-52. , A preliminary report appeared in the Proceedings 9th ACM Symposium on Principles of Database Systems (PODS'90)
- Krick, T., Pardo, L.M., Sombra, M., Sharp estimates for the arithmetic Nullstellensatz (2001) Duke Mathematical Journal, 109 (3), pp. 521-598
- Kuper, G.M., Paredaens, J., Libkin, L., (2000) Constraint Databases, , Springer-Verlag
- Lang, S., (1969) Algebra, , Addison-Wesley Publishing Company, Reading, Massachusetts
- Lecerf, G., Quadratic Newton iterations for systems with multiplicity (2002) Foundations of Computational Mathematics, 2, pp. 247-293
- Paredaens, J., Van Den Bussche, J., Van Gucht, D., Towards a theory of spatial database queries Proceedings of the 13th ACM Symposium on Principles of Database Systems (PODS'94), pp. 279-288. , New York, 1994. ACM Press
- Renegar, J., On the computational complexity and geometry of the first - Order theory of the reals I, II, III (1992) Jornal of Symbolic Computation, 13, pp. 255-352
- Revesz, P., (2002) Introduction to Constraint Databases, , Springer - Verlag
- Schost, E., Computing parametric geometric resolutions (2003) Applicable Algebra in Engineering, Communication and Computing, 13 (5), pp. 349-393
- Shavarevich, I.R., (1994) Basic Algebraic Geometry: Varieties in Projective Space, , Springer - Verlag
- Von Zur Gathen, J., Parallel linear algebra (1993) Synthesis of Parallel Algorithmns, pp. 573-617. , J. Reif, editor, Morgan - Kaufmann
Citas:
---------- APA ----------
Heintz, J. & Kuijpers, B.
(2004)
. Constraint Databases, Data Structures and Efficient Query Evaluation. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3074, 1-24.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v3074_n_p1_Heintz [ ]
---------- CHICAGO ----------
Heintz, J., Kuijpers, B.
"Constraint Databases, Data Structures and Efficient Query Evaluation"
. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3074
(2004) : 1-24.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v3074_n_p1_Heintz [ ]
---------- MLA ----------
Heintz, J., Kuijpers, B.
"Constraint Databases, Data Structures and Efficient Query Evaluation"
. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3074, 2004, pp. 1-24.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v3074_n_p1_Heintz [ ]
---------- VANCOUVER ----------
Heintz, J., Kuijpers, B. Constraint Databases, Data Structures and Efficient Query Evaluation. Lect. Notes Comput. Sci. 2004;3074:1-24.
Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v3074_n_p1_Heintz [ ]