{"entities":{"Q1920218":{"pageid":1930960,"ns":120,"title":"Item:Q1920218","lastrevid":69468627,"modified":"2026-04-13T07:12:26Z","type":"item","id":"Q1920218","labels":{"en":{"language":"en","value":"Testing bag-containment of conjunctive queries"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 918705"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920218$022DBC22-E847-4AB5-A277-60250E4A047B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8f6d57aceb104283fba847666407415a20d827b4","datavalue":{"value":{"text":"Testing bag-containment of conjunctive queries","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1920218$9D07157D-1C3B-49E3-A5D2-3E99CD475650","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"902752ce96455e05c20980b1e41c1899ec5cd60e","datavalue":{"value":"0868.68040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920218$66F491B0-D684-4E89-8F4F-46AA28777C74","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"18b87b6321979d2969e38afba43e9d77c01350c0","datavalue":{"value":{"entity-type":"item","numeric-id":854682,"id":"Q854682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920218$C0ABB96F-6B0D-4A3B-BA8D-30C24A61C2FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"57e9389cd5d334c6c0438ac05cdee6b187ca5e82","datavalue":{"value":{"entity-type":"item","numeric-id":1092682,"id":"Q1092682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920218$64C18FA8-A450-4A7A-933D-014A7AAC598F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920218$F842D449-6907-4588-9D46-B8BE54A9CCAA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c52e4811fffdb8f318da6437d640586a60136db4","datavalue":{"value":{"time":"+1996-09-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1920218$B7C18854-552E-4479-BC07-3F264F300A9D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"191a873c7bd4d79c0e704d5c1a9a7717064bffc5","datavalue":{"value":"Among the bag-theoretic semantics relations are bags of tuples, that is, a tuple may have any number of duplicates. Among this semantics, a conjunctive query \\(Q\\) is bag-contained in a conjunctive query \\(Q'\\), denoted \\(Q\\leq_b Q'\\), if for all databases \\({\\mathcal D}\\), \\(Q({\\mathcal D})\\), the result of applying \\(Q\\) to \\({\\mathcal D}\\), is a subbag of \\(Q' ({\\mathcal D})\\). It is not known whether testing \\(Q\\leq_b Q'\\) is decidable.    In this paper we prove that \\(Q\\leq_b Q'\\) can be tested on a finite set of canonical databases built from the body of \\(Q\\). Using that result we give a procedure that decides the bag-containment problem of conjunctive queries in a large number of cases.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920218$4450C2DC-5A89-4666-9834-D2B992FEC754","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf2726c5c2109371cc10358eaa69bc4df711caf7","datavalue":{"value":"68P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920218$3B32F75A-A72C-40A5-B76D-248DAADC929D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"40d293f5d2161e80872b42afb12a3fc45e5d1401","datavalue":{"value":"68Q55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920218$A174D743-53AC-4B46-A20C-BC2A171DCE95","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a90527365d7d224c684f52272c474f12308e44c4","datavalue":{"value":"918705","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920218$D025E7C8-6B85-48CE-9860-3886C32AB6EF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"979e2e8c35d2089152d9adc9f2441c0e78da961a","datavalue":{"value":"query optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920218$5E2B52BC-DE87-47F9-A681-4C37B4A85697","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"165c1b0e5f579996790113a62a7f1f14329b9005","datavalue":{"value":"conjunctive queries","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920218$440C56F1-B3FD-4331-9076-5288DFD93C55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1811f693351f740c063d29ea7d71b0d58e9e52c","datavalue":{"value":"bag-containment","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920218$34C5A3AE-B4F8-4955-8537-476F5C61E623","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1b637ce835cb863da2bc2f21dc990737c370b6e","datavalue":{"value":"bags","type":"string"},"datatype":"string"},"type":"statement","id":"Q1920218$E67C40A7-1FF2-4514-B7F7-21440665A041","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1920218$925AB529-D1BB-48B6-882E-338FD814515A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d01941f0f26685400a8c2c05fcf168a0734f0733","datavalue":{"value":"https://doi.org/10.1007/s002360050097","type":"string"},"datatype":"url"},"type":"statement","id":"Q1920218$C8A8910E-7F09-4EA1-BD2F-7BD483FEB3A7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cf1748ff9d4c17f75dd98eb1626f6c280643052a","datavalue":{"value":"W2082788828","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920218$7276D2EB-1F7E-410C-B4A9-9397F24C4AA5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e4a3f6969f17cd6eab7a29b0e289c7f404d20bf9","datavalue":{"value":"10.1007/S002360050097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1920218$6B1D2715-CE27-4901-9298-6BA3F946C97C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d75f1360d111c98284274f74d71a0565579d92ac","datavalue":{"value":{"entity-type":"item","numeric-id":1057666,"id":"Q1057666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ea5f9656ffe244c5479fdf2c8c786a1641dfd01","datavalue":{"value":{"amount":"+0.8994857","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1920218$C323C9EC-7C8E-476C-B6C3-20F10D58631A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e24d99d18c0361e6b67ee89fea29563841a40751","datavalue":{"value":{"entity-type":"item","numeric-id":1575132,"id":"Q1575132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00a3ba6ae96791945126ab99157ed3ccd52d7388","datavalue":{"value":{"amount":"+0.87077045","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1920218$35E3F110-4F1C-4D24-9471-6E940F1A6BD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afe3558cf08ec23eaa3513730d75156eb1e85d53","datavalue":{"value":{"entity-type":"item","numeric-id":656574,"id":"Q656574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b43b9780d0e65704d38e5da16719fbbefa4cea79","datavalue":{"value":{"amount":"+0.8626039","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1920218$A19E7F4B-EEE6-407E-8A37-777EEF062ED6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a551ace395b7a3844cba077e1a1ea4ec734e714","datavalue":{"value":{"entity-type":"item","numeric-id":1403319,"id":"Q1403319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"392d6e89c9a1a0d88f1c2bc5380311e9292aa6fc","datavalue":{"value":{"amount":"+0.8608503","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1920218$26770486-2DEE-438C-BE8B-7E8169906BF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae120cefbde4c0dc4c211bb52527f719dd187283","datavalue":{"value":{"entity-type":"item","numeric-id":4413799,"id":"Q4413799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32306809ec651b35cd9553b5b0a8cf412d2614e9","datavalue":{"value":{"amount":"+0.8558974","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1920218$E221C98E-02F0-42EC-8E05-C1E048D04F2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f5546286f751532456075fff07f24dc72464867","datavalue":{"value":{"entity-type":"item","numeric-id":1341716,"id":"Q1341716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6318cb576c2056a3b096ea66ea202ed19d97ef8e","datavalue":{"value":{"amount":"+0.8546173","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1920218$9B46897D-5D6A-4C60-90D7-D7BE4E508106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39a2cde80f07a8c854ecec37b2e677c9e1d849d1","datavalue":{"value":{"entity-type":"item","numeric-id":1591157,"id":"Q1591157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3582f89677e55e9491d16fd3639add2f146206d5","datavalue":{"value":{"amount":"+0.8429722","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1920218$F601DB12-B019-410B-848B-C3677B3AC9A5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Testing bag-containment of conjunctive queries","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Testing_bag-containment_of_conjunctive_queries"}}}}}