{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T21:41:18Z","timestamp":1698010878158},"reference-count":8,"publisher":"Wiley","issue":"7","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":7749,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp;amp; Computers in Japan"],"published-print":{"date-parts":[[1986,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Tableau queries are known as abstract models of queries for relational databases. When two tableau queries are given, the problem of determining whether the result of one of the tableau queries always contains that of the other (containment decision problem), is of fundamental importance in obtaining the optimization procedure of tableau queries. The tableau queries defined by Aho et al. can express joins, projections and selections by equalities in the relational algebra. Under this definition, Aho et al. have shown that the containment decision problems are generally NP\u2010complete and that there exist a class of problems which can be decided in a polynomial time. In this paper, we classify the tableau queries which are obtained so as to be able to express the selections by inequalities into two groups by whether or not they are totally ordered. We show that if inequality selections are added to problems which can be solved in a polynomial time without inequality selection, then the containment decision problems are NP\u2010complete even though the tableau queries are totally ordered. Also, for queries which are not totally ordered, it is shown that even if stronger restriction is added, the containment decision problems are co\u2010NP\u2010complete.<\/jats:p>","DOI":"10.1002\/scj.4690170709","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T12:28:28Z","timestamp":1183811308000},"page":"73-85","source":"Crossref","is-referenced-by-count":0,"title":["Complexity to determine containment among inequality tableau queries"],"prefix":"10.1002","volume":"17","author":[{"given":"Tomoyuki","family":"Terada","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ken'Ichi","family":"Hagihara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nobuki","family":"Tokura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Design and Analysis of Computer Algorithms II","author":"Aho A. V.","year":"1977"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208017"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320112"},{"key":"e_1_2_1_5_2","volume-title":"On Inequality Tableaux, Computer Science Report 403","author":"Klug A.","year":"1980"},{"key":"e_1_2_1_6_2","volume-title":"The Theory of Relational Databases","author":"Maier D.","year":"1983"},{"key":"e_1_2_1_7_2","first-page":"69","article-title":"On the containment of Values of Tableau Queries with Inequality Selections in Relational Databases","volume":"84","author":"Terada","year":"1985","journal-title":"Technical Reports of I.E.C.E., Japan"},{"key":"e_1_2_1_8_2","first-page":"6","article-title":"Containment of Values of Inequality Tableau Queries","volume":"68","author":"Terada","year":"1985","journal-title":"Jour. I.E.C.E., Japan"},{"key":"e_1_2_1_9_2","first-page":"4","volume-title":"IBM Syst. J","author":"Zloof M. M.","year":"1977"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690170709","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690170709","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T00:30:44Z","timestamp":1697934644000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690170709"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,1]]},"references-count":8,"journal-issue":{"issue":"7","published-print":{"date-parts":[[1986,1]]}},"alternative-id":["10.1002\/scj.4690170709"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690170709","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,1]]}}}