Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 30-45 |
| Seitenumfang | 16 |
| Fachzeitschrift | Lecture Notes in Computer Science |
| Jahrgang | 3542 |
| Publikationsstatus | Veröffentlicht - 2005 |
| Veranstaltung | 7th International Conference on Theory and Applications of Satisfiability Testing, SAT 2004 - Vancouver, BC, Kanada Dauer: 10 Mai 2004 → 13 Mai 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 Sachgebiete
- Mathematik (insg.)
- Theoretische Informatik
- Informatik (insg.)
- Allgemeine Computerwissenschaft
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: Lecture Notes in Computer Science, Jahrgang 3542, 2005, S. 30-45.
Publikation: Beitrag in Fachzeitschrift › Konferenzaufsatz in Fachzeitschrift › Forschung › 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 -