Constraint Databases, Data Structures and Efficient Query Evaluation

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 d...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Heintz, J., Kuijpers, B.
Formato:	SER
Materias:	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
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_03029743_v3074_n_p1_Heintz
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_03029743_v3074_n_p1_Heintz
record_format	dspace
spelling	todo:paper_03029743_v3074_n_p1_Heintz2023-10-03T15:18:54Z Constraint Databases, Data Structures and Efficient Query Evaluation Heintz, J. Kuijpers, B. 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 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. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03029743_v3074_n_p1_Heintz
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	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
spellingShingle	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 Heintz, J. Kuijpers, B. Constraint Databases, Data Structures and Efficient Query Evaluation
topic_facet	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
description	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.
format	SER
author	Heintz, J. Kuijpers, B.
author_facet	Heintz, J. Kuijpers, B.
author_sort	Heintz, J.
title	Constraint Databases, Data Structures and Efficient Query Evaluation
title_short	Constraint Databases, Data Structures and Efficient Query Evaluation
title_full	Constraint Databases, Data Structures and Efficient Query Evaluation
title_fullStr	Constraint Databases, Data Structures and Efficient Query Evaluation
title_full_unstemmed	Constraint Databases, Data Structures and Efficient Query Evaluation
title_sort	constraint databases, data structures and efficient query evaluation
url	http://hdl.handle.net/20.500.12110/paper_03029743_v3074_n_p1_Heintz
work_keys_str_mv	AT heintzj constraintdatabasesdatastructuresandefficientqueryevaluation AT kuijpersb constraintdatabasesdatastructuresandefficientqueryevaluation
_version_	1807320521943023616

Constraint Databases, Data Structures and Efficient Query Evaluation

Ejemplares similares