{"entities":{"Q688665":{"pageid":690514,"ns":120,"title":"Item:Q688665","lastrevid":63634032,"modified":"2026-04-11T14:29:59Z","type":"item","id":"Q688665","labels":{"en":{"language":"en","value":"On the complexity of queries in the logical data model"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 438312"}},"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":"Q688665$114FD4B9-0ACD-4CD9-8607-ACA632B91DAD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"db6a20f9f2bba3ec776939ee127418a8d39ad9a8","datavalue":{"value":{"text":"On the complexity of queries in the logical data model","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q688665$948C87C4-6444-40E6-BD84-0EFCB754F579","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f637541cccabae49babbc126ee26cd5c2ac01ffe","datavalue":{"value":"0798.68072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688665$B21C3C89-EEF0-4EF7-B5DF-DB91232EDA93","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2999f21a0b2b1bd9ca2ff5804c8ac44973ca8fbf","datavalue":{"value":"10.1016/0304-3975(93)90219-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688665$67AFE670-7D5A-4279-9316-BCAD8C4F750B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa303ec75886dba15e294b6c0a159a95c2aff9f7","datavalue":{"value":{"entity-type":"item","numeric-id":688664,"id":"Q688664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688665$87753101-99DE-4587-9214-C2CBF8AC31C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce87cbb6ded942a7df2b71cd7e21808de8efe775","datavalue":{"value":{"entity-type":"item","numeric-id":208771,"id":"Q208771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688665$5522EC7A-7619-44F3-BEE0-251745486B33","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688665$FFAA8580-1DA6-4691-8FF1-04B029CAE99F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"32d1d77beb5f3bc65c221a38015efeb024af2386","datavalue":{"value":{"time":"+1994-11-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q688665$7260EA69-F10A-4871-A413-D075CA0C81CB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"20de7b66bce32bc9567fc4d1351338fab1289cfb","datavalue":{"value":"The authors introduced [``A new approach to database logic'', in: Proc. ACM Symp. on New Principles of Database Systems, pp. 86-96 (ACM, 1984)] the logical data model (LDM) which combines and extends Jacobs' database logic and Hull and Yap's format model. The three basic operations in the LDM are: product, union and power set. This paper continues previous studies on the expressiveness of LDM; the concern is on the complexity of query processing. Two measures previously used for the complexity of relational query languages are used: data complexity (complexity w.r.t. the size of the data) and expression complexity (complexity w.r.t. the size of the expressions denoting the queries). The authors show that the product and the union are essentially first-order operations, while the power set is inherently a higher-order operation and is exponentially expensive. In a previous study [``On the expressive power of the logical data model'', in Proc. SIGMOD 1985, p. 180-187 (ACM, 1985)], the authors had shown that the logic of integrity constraints for the LDM is essentially first-order even when the power set operation is involved; the reason for the contrast with the new result is that the logic for integrity constraints deals with existing values when the power set operation is used, whereas the logical query language tries to create new values of power nodes in the schema.   A hierarchy of queries is defined, based on the depth of nesting of powerset operations. This hierarchy is shown to correspond to a hierarchy of alternating Turing machines. The authors give a complete characterization of the complexity of the hierarchy of queries, the terms of tight lower and upper bounds.","type":"string"},"datatype":"string"},"type":"statement","id":"Q688665$34ACF466-2462-4001-B5FB-CA5AB1B2D8C6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688665$F475A6F4-4DC5-48AE-B6D1-E2F3779FF13D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf2726c5c2109371cc10358eaa69bc4df711caf7","datavalue":{"value":"68P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688665$2C8B6E44-F3B6-447C-A0E7-108FB5CFA9EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688665$0B7CCA95-5D53-4EDC-A77B-85036513DA6A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9c7a67c010a3be086f2446067404e825e5e93ec7","datavalue":{"value":"438312","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688665$3A29A3A9-3AEE-43DB-90A6-D6214F599935","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29053cdc10dd0b14e6be36da09a181b85322ea26","datavalue":{"value":"logical data model","type":"string"},"datatype":"string"},"type":"statement","id":"Q688665$5607AF22-9A57-4C19-84E1-C8CB1BC4545B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d964a9a8070e695750f1e5917d3883510ded1814","datavalue":{"value":"database logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q688665$C833204E-6B96-469D-816A-054528D3C133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce625526a9672d8cc9b3821e2df64c296d05f546","datavalue":{"value":"format model","type":"string"},"datatype":"string"},"type":"statement","id":"Q688665$88ABC6C3-C34D-465C-9E7C-8B3CBE9376C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78e469cb56ef748b3f9619abee5f10dfa052a7b9","datavalue":{"value":"expressiveness","type":"string"},"datatype":"string"},"type":"statement","id":"Q688665$603753A0-14CF-4CAE-968D-736D896D68B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61822726412ad5a8b26f03530884ba7934190cab","datavalue":{"value":"complexity of query processing","type":"string"},"datatype":"string"},"type":"statement","id":"Q688665$96C11460-C944-413E-97F6-03AA0CD3BF70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d49315be35778c568eabedbed4ed634f5c9eb2d","datavalue":{"value":"data complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q688665$FA1AEDF1-F05C-44B6-8DDC-CDFEF991BB11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d914195427141ad87f61539c4730fe0d1ea0d00","datavalue":{"value":"expression complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q688665$108A617D-A617-4402-BE5B-98E092A15762","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd02c0c4cd88bf32f0b507a5c512ad6914c3d82b","datavalue":{"value":"integrity constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q688665$C7F8A720-F268-4482-BCF4-AC488CC5257E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2d267e367ec10669b0cc3c193f4ac8d5fb0c91f","datavalue":{"value":"logical query language","type":"string"},"datatype":"string"},"type":"statement","id":"Q688665$B2411ED4-7A41-44FE-AD9B-3EC2197AF33B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73ebd5021b1f9cabffa6534aa25947283831467f","datavalue":{"value":{"entity-type":"item","numeric-id":790617,"id":"Q790617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688665$498AFDC0-DAA8-4020-A559-0750668E848E","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":"Q688665$9D32BA8D-1120-4402-A801-5480DFC57DD5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"baf0ba6b785a0b2a745ee15b2938633ce0540bc3","datavalue":{"value":{"entity-type":"item","numeric-id":5830955,"id":"Q5830955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688665$1DDE768D-375A-4D4F-A669-2127F3BD2B50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04199e03d1d3ec0d2b5fbfff526a164b91654871","datavalue":{"value":{"entity-type":"item","numeric-id":1838840,"id":"Q1838840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688665$2FA7F666-5AC3-43A8-89C1-C2DF065DCFBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688665$04F89DA6-D91E-48BC-92FA-F499D9E97146","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b00c51201f67e59e740260c694a944ba5779880","datavalue":{"value":{"entity-type":"item","numeric-id":5607609,"id":"Q5607609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688665$F15BDD67-034E-4400-9D62-386E5A06E230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688665$2F85AD44-E9EC-4471-B15F-2E66847DD340","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d753f602d37f387f4bb08319b5d7d62fb7f471d6","datavalue":{"value":{"entity-type":"item","numeric-id":3766893,"id":"Q3766893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688665$DE3B2B93-46F2-4ABA-9F65-30A6ABB01567","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"615b3503f4eabccb3bc1e2508fae039476d7db44","datavalue":{"value":{"entity-type":"item","numeric-id":3962497,"id":"Q3962497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688665$EE5DA3D7-39C6-413B-98B4-416799810938","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688665$724E4639-95DF-464D-8BC7-CEF7D5103ABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3edfa56e27db92ffca6f4798f086ec18992b6864","datavalue":{"value":{"entity-type":"item","numeric-id":793017,"id":"Q793017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688665$76040808-49C7-4A7E-A72D-10694FEF4F45","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"096dc51548eb2fcb3d3c698aaaf7370d0fb8e9ea","datavalue":{"value":"https://doi.org/10.1016/0304-3975(93)90219-j","type":"string"},"datatype":"url"},"type":"statement","id":"Q688665$C6AA6DAB-C89D-457D-8E7B-DE5ECEA4C3BC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bc552e53dc36988c5e2f54c60836e186cbee9c78","datavalue":{"value":"W2155243135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688665$39F41AA7-4696-4DAE-A499-DCCDC11E5B2A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcc0c6d2746c9bbc086727a0d938433fd9696eb8","datavalue":{"value":{"entity-type":"item","numeric-id":3798297,"id":"Q3798297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","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":"Q688665$690E9F41-74E0-4AC1-97A4-81CC7715CD43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ff529f2a05e5e15654cb15f72f0be747d5cc26b","datavalue":{"value":{"entity-type":"item","numeric-id":360130,"id":"Q360130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb2c24b6a2089566aec3f263cdb237247b3827ec","datavalue":{"value":{"amount":"+0.9155333","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":"Q688665$ADA293B0-D7F2-4069-BF5F-A813854AADB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18ed8e508bf58a3561d9a885343b326b4221e1df","datavalue":{"value":{"entity-type":"item","numeric-id":3643109,"id":"Q3643109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9f5bc5e8817e1040d918e0fbc0fb73d93a90d75","datavalue":{"value":{"amount":"+0.89861715","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":"Q688665$AD9D2C69-AD4D-4AD4-AFE0-897949D71EF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7aa258104143d9df59363526b6532fa9b704a57e","datavalue":{"value":{"entity-type":"item","numeric-id":945056,"id":"Q945056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a75e2a1f2e7ff7b14b58506c50a933bddecbe53","datavalue":{"value":{"amount":"+0.8979356","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":"Q688665$FEDF52A7-249F-46D6-A20B-5D3BD31DBF88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b719a9c560ecf484c9add700155ae4fcd08821b","datavalue":{"value":{"entity-type":"item","numeric-id":1307689,"id":"Q1307689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c10022e8af9b79d4c95ecc0de5ac266388b6beb9","datavalue":{"value":{"amount":"+0.88873535","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":"Q688665$CACE97EA-E2FB-4FC1-B695-014D8F00E493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e8039936cb89626db27b247bf71ac85984c2c04","datavalue":{"value":{"entity-type":"item","numeric-id":3334110,"id":"Q3334110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"734694abb08eb135f576bd43f48189143186cb2b","datavalue":{"value":{"amount":"+0.88866216","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":"Q688665$1E93540E-E6F6-4E2A-BE6F-E555B5FC9066","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"164be3db64f1f40c76d9d0f030e7bb018859e7f2","datavalue":{"value":{"entity-type":"item","numeric-id":4938426,"id":"Q4938426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36d013032f5db514c1dacf4ea9a8d40339573000","datavalue":{"value":{"amount":"+0.88814265","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":"Q688665$5B07CCC2-33B5-4995-9B3A-65ABF13E3988","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1077625a58032b6eaa48e422764e16f398eafb8","datavalue":{"value":{"entity-type":"item","numeric-id":3623016,"id":"Q3623016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b7204bdbe2a5a41a89887a9710776284f04416d","datavalue":{"value":{"amount":"+0.8853806","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":"Q688665$AA7FDFD7-ECAB-4517-9BFF-9A1E56DF879B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ec0a7055ddd845f2ebd3656e4516f45e34baae4","datavalue":{"value":{"entity-type":"item","numeric-id":269317,"id":"Q269317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f96f27e068846dc373f78811651d8477d7a8d19","datavalue":{"value":{"amount":"+0.8852944","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":"Q688665$A7A2D2D2-B191-4AB9-809F-E3ABD9A13EC5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of queries in the logical data model","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_queries_in_the_logical_data_model"}}}}}