{"entities":{"Q800103":{"pageid":801951,"ns":120,"title":"Item:Q800103","lastrevid":64432080,"modified":"2026-04-11T19:50:08Z","type":"item","id":"Q800103","labels":{"en":{"language":"en","value":"Acyclic join dependency and data base projections"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3876646"}},"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":"Q800103$45857C3B-EB91-426A-8293-3A1969D72B88","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ffdb7df060606905d84b1e25aa64787714cd967b","datavalue":{"value":{"text":"Acyclic join dependency and data base projections","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q800103$8F20A725-A58D-4584-83CE-2100AAF7E662","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7f2cbdd4f418e37a4119945e9a136599c039e987","datavalue":{"value":"0549.68092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800103$0F24A3B3-8D17-47B4-A06B-1BE9F5D0A08F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2a4686cb9a4387b95128b95073fd28297a435007","datavalue":{"value":"10.1016/0022-0000(83)90046-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800103$489623F2-69D4-48F9-9DA1-2C0D00EEF20C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0895c8b11e4a5feeab0d62b73df2f7d36cadce36","datavalue":{"value":{"entity-type":"item","numeric-id":686643,"id":"Q686643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800103$345D7833-139E-4A6D-826E-D325EF117A85","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800103$AFCFE30A-22A1-448A-8AD1-7D51791F973F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q800103$0D16DD52-392B-4594-AE2E-072A45D3AC90","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"086f846fba4fffbc29f274a87a4611cc9ddb04e6","datavalue":{"value":"In the presence of a join dependency \\(*[R_ 1,R_ 2,...,R_ k]\\) over relation scheme U, a relation I(U) can be faithfully represented by the database of projected relations \\(d=\\{r_ 1,r_ 2,...,r_ n\\},\\) where \\(r_ i=\\pi_{R_ i}(I).\\) The question addressed in this paper is how to compute efficiently a projection \\(\\pi_ X(I)\\) directly from the relations in d. The computations considered are joins of projections of relations in d, and ''efficiency'' means minimizing the number of joins. Permitting projections of relations in d, rather than simply the relations themselves, sets this work apart from that of \\textit{M. Yannakakis}, who independently obtained similar results [Proc. 7th int. Conf. Very Large Databases, Cannes, 82-94 (1981)]. The paper gives a sufficient condition on a set of projections of relations in d for computing \\(\\pi_ X(I)\\). Using an alternative definition of acyclic database scheme based on structured edge-trees the author shows the sufficient condition is also necessary if \\(\\{R_ 1,R_ 2,...,R_ n\\}\\) is an acyclic database scheme. The alternative definition of acyclic database scheme is also used to derive a modified Graham reduction procedure that will determine which projections of relations in d are needed to compute \\(\\pi_ X(I)\\), given X.","type":"string"},"datatype":"string"},"type":"statement","id":"Q800103$F0F69129-B031-4F5D-ACFA-DC99E181953D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800103$DA7104D2-A7CA-49D5-8954-32D55D5EDD7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800103$35EA5FBF-E9BD-49BF-8014-2F2DBC5A0517","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b5f51ae9029e6a5304449bb2ed192fd393ac606d","datavalue":{"value":"3876646","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800103$E51C9FF6-B88F-4975-976F-ACB506833278","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"74473800caa00ca2354e3822045142f9adaae316","datavalue":{"value":"relational database","type":"string"},"datatype":"string"},"type":"statement","id":"Q800103$68569208-BF1E-4065-AAC2-28F516BD7CC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98b5c69077767dca9455fde1b0c184a2375b27a8","datavalue":{"value":"universal instance","type":"string"},"datatype":"string"},"type":"statement","id":"Q800103$9D42E6F4-8A36-458F-B7FF-54B04F8A2240","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"17d7a647ac9fad1ecd9e732102ebf5ea39a608ef","datavalue":{"value":"database decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q800103$C4719551-09BA-4F7F-9C4A-75DF98F62463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"320bfdfe89579b7b52fce9feb7995ef007666a3f","datavalue":{"value":"join dependency","type":"string"},"datatype":"string"},"type":"statement","id":"Q800103$DAF56892-2689-4E52-9DF9-AC2302E4641A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64188b084e3b3609d8e97194d06630def85452bd","datavalue":{"value":"relation scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q800103$C40946EB-11C0-4248-A3E8-CFBFDA934A7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67cfd41e10382af7426a840acc8483340d5ca343","datavalue":{"value":"projections of relations","type":"string"},"datatype":"string"},"type":"statement","id":"Q800103$DE7080ED-D6E8-4DFE-AFF1-6DB411AAD16C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"73fc5c6061d00fa4485abcaad241897d6533d913","datavalue":{"value":"acyclic database scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q800103$AA786843-E098-4762-BE20-AF8DA3EC3A33","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":"Q800103$33766218-4E1B-459F-B70F-FF88C01B235C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"09493a1a2a5ed62c8f18001f5aedb8d0046c698d","datavalue":{"value":"https://doi.org/10.1016/0022-0000(83)90046-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q800103$9DD4F39E-0344-44D8-A010-8280A9BD4C92","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c6193c81bd4cfbec107a15c17d971ba1470fa62e","datavalue":{"value":"W2001476721","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800103$71155664-9FBD-4E64-B1C5-6197A3FAB68E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"40de328e4ef0bb002df5ae148f526335f6b1b92d","datavalue":{"value":{"entity-type":"item","numeric-id":4199525,"id":"Q4199525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800103$B1297D28-ECB9-41B3-A151-1347356761B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a08cfcc5870263a5c9ca63fbdf30de9c21f5aec","datavalue":{"value":{"entity-type":"item","numeric-id":3026382,"id":"Q3026382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800103$B64A0600-4EA7-40D9-B3D9-1CCC33655F59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df8aeb37c7c980e88c1d1fff0a4cf9d1a112c191","datavalue":{"value":{"entity-type":"item","numeric-id":3925900,"id":"Q3925900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800103$EF621A87-F890-4665-9617-2671D582A7B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800103$BDC2E883-1319-42E3-BCD4-00225BA97841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7c6781735c13ab5b80904660a67e47129b757f4","datavalue":{"value":{"entity-type":"item","numeric-id":3950001,"id":"Q3950001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800103$69A6B74B-A40C-4DE5-AF17-706DA499BE3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1de4efb549c5ae704987aeb0480dc76e0061a43e","datavalue":{"value":{"entity-type":"item","numeric-id":3956441,"id":"Q3956441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800103$2D05C209-A3EE-40C4-B094-8C24C9EE084F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82f3011214be1c865bb51d01938bc5eb984acc83","datavalue":{"value":{"entity-type":"item","numeric-id":762180,"id":"Q762180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800103$E7D8A7E1-A7DC-4BB5-99A4-7E3B2B2F85BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44bc767850337e21a183ed9e8b9103abf049f928","datavalue":{"value":{"entity-type":"item","numeric-id":3206351,"id":"Q3206351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800103$B6C7ABBC-6682-4FA6-ACF7-73E6F28BE5E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d7fa36060b3e6075ae48a810399ee41c40b682a","datavalue":{"value":{"entity-type":"item","numeric-id":3339330,"id":"Q3339330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800103$6015E607-AD92-4D73-B677-F3A5AB2C8869","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b36191f63b95063586227147d04080c6cc52a225","datavalue":{"value":{"entity-type":"item","numeric-id":3026382,"id":"Q3026382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ff683d13fd3bc68c8090c3391e481ac683e01cf","datavalue":{"value":{"amount":"+0.8345233201980591","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":"Q800103$85F85710-4A23-4AEB-B6D6-7AA66713B5E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bc7c2c96653ed9d3edc452cc49b9b710ade5d52","datavalue":{"value":{"entity-type":"item","numeric-id":1123019,"id":"Q1123019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5835d7917200c10ce064d7744ad177d356e6e419","datavalue":{"value":{"amount":"+0.8137511610984802","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":"Q800103$B488AFF8-97F6-47E3-B3CE-6CC318CD849F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52d266bc31bcaf481b16e35ef3748be56d42ccd4","datavalue":{"value":{"entity-type":"item","numeric-id":3735098,"id":"Q3735098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"169b9ba6ff951ed518635e02a85bbf85b651ad52","datavalue":{"value":{"amount":"+0.8101009130477905","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":"Q800103$030C77F6-4222-4116-A4BA-857FE1D862F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07f95965f5c6a8a947b7264f634e75c654d8b8ad","datavalue":{"value":{"entity-type":"item","numeric-id":3738613,"id":"Q3738613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07897ce6d56889edb5e51953ad4f923f2221584d","datavalue":{"value":{"amount":"+0.7998660206794739","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":"Q800103$555B761B-C8A7-4AE9-B11F-EB30347A4787","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a8ca30f33fc946078fff88f75b9f259012e4f75","datavalue":{"value":{"entity-type":"item","numeric-id":582944,"id":"Q582944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"040f5af89073260a2717f803aa3750860a4b17ed","datavalue":{"value":{"amount":"+0.7895945310592651","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":"Q800103$88CB984B-E0B2-4B9A-A71A-E7CAC9F5A52D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Acyclic join dependency and data base projections","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Acyclic_join_dependency_and_data_base_projections"}}}}}