The Semantic Web is the next evolutionary step of the open internet. Standardized by the W3C, it makes information on the web understandable by the computer. Web sites can publish data in a standard format, linking to data from other sites.

RDF is the graph-based data format at the core of the Semantic Web. Queries in such linked databases are usually expressed with the SPARQL language. The graph-based nature of the data makes evaluating such queries inherently NP-hard. Multiple solutions have been proposed to tackle the problem, but none are currently fully satisfactory. Efficient querying of Semantic Web databases is an open research problem.

Constraint Programming is an optimization technique designed to handle NP-hard problems. It has been applied with success to various graph matching problems, which are closely related to the SPARQL problem. The goal of this research is to explore constraint programming for solving SPARQL queries.