Efficient evaluation of specific queries in constraint databases
Let F1,...,FsεR[X1,...,Xn] be polynomials of degree at most d, and suppose that F1,...,F s are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of Rn defined by F 1,...,Fs. For any point xεRn, we consider the task of determining the signs of...
Guardado en:
| Publicado: |
2011
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v111_n19_p941_GrimsOn http://hdl.handle.net/20.500.12110/paper_00200190_v111_n19_p941_GrimsOn |
| Aporte de: |
| id |
paper:paper_00200190_v111_n19_p941_GrimsOn |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_00200190_v111_n19_p941_GrimsOn2023-06-08T14:40:20Z Efficient evaluation of specific queries in constraint databases Computational complexity Constraint databases Query evaluation Arithmetic circuit Arithmetic operations Connected component Constraint Databases Genericity Keypoints Mutatis-mutandis Point location Query evaluation Sign conditions Upper Bound Polynomials Database systems Let F1,...,FsεR[X1,...,Xn] be polynomials of degree at most d, and suppose that F1,...,F s are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of Rn defined by F 1,...,Fs. For any point xεRn, we consider the task of determining the signs of the values F1(x),...,F s(x) (sign condition query) and the task of determining the connected component of A to which x belongs (point location query). By an extremely simple reduction to the well-known case where the polynomials F 1,...,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size sO(L+n) which allows the evaluation of the sign condition query using only (Ln)O(1)log(s) arithmetic operations. The key point of this paper is the proof that this upper bound is almost optimal. By the way, we show that the point location query can be evaluated using dO(n)log(s) arithmetic operations. Based on a different argument, analogous complexity upper-bounds are exhibited with respect to the bit-model in case that F 1,...,Fs belong to Z[X1,...,Xn] and satisfy a certain natural genericity condition. Mutatis mutandis our upper-bound results may be applied to the sparse and dense representations of F 1,...,Fs. © 2011 Elsevier B.V. All rights reserved. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v111_n19_p941_GrimsOn http://hdl.handle.net/20.500.12110/paper_00200190_v111_n19_p941_GrimsOn |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Computational complexity Constraint databases Query evaluation Arithmetic circuit Arithmetic operations Connected component Constraint Databases Genericity Keypoints Mutatis-mutandis Point location Query evaluation Sign conditions Upper Bound Polynomials Database systems |
| spellingShingle |
Computational complexity Constraint databases Query evaluation Arithmetic circuit Arithmetic operations Connected component Constraint Databases Genericity Keypoints Mutatis-mutandis Point location Query evaluation Sign conditions Upper Bound Polynomials Database systems Efficient evaluation of specific queries in constraint databases |
| topic_facet |
Computational complexity Constraint databases Query evaluation Arithmetic circuit Arithmetic operations Connected component Constraint Databases Genericity Keypoints Mutatis-mutandis Point location Query evaluation Sign conditions Upper Bound Polynomials Database systems |
| description |
Let F1,...,FsεR[X1,...,Xn] be polynomials of degree at most d, and suppose that F1,...,F s are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of Rn defined by F 1,...,Fs. For any point xεRn, we consider the task of determining the signs of the values F1(x),...,F s(x) (sign condition query) and the task of determining the connected component of A to which x belongs (point location query). By an extremely simple reduction to the well-known case where the polynomials F 1,...,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size sO(L+n) which allows the evaluation of the sign condition query using only (Ln)O(1)log(s) arithmetic operations. The key point of this paper is the proof that this upper bound is almost optimal. By the way, we show that the point location query can be evaluated using dO(n)log(s) arithmetic operations. Based on a different argument, analogous complexity upper-bounds are exhibited with respect to the bit-model in case that F 1,...,Fs belong to Z[X1,...,Xn] and satisfy a certain natural genericity condition. Mutatis mutandis our upper-bound results may be applied to the sparse and dense representations of F 1,...,Fs. © 2011 Elsevier B.V. All rights reserved. |
| title |
Efficient evaluation of specific queries in constraint databases |
| title_short |
Efficient evaluation of specific queries in constraint databases |
| title_full |
Efficient evaluation of specific queries in constraint databases |
| title_fullStr |
Efficient evaluation of specific queries in constraint databases |
| title_full_unstemmed |
Efficient evaluation of specific queries in constraint databases |
| title_sort |
efficient evaluation of specific queries in constraint databases |
| publishDate |
2011 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v111_n19_p941_GrimsOn http://hdl.handle.net/20.500.12110/paper_00200190_v111_n19_p941_GrimsOn |
| _version_ |
1768542922479763456 |