{"entities":{"Q1107969":{"pageid":1118718,"ns":120,"title":"Item:Q1107969","lastrevid":67009995,"modified":"2026-04-12T14:18:17Z","type":"item","id":"Q1107969","labels":{"en":{"language":"en","value":"The complexity of strict serializability revisited"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4066301"}},"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":"Q1107969$BB904BCB-970D-4927-AEDF-96F6E15EE629","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"00d1ab6cb71320d6b76206b5cad61d600b73ff64","datavalue":{"value":{"text":"The complexity of strict serializability revisited","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1107969$306D186E-270D-4C56-83AB-E721A469735E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cbb6aa25822f5f01f4b4b1efe4b8d92008443554","datavalue":{"value":"0653.68007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107969$F5739139-4933-4E99-B2BE-F59EBD22D93F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"30302e1ada11a55019cd2bf0d460f7469743f150","datavalue":{"value":"10.1016/0020-0190(87)90220-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107969$125C5888-AE4A-4D8C-8AF1-1664D079947A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3bc908459c0826054d0dc850220d30c3ecdff71f","datavalue":{"value":{"entity-type":"item","numeric-id":1107968,"id":"Q1107968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107969$9EBDFDB1-CC2E-4CB2-9C58-310371DCD3B3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107969$AA8A3467-C526-4370-AA3C-17042492C939","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1107969$16C6560B-D783-4680-A211-812AC46228C6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c25e126ca2ec716478cd2d2f1fa9c03a4d1805e5","datavalue":{"value":"A well known result by \\textit{R. Sethi} [J. Assoc. Comput. Mach. 29, 394- 403 (1982; Zbl 0478.68098)], states that strict view- and final-state serializability are NP-complete in general, but decidable in polynomial time if useless values are absent. This paper falsifies one of these claims by proving that the absence of useless values is not sufficient to make strict final-state serializability decidable in polynomial time. Moreover, we show that a slightly stronger condition is sufficient, namely the absence of dead values. All claim intersection is empty. The algorithm is based on a simple technique for detecting a redundant inequality among a set of inequalities of two variables.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107969$5EF159B4-CA5A-4D1F-875A-3E0B6C56B7BB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107969$E3BE3E4F-E203-4029-AC4B-8D4C3A2EDFD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107969$5631D772-A897-49AC-8E3B-7EFA2488D723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107969$9F108080-25C4-4877-B5DE-F0E4E5EDBA7D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ddfc5e1c15b8953ff42eff0644f296d047c8460f","datavalue":{"value":"4066301","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107969$9CEE58E7-6B5E-4A6A-AC02-B738A9B32754","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa539aa3b4743c6aeee9af72e81e3d5a0b13aaeb","datavalue":{"value":"concurrency control theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107969$FFE8FCA6-6C17-4BBC-8C04-788B55DF2067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"021da1737bf3693b75102c9bb5f4e96fd3fefb0a","datavalue":{"value":"strict serializability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107969$6EBD3565-0631-4F19-9DCD-1A8D0336135F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67e38344b0ecbbab1496e7b5fd527e6305bff31d","datavalue":{"value":"final-state serializability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107969$23317685-0B6D-4D5C-B804-1BDC3297DF87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107969$717278E3-9661-49FA-A2BB-40FB3FF59871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b283cdacafc1481726319a2f39a67a39606025c","datavalue":{"value":"useless values","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107969$80D8710E-845A-4AFC-9333-DE4597BFA585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e17f2240aaabe8f4042129bef021d82e4f0d47e5","datavalue":{"value":"dead values","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107969$DC76DDC5-5D87-46AF-9BEF-7194674497C3","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":"Q1107969$39DF4E9E-845E-48C5-8DA0-AD75D13911C8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e7a1a4180bcd25440e607da13780aa67070270e2","datavalue":{"value":"https://doi.org/10.1016/0020-0190(87)90220-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1107969$EEC00D00-0D7E-4EC2-9840-EAEB50F17841","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f1f13a6fc9dc590be7e3d8dd679843e8903f5ff0","datavalue":{"value":"W2023087184","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107969$BC06449B-91C9-4F0D-B4FD-8B2FB6BFE19F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a10da638947251c15a164b4a0a37714c44395c55","datavalue":{"value":{"entity-type":"item","numeric-id":4179819,"id":"Q4179819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107969$64470AF9-C7EA-438D-A10C-51535029E4DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c7fc87a2e0cb80eee2b114c7b557a85059501f3","datavalue":{"value":{"entity-type":"item","numeric-id":4721674,"id":"Q4721674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107969$52682AF2-D554-4AB0-92C9-A3EB7D7D961B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6348150fbedb9a1fedfac5be360d31156eafa2e6","datavalue":{"value":{"entity-type":"item","numeric-id":3718140,"id":"Q3718140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107969$42E771F0-AD02-44A4-939E-F813E3DD27F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e820571891b785027455348609df8933bb15ff5","datavalue":{"value":{"entity-type":"item","numeric-id":3906402,"id":"Q3906402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107969$E67465E6-9D8D-46D6-972A-374603F6F917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a7ac70217829001bfdbe229aa58327de02581ad","datavalue":{"value":{"entity-type":"item","numeric-id":3853111,"id":"Q3853111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107969$BEC39CC3-24FF-4FA4-B809-08CEA71879CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dedde8f247dbdcb221d1a4bc4606ba6fbd6c0fee","datavalue":{"value":{"entity-type":"item","numeric-id":3936233,"id":"Q3936233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107969$2B6C5918-D978-48DE-BA9D-19894C4C66DA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81c15c7ac89df188359a1c6cb3ccfd5a66f73602","datavalue":{"value":{"entity-type":"item","numeric-id":3718140,"id":"Q3718140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24adb01f66c9c10f8163fe6d0db740fe798bfed1","datavalue":{"value":{"amount":"+0.8260751962661743","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":"Q1107969$EB136B33-AF04-406A-AE67-5314A8A54D93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e62ac19f5cdadcd390ab514f5665b551ac34f4d","datavalue":{"value":{"entity-type":"item","numeric-id":3341954,"id":"Q3341954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"674cd05ed6cf3003057530d93cb85c5067f45ffa","datavalue":{"value":{"amount":"+0.7935473918914795","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":"Q1107969$228FB90A-C5D1-4040-955E-101C0FFE248B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc666f36db0b318080507e52604d6e54deffbf50","datavalue":{"value":{"entity-type":"item","numeric-id":2770735,"id":"Q2770735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98d0cfd94966c39ac6bb531a61be46534a9cb5e2","datavalue":{"value":{"amount":"+0.7691823840141296","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":"Q1107969$3C284AF5-C0D3-45F3-91A3-7B1B93813409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"736fbd289fc99563389c462e1ed4f0bd74db0762","datavalue":{"value":{"entity-type":"item","numeric-id":1073577,"id":"Q1073577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b0aedc1f6c492b4929612387055579d4a0b8217","datavalue":{"value":{"amount":"+0.7620306015014648","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":"Q1107969$5EDCC295-5F0D-4F3E-AA81-6E1B47726F7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13595fb25654c4acf854f16dfa8dc04bff6f39ab","datavalue":{"value":{"entity-type":"item","numeric-id":3738609,"id":"Q3738609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd52e2c730ebe3ff46205a3ae890caaec7d32382","datavalue":{"value":{"amount":"+0.7619946002960205","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":"Q1107969$9D05229F-2C14-448E-99F5-8F8A54277380","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of strict serializability revisited","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_strict_serializability_revisited"}}}}}