{"entities":{"Q5940927":{"pageid":8117729,"ns":120,"title":"Item:Q5940927","lastrevid":47657683,"modified":"2026-01-02T08:49:14Z","type":"item","id":"Q5940927","labels":{"en":{"language":"en","value":"Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1635078"}},"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":"Q5940927$C9F19906-CB6B-491A-8F03-23163D0F2ADE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"683e40681abd1ef9d9a05d50e50ac7b9a3b22de1","datavalue":{"value":{"text":"Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5940927$77C22D52-37B8-4887-B048-71C395E2D636","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d75de3726a31cb5e222e72ad2de6359ec5b15ce8","datavalue":{"value":"0974.68047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940927$33059902-02EC-435B-B223-F2752029A428","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6fd6119c2666db5aa1da8bed20199ba66155f005","datavalue":{"value":"10.1016/S0304-3975(99)00301-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940927$730741CE-8703-41AC-9246-E7EE3B53D4B1","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":"Q5940927$F312D0B6-9508-40C1-9113-C7841E9E7C17","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0d780905acb67c2b1b938af03e08b68df411214b","datavalue":{"value":{"time":"+2001-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5940927$9BF33A23-0563-4169-9282-5F0D0C20868B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"75c5e830b9c16822990d11a3de3b96d5096f4408","datavalue":{"value":"\\textit{J. Paredaens} and \\textit{D. Van Gucht} [Converting nested algebra expressions into flat algebra expressions, ACM Trans. Database Systems 17, No. 1, 65-93 (1992)] proved that the flat relational algebra has the same expressive power as the nested relational algebra, as far as queries over flat relations and with flat results are concerned. We provide a new, very direct proof of this fact using a simulation technique. Our technique is also applied to partially answer a question posed by Suciu and Paredaens regarding the complexity of evaluating powerset algebra expressions. Specifically, we show that when only unary flat relations are into play, any powerset algebra expression is either equivalent to a nested algebra expression, or its evaluation will produce intermediate results of exponential size.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940927$D8BC4803-A69F-4F07-9ED3-F926B0B5F068","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf2726c5c2109371cc10358eaa69bc4df711caf7","datavalue":{"value":"68P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940927$82C9C469-B87B-4D5A-A4AD-D35E53C676EA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cb53a30ffc468d774c4523cb962f32f080782e73","datavalue":{"value":"1635078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940927$4A5775A3-A80E-41EB-A55F-384FE4CA8811","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f46f0232eee4bb70d433e9dbc194d128e7ecffb1","datavalue":{"value":"nested relational databases","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940927$7581F246-E697-424D-8DF1-26B4E76570AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0052dbb998ade7d726f0c0b86e4baadd7e346db9","datavalue":{"value":"query languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940927$A586C060-76D4-493A-995E-81EEFE82E6F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e16fdb519452f3bafdb17bd5ad06b8194f047110","datavalue":{"value":"expressive power","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940927$D8AEFABC-8E09-4560-BDCF-CB5340657AEA","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":"Q5940927$B071B217-1455-4276-892C-FEC84A927323","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"06f598766a9a0139de944a29433f8e771d53e2ad","datavalue":{"value":{"entity-type":"item","numeric-id":579959,"id":"Q579959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940927$45089B66-56EE-4F8D-A539-37780D9BFE38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"315f75a392dcca6bd6d67dec606516d0d989b568","datavalue":{"value":{"entity-type":"item","numeric-id":749194,"id":"Q749194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940927$99DCDC31-0357-423D-85E3-BA788C04A1BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae600d82e59da48d9490ff29ee5b51a547bc0409","datavalue":{"value":{"entity-type":"item","numeric-id":4864249,"id":"Q4864249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940927$F1970B7B-1F1B-46DA-ACF0-BE4803FF754B","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":"Q5940927$6582FCA6-D35A-4842-9769-58515EA50D0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d2c32b298b09103f7cc9eabedf752dc67f406d3","datavalue":{"value":{"entity-type":"item","numeric-id":4850061,"id":"Q4850061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940927$E5872134-F467-41F0-A5D6-8A8B31851E4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bf5d0ec7e0d14cf4d6b7a7f7341be4669ef5ba3","datavalue":{"value":{"entity-type":"item","numeric-id":1854400,"id":"Q1854400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940927$6A0777EC-FF30-4E2F-AD23-8A9AC59CF1D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a749b6395f76d2badad36cd1391ea5621fdc5da","datavalue":{"value":{"entity-type":"item","numeric-id":1176290,"id":"Q1176290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940927$51B3F614-E3F3-41AF-8842-58B3F53B1356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"498042ee4b0767ee5b7debe836b6dab24b7b3d81","datavalue":{"value":{"entity-type":"item","numeric-id":3992720,"id":"Q3992720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940927$B61D625A-E0F7-4A9E-A89B-AD4F5917CDDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b4f514d37bee8ec849b2c73f757c66c808c0fa0","datavalue":{"value":{"entity-type":"item","numeric-id":1392283,"id":"Q1392283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940927$AAE4CD68-3751-48D6-BD94-A562C2F236B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49f8316f2d4be1a618aff18e472ee1dedb56a7bf","datavalue":{"value":{"entity-type":"item","numeric-id":1376410,"id":"Q1376410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940927$FCEC2B9C-0EBD-4A58-A43B-35F5C9EB4A91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59d04fee02ae2590277472957415b41d080b5449","datavalue":{"value":{"entity-type":"item","numeric-id":1924384,"id":"Q1924384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940927$383A5755-253A-49F5-B08F-F04150223CEB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6c0d20c8e14bc8d92e55c92c0c80f162a8db7a3b","datavalue":{"value":"https://doi.org/10.1016/s0304-3975(99)00301-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q5940927$81542327-E74C-416E-8F36-4EEEF575E042","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a0b14b46de3980768fece0c5e1b38e69f96ea0a0","datavalue":{"value":"W1972514879","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940927$AB288F2D-DAD7-4B2C-991B-F7F5AB3D8D17","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a72076be407becfc76cbafa01d67d9609ac78c2f","datavalue":{"value":"Q127124586","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940927$9BD7F42B-4AD2-410D-9EC9-CCEF26BD9A9A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4d17eed939d4be15a044dfb000abeabaaa52a52","datavalue":{"value":{"entity-type":"item","numeric-id":256712,"id":"Q256712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940927$B5B1EEF9-4EA3-4206-898C-69471E29EB8D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81692fa60c008ed77d3c7ff11ab7d081241bc0e6","datavalue":{"value":{"entity-type":"item","numeric-id":1177142,"id":"Q1177142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f83e3a7ab467376f0642316cba8cd12f087b906","datavalue":{"value":{"amount":"+0.813137948513031","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":"Q5940927$AA553855-51C1-4D9D-9BD4-7048A79EFD41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5705607e5b241c2cdae9d7f36931a33989cc8c03","datavalue":{"value":{"entity-type":"item","numeric-id":4651505,"id":"Q4651505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b26f884e09bbf214b88ae641d24d8d9ce0549807","datavalue":{"value":{"amount":"+0.8131372332572937","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":"Q5940927$B00B82FB-B9BE-4986-9372-4D766BD32F97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e339056b1d26c6a1d74a0a94b3a7ec5a9c69823","datavalue":{"value":{"entity-type":"item","numeric-id":1198662,"id":"Q1198662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c46520b884f661b17f7ec536051374a13ec2e30","datavalue":{"value":{"amount":"+0.7976425290107727","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":"Q5940927$2E099754-BBBA-4069-808D-9A8BDB053789","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c0b469b4a9dad42e50b9552799e62c792402501","datavalue":{"value":{"entity-type":"item","numeric-id":1192209,"id":"Q1192209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"461fe2aa8fdd3b3f040e9e7b5df5893d79dae0fc","datavalue":{"value":{"amount":"+0.7909113764762878","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":"Q5940927$F0239C4D-1924-466F-AAD0-68EC8E01C793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a92ca8268c4c270c00363bf4f60b3d47109985e","datavalue":{"value":{"entity-type":"item","numeric-id":1854400,"id":"Q1854400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ca39fc02288aa11a54be1ed11383777fc8412ec","datavalue":{"value":{"amount":"+0.7471377849578857","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":"Q5940927$889A8FDE-CF6C-40EE-86CA-C9B26DF596D5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5940927","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5940927"}}}}}