Magic checking: Constraint checking for database query optimisation

Mark Wallace, Stephane Bressan, Thierry Le Provost

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

2 Citations (Scopus)

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 languageEnglish
Title of host publicationConstraint Databases and Applications - ESPRIT WG CONTESSA Workshop, 1995, Proceedings
PublisherSpringer-Verlag London Ltd.
Pages148-166
Number of pages19
ISBN (Print)3540607943, 9783540607946
Publication statusPublished - 1 Jan 1996
Externally publishedYes
EventWorkshop on Constraint Databases and Applications, ESPRIT WG CONTESSA 1995 - Friedrichshafen, Germany
Duration: 8 Sep 19959 Sep 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1034
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceWorkshop on Constraint Databases and Applications, ESPRIT WG CONTESSA 1995
CountryGermany
CityFriedrichshafen
Period8/09/959/09/95

Cite this