Navegar

Colección

Datos Estadísticas

Artículo

Heintz, J.; Kuijpers, B. "Constraint Databases, Data Structures and Efficient Query Evaluation" (2004) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 3074:1-24
El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte la política de Acceso Abierto del editor

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 [ ]