{"entities":{"Q4649543":{"pageid":6679124,"ns":120,"title":"Item:Q4649543","lastrevid":82273454,"modified":"2026-05-06T20:30:43Z","type":"item","id":"Q4649543","labels":{"en":{"language":"en","value":"A negative conjunctive query is easy if and only if it is beta-acyclic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6109830"}},"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":"Q4649543$12806475-EAF6-4B92-AABF-3C8FA25B899E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ec3d81ab973f8dd9470dd1b9318827257c5d58d5","datavalue":{"value":"1252.68092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4649543$72216848-30CE-44D0-992A-B5E849E1F4D4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"afd0b9146c048826e2e80db78aeea5ac72179e1e","datavalue":{"value":{"entity-type":"item","numeric-id":2954990,"id":"Q2954990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4649543$2D6078AC-A38B-4234-9842-72530F5A5081","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2f3aa46d2f66375aad8f9f235cf6aa2da570e73e","datavalue":{"value":{"time":"+2012-11-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4649543$A7238A29-3427-4700-9A09-E3137CAA1F3A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf2726c5c2109371cc10358eaa69bc4df711caf7","datavalue":{"value":"68P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4649543$830C87D4-F3D2-418A-B3BF-9B69765D74FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4649543$AE5F7E8C-076B-4D4E-9283-18CDE9556BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4649543$897CD4A5-2B2D-4CAF-B18A-2FCE4BA4E546","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4649543$ACFFF9E6-8BE9-4625-9BF9-67A940A93AC7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f5a4c04a7c2b61071d0e7dbe26aa293ae8c5450c","datavalue":{"value":"6109830","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4649543$05B0C4B8-5DF2-484F-B3B7-D60557DCD907","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"70cee574f6c8b66af1be6f142a132e8c7bec4915","datavalue":{"value":"conjunctive query","type":"string"},"datatype":"string"},"type":"statement","id":"Q4649543$6934E4EF-48CA-43F5-847C-BD5CBEDF38CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63a0b5bbdbffeb2f6d94dda6a7bccbc2173775aa","datavalue":{"value":"hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4649543$D6B0CDC4-109D-4F69-9C5B-02DE87557EFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e56693d1482687cc5824488d3e4d1daf4638d852","datavalue":{"value":"beta-acyclicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4649543$7F0D497E-60DC-48D7-984A-822C60A3EEFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d49315be35778c568eabedbed4ed634f5c9eb2d","datavalue":{"value":"data complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4649543$A46C8CFD-4514-4C7D-ABE3-833B320F55AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b2085f6ca6b5f22ff227aa538ed50fc77fe1a47b","datavalue":{"value":"Davis-Putnam procedure","type":"string"},"datatype":"string"},"type":"statement","id":"Q4649543$8F658A59-7B45-40BE-B563-3ED5D2BA60DB","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":"Q4649543$E0C40A23-84D6-4867-9C6A-845FFA71C3EA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3e04329936b2cde85452cbd76365277a72f66301","datavalue":{"value":"10.4230/LIPICS.CSL.2012.137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4649543$E5BD403C-B57E-4F9C-9013-F56E4AFCA912","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54971bdb5f6072c500ce009e99e3a0ab2928a080","datavalue":{"value":{"entity-type":"item","numeric-id":3196620,"id":"Q3196620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e17fd3900d6101d83fb1ea0c427aa820142b9a27","datavalue":{"value":{"amount":"+0.7763333320617676","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4649543$DD9BB509-4F50-44CC-9F8D-101912E20D95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0659dd7fb668c3a07cce0101e91f1c20d5145767","datavalue":{"value":{"entity-type":"item","numeric-id":696962,"id":"Q696962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2658370f57759af7f9a7b721513c8d29fd012883","datavalue":{"value":{"amount":"+0.7755386829376221","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4649543$D4441549-9483-4271-92D2-A58FA5D5028F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4726337f2943fc1103d9da9a061f07e39840c7d","datavalue":{"value":{"entity-type":"item","numeric-id":506166,"id":"Q506166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8992e4b1040cf509c9283d123caeaca4464c9c92","datavalue":{"value":{"amount":"+0.7718681693077087","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4649543$62C7F678-0C4B-44AF-8403-E7740FEFBBF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5009cee825a4099a9791240836bc0979731768b","datavalue":{"value":{"entity-type":"item","numeric-id":3608414,"id":"Q3608414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02b1d063c67faac4ead87cda15297573c1277073","datavalue":{"value":{"amount":"+0.7629659175872803","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4649543$AF0D18E3-4282-43C3-B249-8DE5EE4C50F9","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":"15f2d155df4cbc60609ecc70e72fcef86622f3f0","datavalue":{"value":{"amount":"+0.7520365118980408","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4649543$C310547D-CAC0-4384-82F1-DD62053AB486","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A negative conjunctive query is easy if and only if it is beta-acyclic","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_negative_conjunctive_query_is_easy_if_and_only_if_it_is_beta-acyclic"}}}}}