{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T20:14:39Z","timestamp":1784232879907,"version":"3.55.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n            A well-established and fundamental insight in database theory is that negation (also known as complementation) tends to make queries difficult to process and difficult to reason about. Many basic problems are decidable and admit practical algorithms in the case of unions of conjunctive queries, but become difficult or even undecidable when queries are allowed to contain negation. Inspired by recent results in finite model theory, we consider a restricted form of negation,\n            <jats:italic>guarded negation<\/jats:italic>\n            . We introduce a fragment of SQL, called GN-SQL, as well as a fragment of Datalog with stratified negation, called GN-Datalog, that allow only guarded negation, and we show that these query languages are computationally well behaved, in terms of testing query containment, query evaluation, open-world query answering, and boundedness. GN-SQL and GN-Datalog subsume a number of well known query languages and constraint languages, such as unions of conjunctive queries, monadic Datalog, and frontier-guarded tgds. In addition, an analysis of standard benchmark workloads shows that many uses of negation in SQL in practice are guarded.\n          <\/jats:p>","DOI":"10.14778\/2350229.2350250","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1328-1339","source":"Crossref","is-referenced-by-count":18,"title":["Queries with guarded negation"],"prefix":"10.14778","volume":"5","author":[{"given":"Vince","family":"B\u00e1r\u00e1ny","sequence":"first","affiliation":[{"name":"TU Darmstadt, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Balder","family":"ten Cate","sequence":"additional","affiliation":[{"name":"UC Santa Cruz, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Otto","sequence":"additional","affiliation":[{"name":"TU Darmstadt, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Addison-Wesley","author":"Abiteboul S.","year":"1995"},{"key":"e_1_2_1_2_1","volume-title":"Elsevier","author":"Arnold A.","year":"2001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.03.002"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5591\/978-1-57735-516-8\/IJCAI11-126"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.02.005"},{"key":"e_1_2_1_7_1","first-page":"356","volume-title":"Proc. ICALP","author":"B\u00e1r\u00e1ny V.","year":"2011"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273529"},{"key":"e_1_2_1_9_1","unstructured":"A. Blumensath M. Otto and M. Weyer. Decidability results for the boundedness problem. Preprint at www.mathematik.tu-darmstadt.de\/~otto\/ 2011.  A. Blumensath M. Otto and M. Weyer. Decidability results for the boundedness problem. Preprint at www.mathematik.tu-darmstadt.de\/~otto\/ 2011."},{"key":"e_1_2_1_10_1","volume-title":"Proc. Description Logics Workshop","author":"Cal\u00ec A.","year":"2009"},{"key":"e_1_2_1_11_1","first-page":"260","volume-title":"Proc. KR","author":"Calvanese D.","year":"2006"},{"key":"e_1_2_1_12_1","first-page":"344","volume-title":"Proc. STACS","author":"B.","year":"2011"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1452"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87531-4_30"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62259"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/504077.504079"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962450"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/788021.788956"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(95)00051-K"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/211414.211419"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42273"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-005-5789-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00736-3"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.03.001"},{"key":"e_1_2_1_27_1","volume-title":"Proc. Description Logics Workshop","author":"Ortiz M.","year":"2006"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"M. Otto. Expressive completeness through logically tractable models. Submitted 2012.  M. Otto. Expressive completeness through logically tractable models. Submitted 2012.","DOI":"10.1016\/j.apal.2013.06.017"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_12"},{"key":"e_1_2_1_30_1","volume-title":"Accessed","author":"Sky Survey Sloan Digital","year":"2011"},{"key":"e_1_2_1_31_1","unstructured":"TPPC. TPC-DS benchmark. http:\/\/www.tpc.org\/tpcds\/. Release 2008-01-21.  TPPC. TPC-DS benchmark. http:\/\/www.tpc.org\/tpcds\/. Release 2008-01-21."},{"key":"e_1_2_1_32_1","unstructured":"TPPC. TPC-H benchmark. http:\/\/www.tpc.org\/tpch\/. Release 2.14.3.  TPPC. TPC-H benchmark. http:\/\/www.tpc.org\/tpch\/. Release 2.14.3."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1455"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:27:58Z","timestamp":1672226878000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":33,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350250"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350250","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}