{"entities":{"Q1060030":{"pageid":1061878,"ns":120,"title":"Item:Q1060030","lastrevid":66056541,"modified":"2026-04-12T07:14:46Z","type":"item","id":"Q1060030","labels":{"en":{"language":"en","value":"On the existence of acyclic views in a database scheme"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3905880"}},"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":"Q1060030$2F8C6377-D310-45F3-9EFB-4D4E7725B8C3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eb6ba1d1e38a77eefba07c6b0952187b03710ee9","datavalue":{"value":{"text":"On the existence of acyclic views in a database scheme","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1060030$DA4B9EBA-E270-4432-A5BE-7D2C60F6F562","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0c22c45aede928acc6e79b124bd12c4e4f665f35","datavalue":{"value":"0567.68061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060030$654D09AA-CEFA-4F18-A7AC-DFDB1B2D34BA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"baf2e6fc15b9ca24bd30218671da712b97ec75bd","datavalue":{"value":"10.1016/0304-3975(85)90012-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060030$665A9D46-EA6A-4DB2-8A27-F517BC75623F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c86f894860ed1ad30e38407d744d07b5dc06b89","datavalue":{"value":{"entity-type":"item","numeric-id":289923,"id":"Q289923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060030$296EDC12-BF26-4EB9-94BE-8DB3F90D6018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"074bce08c67c0d5d1b4b67e8ed0bf2ee6fe88024","datavalue":{"value":{"entity-type":"item","numeric-id":266843,"id":"Q266843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060030$3D5611A4-A4CC-4394-9A7C-8E67885CAE06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c6fe51a3a505947d9c3637e9128c86cd04a80258","datavalue":{"value":{"entity-type":"item","numeric-id":579963,"id":"Q579963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060030$1A5E5BC9-7EB2-425B-AD0D-94115E460211","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":"Q1060030$43BAE25D-D2DF-4DF0-B809-83BD941B7738","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1060030$19A59880-F63B-4903-AF9D-4E6D78B3939D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7237b747e1ea0151ac0537902564843c4778b064","datavalue":{"value":"The importance of acyclic database schemes in relational database theory has been pointed out in various contributions in the literature. Unfortunately, the realm of interest which is captured by the database scheme is often intrinsically cyclic; therefore, we are faced with the problem of finding acyclic views on such a scheme. In this paper we consider three kinds of acyclicity, called \\(\\alpha\\)-, \\(\\gamma\\)- and Berge-acyclicity by Fagin (1983), and we approach the problem of the existence of acyclic views in a database scheme. We show that the problem of deciding whether there exists a Berge-, \\(\\gamma\\)-, or \\(\\alpha\\)-acyclic view in a general database scheme is NP-complete and that the problem of deciding whether there exists a Berge- or \\(\\gamma\\)-acyclic view on an \\(\\alpha\\)-acyclic scheme is also computationally intractable. On the other hand, if the given database scheme is \\(\\gamma\\)-acyclic, the problem of deciding the existence of a Berge-acyclic view may be solved by means of efficient algorithms which may also be used to find an acyclic view which involves the minimum number of relations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060030$3BDD58E0-C2D2-4C45-8E83-2EAC105BB3E4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060030$41D36739-D217-476E-9031-A663B3A7C406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060030$AFE3298D-384B-4BB5-A44D-BADD363E4BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060030$5A4A4E6E-A904-4EBF-B14F-39E5FEF7ACFB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4d138172fe639c46df5ecb41961cf9b168090296","datavalue":{"value":"3905880","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060030$C9234F01-C088-4F59-9BF9-3639EA82A88D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b033181b2307ec3549055d9e429ebc6440a014b7","datavalue":{"value":"universal relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060030$52CFAC5F-38C9-41D4-A899-94D9A31892AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060030$9E4E98F2-F14C-4F3D-9BFE-D653801EAB84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5554a0e713fa3b7d56bd42bb751f27a1a39ce1d1","datavalue":{"value":"acyclic database schemes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060030$013ECB71-94B5-4EC6-A834-319A956FF365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"74473800caa00ca2354e3822045142f9adaae316","datavalue":{"value":"relational database","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060030$86C3BA31-B3E3-488D-8D76-9CE143D8C3D6","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":"Q1060030$9269A059-65EF-47A9-8ED6-750F9DECBAB4","rank":"normal"}],"P223":[{"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":"Q1060030$B7D9720A-3B2E-4EA9-9125-3C48FC5D2559","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060030$A121E56B-F2BF-4E65-9E8A-5FC428ACD192","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e95eaddd41b158e3a994e5e6b7abb09feb37f31c","datavalue":{"value":{"entity-type":"item","numeric-id":3309102,"id":"Q3309102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060030$77920419-DEDE-492B-BE3A-7DC0DC3BA591","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbf60b8621d856d80efdab97a0a055b9b53fa164","datavalue":{"value":{"entity-type":"item","numeric-id":3026383,"id":"Q3026383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060030$402246CD-FA61-4597-8825-7918EAD111D6","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":"Q1060030$EB8EFED2-60CA-4A90-9CB7-D3755ABD13D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060030$BABEEACD-CA0D-46F7-9F9B-F8C42E8DFD9C","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":"Q1060030$37E7DBF5-259B-45E5-9F90-D33AED073FF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15441b50dad22a5bfaccac6ef09461d0c86d9033","datavalue":{"value":{"entity-type":"item","numeric-id":3321499,"id":"Q3321499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060030$F0A59F4A-839E-4267-9E19-0C7B38094818","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b8793493983ef79387cdf9085bcee0c585bc4d0","datavalue":{"value":{"entity-type":"item","numeric-id":3347338,"id":"Q3347338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060030$037101C5-7D02-4513-9475-DF57B75284E7","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":"dfe09f1d3ada7ddb7721b0dc02307cfdbc7b2217","datavalue":{"value":{"amount":"+0.8574223518371582","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":"Q1060030$B7A12618-0989-43E8-ACCB-EC6CB51EF3BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c96872211591c8d2052f09c6097521050e1a3e3","datavalue":{"value":{"entity-type":"item","numeric-id":3026383,"id":"Q3026383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a26053fe1b58c96ff6d722d48772ad27117dd15","datavalue":{"value":{"amount":"+0.8342058062553406","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":"Q1060030$94925A18-4C4E-4056-919D-C83061B6BF39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a7610affac12f58a8f9f8c805bec5e3000aa75a","datavalue":{"value":{"entity-type":"item","numeric-id":3216158,"id":"Q3216158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfe79d879b4fc3bd1a1956a4487e3b04f32c24a3","datavalue":{"value":{"amount":"+0.8288329839706421","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":"Q1060030$1BA7872F-2A9C-490E-9C67-41E1B7B495A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67af65665941fbe186950ede5029afe2f7d62024","datavalue":{"value":{"entity-type":"item","numeric-id":4870290,"id":"Q4870290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c3fb6952ed4ca64af5e8b730fa0f47fbf20ee91","datavalue":{"value":{"amount":"+0.8166468739509583","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":"Q1060030$5A93062D-5DB2-44D2-9A17-D34C97A3569A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18917528288d8c1e550632d9a83b84e7e0622303","datavalue":{"value":{"entity-type":"item","numeric-id":3775009,"id":"Q3775009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"644d7ede398b07c528a877826167d603435f3db1","datavalue":{"value":{"amount":"+0.8057020902633667","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":"Q1060030$8E1A243F-4156-4402-91B4-280622B5B48D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the existence of acyclic views in a database scheme","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_existence_of_acyclic_views_in_a_database_scheme"}}}}}