Abstract
Constraint satisfaction techniques, embedded in constraint programming languages such as CHIP, have proven their worth or/ a wide variety of practical applications. This paper describes a first step towards integrating these techniques into database systems. The main idea is to optimise complex queries by continually checking to see if the current partial results are consistent with the remainder of the query. In this paper we present a query language, based on Datalog, which enables the database user to control the checking by annotating certain atomic goals. We show how queries expressed in this language can be translated into queries expressed in standard Datalog. Each Datalog rule is separately optimised by the database optimiser. The language and the translation are motivated by various examples; in particular an application to crossword generation is described where the optimisation proposed in this paper adds significantly to standard database optimisation techniques.
| Original language | English |
|---|---|
| Title of host publication | Constraint Databases and Applications - ESPRIT WG CONTESSA Workshop, 1995, Proceedings |
| Publisher | Springer-Verlag London Ltd. |
| Pages | 148-166 |
| Number of pages | 19 |
| ISBN (Print) | 3540607943, 9783540607946 |
| Publication status | Published - 1 Jan 1996 |
| Externally published | Yes |
| Event | Workshop on Constraint Databases and Applications, ESPRIT WG CONTESSA 1995 - Friedrichshafen, Germany Duration: 8 Sep 1995 → 9 Sep 1995 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 1034 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | Workshop on Constraint Databases and Applications, ESPRIT WG CONTESSA 1995 |
|---|---|
| Country | Germany |
| City | Friedrichshafen |
| Period | 8/09/95 → 9/09/95 |
Cite this
}
Magic checking : Constraint checking for database query optimisation. / Wallace, Mark; Bressan, Stephane; Provost, Thierry Le.
Constraint Databases and Applications - ESPRIT WG CONTESSA Workshop, 1995, Proceedings. Springer-Verlag London Ltd., 1996. p. 148-166 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1034).Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review
TY - GEN
T1 - Magic checking
T2 - Constraint checking for database query optimisation
AU - Wallace, Mark
AU - Bressan, Stephane
AU - Provost, Thierry Le
PY - 1996/1/1
Y1 - 1996/1/1
N2 - Constraint satisfaction techniques, embedded in constraint programming languages such as CHIP, have proven their worth or/ a wide variety of practical applications. This paper describes a first step towards integrating these techniques into database systems. The main idea is to optimise complex queries by continually checking to see if the current partial results are consistent with the remainder of the query. In this paper we present a query language, based on Datalog, which enables the database user to control the checking by annotating certain atomic goals. We show how queries expressed in this language can be translated into queries expressed in standard Datalog. Each Datalog rule is separately optimised by the database optimiser. The language and the translation are motivated by various examples; in particular an application to crossword generation is described where the optimisation proposed in this paper adds significantly to standard database optimisation techniques.
AB - Constraint satisfaction techniques, embedded in constraint programming languages such as CHIP, have proven their worth or/ a wide variety of practical applications. This paper describes a first step towards integrating these techniques into database systems. The main idea is to optimise complex queries by continually checking to see if the current partial results are consistent with the remainder of the query. In this paper we present a query language, based on Datalog, which enables the database user to control the checking by annotating certain atomic goals. We show how queries expressed in this language can be translated into queries expressed in standard Datalog. Each Datalog rule is separately optimised by the database optimiser. The language and the translation are motivated by various examples; in particular an application to crossword generation is described where the optimisation proposed in this paper adds significantly to standard database optimisation techniques.
UR - http://www.scopus.com/inward/record.url?scp=84947814860&partnerID=8YFLogxK
M3 - Conference Paper
AN - SCOPUS:84947814860
SN - 3540607943
SN - 9783540607946
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 148
EP - 166
BT - Constraint Databases and Applications - ESPRIT WG CONTESSA Workshop, 1995, Proceedings
PB - Springer-Verlag London Ltd.
ER -