Magic checking: Constraint checking for database query optimisation

Mark Wallace; Stephane Bressan; Thierry Le Provost

Magic checking: Constraint checking for database query optimisation

Mark Wallace, Stephane Bressan, Thierry Le Provost

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

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

Access to Document

Link to publication in Scopus

Cite this

Wallace, M., Bressan, S., & Provost, T. L. (1996). Magic checking: Constraint checking for database query optimisation. In Constraint Databases and Applications - ESPRIT WG CONTESSA Workshop, 1995, Proceedings (pp. 148-166). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1034). Springer-Verlag London Ltd..

Wallace, Mark ; Bressan, Stephane ; Provost, Thierry Le. / Magic checking : Constraint checking for database query optimisation. Constraint Databases and Applications - ESPRIT WG CONTESSA Workshop, 1995, Proceedings. Springer-Verlag London Ltd., 1996. pp. 148-166 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f49990c32f274a709bfe24f3fbea7f9c,

title = "Magic checking: Constraint checking for database query optimisation",

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.",

author = "Mark Wallace and Stephane Bressan and Provost, {Thierry Le}",

year = "1996",

month = jan,

day = "1",

language = "English",

isbn = "3540607943",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag London Ltd.",

pages = "148--166",

booktitle = "Constraint Databases and Applications - ESPRIT WG CONTESSA Workshop, 1995, Proceedings",

address = "Germany",

note = "Workshop on Constraint Databases and Applications, ESPRIT WG CONTESSA 1995 ; Conference date: 08-09-1995 Through 09-09-1995",

}

Wallace, M, Bressan, S & Provost, TL 1996, Magic checking: Constraint checking for database query optimisation. in Constraint Databases and Applications - ESPRIT WG CONTESSA Workshop, 1995, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1034, Springer-Verlag London Ltd., pp. 148-166, Workshop on Constraint Databases and Applications, ESPRIT WG CONTESSA 1995, Friedrichshafen, Germany, 8/09/95.

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 - Workshop on Constraint Databases and Applications, ESPRIT WG CONTESSA 1995

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.

Y2 - 8 September 1995 through 9 September 1995

ER -

Wallace M, Bressan S, Provost TL. Magic checking: Constraint checking for database query optimisation. In 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)).