We argue that database query languages can be used to spec- if'y constraint satisfaction problems. We describe one such language here. It is based on tuple relational calculus and its sentences are used to define constraints. For a fragment of this language we develop a front end, Constraint Lingo, to fa- cilitate programming tasks. Finally, we show that programs in Constraint Lingo can be compiled into DATALOG ~ and its versions and processed by ASP solvers such as smodels. Introduction In this preliminary report, we treat the class of constraint- satisfaction problems that can be conveniently modeled by means of query languages developed in the area of databases. We discuss one such language here based on tu- ple relational calculus (Maier 1983). We describe an im- plementation of a restricted version that we call Constraint Lingo. We show that answer-set programming formalisms such as smodels (Niemelfi & Simons 1997; 2000), des (East & Truszczydski 2000) and dlv (Eiter et al. 1998) can be used as a processing back end for Constraint Lingo. We conclude with a brief discussion of related research problems. DATALOG-" is a restricted version of the formalism of logic programming with stable-model semantics in that it disallows function symbols from the language. It has been proposed as a query language; the resu-iction is motivated by the requirement of finiteness of answers to database queries (Ullman 1988). A database, say D, is represented in DATALOG" by a collection of ground atoms defining ex- tensions of the corresponding predicates. These atomic facts are referred to as the extensional database and their predicate symbols as extensional predicates. A DATALOG" program Q such that extensional predicates appear only in the bodies of its rules is called a query. All non-extensional predicates occurring in a query are called intensional. A query Q on an extensional database D is a specification ofintensional pred- icates appearing in Q. The extension of one (distinguished) intensional predicate serves as the answer to Q. This ex- tension is defined through some chosen semantics of logic programs with negation, for instance, stable-model seman- tics. Namely, ifM is a stable model ofQ U D, and answer is the intensional predicate of interest, the answer is given
['Raphael A. Finkel', 'Victor W. Marek', 'Miroslaw Truszczynski']
Tabular Constraint-Satisfaction Problems and Answer Set Programming.