Details
| Original language | English |
|---|---|
| Pages (from-to) | 30-45 |
| Number of pages | 16 |
| Journal | Lecture Notes in Computer Science |
| Volume | 3542 |
| Publication status | Published - 2005 |
| Event | 7th International Conference on Theory and Applications of Satisfiability Testing, SAT 2004 - Vancouver, BC, Canada Duration: 10 May 2004 → 13 May 2004 |
Abstract
Conjunctive-query containment is considered as a fundamental problem in database query evaluation and optimization. Kolaitis and Vardi pointed out that constraint satisfaction and conjunctive query containment are essentially the same problem. We study the Boolean conjunctive queries under a more detailed scope, where we investigate their counting problem by means of the algebraic approach through Galois theory, taking advantage of Post's lattice. We prove a trichotomy theorem for the generalized conjunctive query counting problem, showing this way that, contrary to the corresponding decision problems, constraint satisfaction and conjunctive-query containment differ for other computational goals. We also study the audit problem for conjunctive queries asking whether there exists a frozen variable in a given query. This problem is important in databases supporting statistical queries. We derive a dichotomy theorem for this audit problem that sheds more light on audit applicability within database systems.
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
- General Computer Science
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Lecture Notes in Computer Science, Vol. 3542, 2005, p. 30-45.
Research output: Contribution to journal › Conference article › Research › peer review
}
TY - JOUR
T1 - An algebraic approach to the complexity of generalized conjunctive queries
AU - Bauland, Michael
AU - Chapdelaine, Philippe
AU - Creignou, Nadia
AU - Hermann, Miki
AU - Vollmer, Heribert
PY - 2005
Y1 - 2005
N2 - Conjunctive-query containment is considered as a fundamental problem in database query evaluation and optimization. Kolaitis and Vardi pointed out that constraint satisfaction and conjunctive query containment are essentially the same problem. We study the Boolean conjunctive queries under a more detailed scope, where we investigate their counting problem by means of the algebraic approach through Galois theory, taking advantage of Post's lattice. We prove a trichotomy theorem for the generalized conjunctive query counting problem, showing this way that, contrary to the corresponding decision problems, constraint satisfaction and conjunctive-query containment differ for other computational goals. We also study the audit problem for conjunctive queries asking whether there exists a frozen variable in a given query. This problem is important in databases supporting statistical queries. We derive a dichotomy theorem for this audit problem that sheds more light on audit applicability within database systems.
AB - Conjunctive-query containment is considered as a fundamental problem in database query evaluation and optimization. Kolaitis and Vardi pointed out that constraint satisfaction and conjunctive query containment are essentially the same problem. We study the Boolean conjunctive queries under a more detailed scope, where we investigate their counting problem by means of the algebraic approach through Galois theory, taking advantage of Post's lattice. We prove a trichotomy theorem for the generalized conjunctive query counting problem, showing this way that, contrary to the corresponding decision problems, constraint satisfaction and conjunctive-query containment differ for other computational goals. We also study the audit problem for conjunctive queries asking whether there exists a frozen variable in a given query. This problem is important in databases supporting statistical queries. We derive a dichotomy theorem for this audit problem that sheds more light on audit applicability within database systems.
UR - http://www.scopus.com/inward/record.url?scp=26444620122&partnerID=8YFLogxK
U2 - 10.1007/11527695_3
DO - 10.1007/11527695_3
M3 - Conference article
AN - SCOPUS:26444620122
VL - 3542
SP - 30
EP - 45
JO - Lecture Notes in Computer Science
JF - Lecture Notes in Computer Science
SN - 0302-9743
T2 - 7th International Conference on Theory and Applications of Satisfiability Testing, SAT 2004
Y2 - 10 May 2004 through 13 May 2004
ER -