{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:13:13Z","timestamp":1760170393981},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"1-2","license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The goal of this paper is to provide a strong integration between constraint modelling and relational DBMSs. To this end we propose extensions of standard query languages such as relational algebra and <jats:sc>SQL<\/jats:sc>, by adding constraint modelling capabilities to them. In particular, we propose non-deterministic extensions of both languages, which are specially suited for combinatorial problems. Non-determinism is introduced by means of a <jats:italic>guessing<\/jats:italic> operator, which declares a set of relations to have an arbitrary extension. This new operator results in languages with higher expressive power, able to express all problems in the complexity class NP. Some syntactical restrictions which make data complexity polynomial are shown. The effectiveness of both extensions is demonstrated by means of several examples. The current implementation, written in Java using local search techniques, is described.<\/jats:p>","DOI":"10.1017\/s1471068406002857","type":"journal-article","created":{"date-parts":[[2007,2,9]],"date-time":"2007-02-09T07:38:10Z","timestamp":1171006690000},"page":"37-65","source":"Crossref","is-referenced-by-count":7,"title":["Combining relational algebra, <i>SQL<\/i>, constraint modelling, and local search"],"prefix":"10.1017","volume":"7","author":[{"given":"MARCO","family":"CADOLI","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TONI","family":"MANCINI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2007,1,1]]},"reference":[{"key":"S1471068406002857_N10200","unstructured":"Eclipse. ECLiPSe Home page. www-icparc.doc.ic.ac.uk\/eclipse\/."},{"key":"S1471068406002857_N103DF","unstructured":"Sicstus. SICStus Prolog home page. http:\/\/www.sics.se\/sicstus\/."},{"key":"S1471068406002857_N10267","volume-title":"AMPL: A Modeling Language for Mathematical Programming","author":"Fourer","year":"1993"},{"key":"S1471068406002857_N10104","volume-title":"Local search in combinatorial optimization","author":"Aarts","year":"1997"},{"key":"S1471068406002857_N1013F","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.34.2.180.12302"},{"key":"S1471068406002857_N10393","doi-asserted-by":"publisher","DOI":"10.1023\/A:1006576209967"},{"key":"S1471068406002857_N1032E","unstructured":"Leone N. , Pfeifer G. , Faber W. , Eiter T. , Gottlob G. and Perri Simona abd Scarcello F. The DLV System for Knowledge Representation and Reasoning. ACM Transactions on Computational Logic. To appear."},{"key":"S1471068406002857_N101B7","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90032-X"},{"key":"S1471068406002857_N1043F","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45193-8_5"},{"key":"S1471068406002857_N10121","unstructured":"Abiteboul S. , Hull R. and Vianu V. 1995. Foundations of Databases. Addison, Reading, Massachussetts."},{"key":"S1471068406002857_N1016E","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45988-X_12"},{"key":"S1471068406002857_N10194","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00108-4"},{"key":"S1471068406002857_N102ED","unstructured":"ILOG-98 1998. ILOG optimization suite \u2013 white paper. Available at www.ilog.com."},{"key":"S1471068406002857_N101DA","doi-asserted-by":"publisher","DOI":"10.1002\/spe.524"},{"key":"S1471068406002857_N10215","first-page":"43","volume-title":"Complexity of Computation","author":"Fagin","year":"1974"},{"key":"S1471068406002857_N1023B","first-page":"214","volume-title":"Proceedings of International Symposium LOPSTR 2003: Revised selected papers","author":"Flener","year":"2004"},{"key":"S1471068406002857_N10287","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"S1471068406002857_N102A4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-6089-0"},{"key":"S1471068406002857_N102C1","doi-asserted-by":"publisher","DOI":"10.1145\/972639.972646"},{"key":"S1471068406002857_N102FC","unstructured":"ILOG-DBLINK 1999. ILOG DBLink 4.1 Tutorial. Available at www.ilog.com."},{"key":"S1471068406002857_N1035B","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009818401322"},{"key":"S1471068406002857_N10381","unstructured":"Papadimitriou C. H. 1994. Computational Complexity. Addison Wesley, Reading, MA."},{"key":"S1471068406002857_N103EB","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00187-X"},{"key":"S1471068406002857_N10417","volume-title":"Principles of Database and Knowledge Base Systems","author":"Ullman","year":"1988"},{"key":"S1471068406002857_N1042B","volume-title":"The OPL Optimization Programming Language","author":"Van Hentenryck","year":"1999"},{"key":"S1471068406002857_N10465","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"S1471068406002857_N103B3","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(200003)30:3<233::AID-SPE297>3.0.CO;2-K"},{"key":"S1471068406002857_N1030B","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90033-2"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068406002857","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,4]],"date-time":"2019-04-04T16:49:35Z","timestamp":1554396575000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068406002857\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":28,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["S1471068406002857"],"URL":"https:\/\/doi.org\/10.1017\/s1471068406002857","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}