{"entities":{"Q303689":{"pageid":305456,"ns":120,"title":"Item:Q303689","lastrevid":60781434,"modified":"2026-04-10T19:06:17Z","type":"item","id":"Q303689","labels":{"en":{"language":"en","value":"Optimal covers in the relational database model"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6618614"}},"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":"Q303689$EDFA613D-DB86-4875-8670-756E815DF721","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1e6f145bec98b100edb90decd42a6881de5ff522","datavalue":{"value":{"text":"Optimal covers in the relational database model","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q303689$9A26C00D-7785-4EE9-AF39-6F9CB2BA8140","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"61655555f4134b44e2e8dd8ed8ea31ff2826a71f","datavalue":{"value":"1347.68112","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303689$C2C465F0-6CAA-447D-9C54-A5EBBC2C6F7D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"28c97064cd75d0e706019737b183bb2abab523ef","datavalue":{"value":{"entity-type":"item","numeric-id":303687,"id":"Q303687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303689$F02B6E3A-B9DD-4AAE-BA55-DE4FCA4BE5C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"862951ed17214b7befcb117d95c870c04ef52e09","datavalue":{"value":{"entity-type":"item","numeric-id":303688,"id":"Q303688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303689$BC91DA22-BCDA-4E7A-BDF4-2F2DE42363E9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303689$63F7C076-55A5-429F-AB98-12B6D4B53A56","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70e273fe9462a734f2d1ac8ce28702f050bb6f4b","datavalue":{"value":{"time":"+2016-08-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q303689$86780127-13CA-4A9C-86E0-6B20302DE8F2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cf6f73a03e0016c26bbfaaaf355ac8beaf87989f","datavalue":{"value":"Functional dependencies (FD) belong to very important integrity constraints of the relational database model.  Their theoretical problems were studied mainly in the 80s and they are still a challenge for some researches.  The paper is focused on finding an optimal cover for a set of FDs, which is an NP-complete problem.  The authors of the paper show that an optimal cover can be found, using the notion of mini-cover.  The paper's content is divided into five sections.  Section 1 presents some important concepts and background concerning FDs and optimal covers.  Section 2 introduces the notions of mini-cover and minimum Boolean expression.  The latter contributes to finding mini-covers using the transformation of the output of a Boolean expression minimization algorithm.  Section 3 introduces the notion of minimum cover, defined by \\textit{D. Maier} in [J. Assoc. Comput. Mach. 27, 664--674 (1980; Zbl 0466.68085)], including an algorithm, \\(\\mathrm{MINIMIZE}(G)\\), to compute a minimum cover of a set \\(G\\) of FDs.  Section 4 starts with introducing the notion of derivation sequence [\\textit{D. Maier}, The theory of relational databases. London: Pitman Publishing Limited (1983; Zbl 0519.68082)], which allows one to prove that an optimal cover can be found using the mini-cover as the input of \\(\\mathrm{MINIMIZE}(G)\\).  The theoretical analysis of the algorithm's complexity is not conducted in this paper.  Section 5 presents some conclusions.  The paper is written at a sufficiently formal level, it is completed by many examples illustrating the used notions.  It gives a meaningful contribution to extending the theory of FDs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q303689$F21BBA75-37AD-4859-9C8D-AD00E287D5C3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"41927d0273d17be217af24d3bf572ac62623d210","datavalue":{"value":{"entity-type":"item","numeric-id":590760,"id":"Q590760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303689$A544E204-523B-4693-84F0-7ACCF7D690EA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf2726c5c2109371cc10358eaa69bc4df711caf7","datavalue":{"value":"68P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303689$A404EF5D-3174-4820-B443-197A3A7B1FF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"674153c9488f8b0f9e97858664bfaf3fbbbac9b1","datavalue":{"value":"03G05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303689$DBDF6F8B-3405-425F-9B91-5A0658EBB789","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"12a5c59728f3c5e5748c1e1d9897d5dbd10a0bed","datavalue":{"value":"6618614","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303689$0BE1A416-D88A-4C72-9E3A-A28A53A9AD2B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c1cdec68f6f531065eeae64be8360df19d70183","datavalue":{"value":"functional dependency","type":"string"},"datatype":"string"},"type":"statement","id":"Q303689$8737C0A8-D01E-4187-B96E-86AAA777BD5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f10b685c594a9928a58771b933c97ee78f7cd27f","datavalue":{"value":"optimal cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q303689$4C68553F-2C4D-4E5F-B04C-CB5DC85B809B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f1d78b2f72e01463d8d42ef539a628d50aa5832","datavalue":{"value":"mini-cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q303689$D2385D68-DA5E-4A11-8696-98E615C0F075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5fdd57397953b197a7a731c5d8c94e730b1def40","datavalue":{"value":"minimum cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q303689$5F99AA54-B0C7-4513-A3CA-ECCD5E5DA269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd65c3344f2aaff120ffb0879e06a9b8f59b491b","datavalue":{"value":"minimum Boolean expression","type":"string"},"datatype":"string"},"type":"statement","id":"Q303689$4E7D5C41-99E8-4A61-9536-F140CA8D10C6","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":"Q303689$0F60CF30-850F-4BC7-B026-392B8EBE50A0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fd2568bd69858645d8ac3b9ce768f95f3e95d22b","datavalue":{"value":"https://doi.org/10.1007/s00236-015-0247-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q303689$0AEB4675-A0FB-484D-AC02-437313EA8298","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"11de18a35a5bc6df2a87bb84fdf1c4d5bae07635","datavalue":{"value":"W1908227512","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303689$9E4EFA74-EE8B-4692-9251-270CCCF15F96","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a3e052346b3e42c07257c51858e7ff99f9837","datavalue":{"value":{"entity-type":"item","numeric-id":3738576,"id":"Q3738576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303689$834AF49D-1D79-46DB-9F2F-2E0BB73B54B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8320858fd267bbcd8a8748fa0ea0f11829d10dd","datavalue":{"value":{"entity-type":"item","numeric-id":3026384,"id":"Q3026384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303689$99B0E2F5-E3CE-45C6-862F-5D1B516DC0AC","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":"Q303689$59AE2D32-81BE-40B9-B897-FA6398F598D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee50e4d9230b707f8144bdca5d10740b54dd6dc6","datavalue":{"value":{"entity-type":"item","numeric-id":5674969,"id":"Q5674969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303689$9B8B708A-A3B4-4F0D-B3C8-E815A98BACA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45d82df60ca984fa15e75d19fe33058c8e298ba4","datavalue":{"value":{"entity-type":"item","numeric-id":4142680,"id":"Q4142680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303689$74911E67-54D8-4B26-8ECC-E10C0FAE8FB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c8b2577eba1e6a6cfb65bda23e01f7bd4110717","datavalue":{"value":{"entity-type":"item","numeric-id":1253096,"id":"Q1253096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303689$B8924341-3424-46A9-896C-E926930BF1D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e00dbe049ef694ddf89bda4540748d3bb56f13be","datavalue":{"value":{"entity-type":"item","numeric-id":3919121,"id":"Q3919121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303689$34D76F5A-C60F-4B75-A1DE-DD76509D3700","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"143421a0cbe4ba34cedbed6f5fa70d101952a550","datavalue":{"value":{"entity-type":"item","numeric-id":3668890,"id":"Q3668890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303689$95F98FAA-EBE2-4EBE-9982-0F45EBC6DC8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2e00d91d6354f3c423a4f51e7bfbc970d637fe1","datavalue":{"value":{"entity-type":"item","numeric-id":1836314,"id":"Q1836314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q303689$29E274D9-51F6-49F1-9315-7D862678C358","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fe0c51b34a27c7725000c74e74e3a50f8f9aef7a","datavalue":{"value":"10.1007/S00236-015-0247-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q303689$D3507891-E070-4B6F-8124-B4584603E88F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a4155ef160df6ad0b1de7cf6ec474e190224120","datavalue":{"value":{"entity-type":"item","numeric-id":3833663,"id":"Q3833663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"188fef3ad765319feef38277f4ed9c18e6e3f175","datavalue":{"value":{"amount":"+0.86827826","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q303689$55470EF0-F885-4D61-8657-E71C19459A98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02811f4a9651a99c6a5e01ed996b2e107a8aaf94","datavalue":{"value":{"entity-type":"item","numeric-id":1072723,"id":"Q1072723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"546aeadf705df8d14f97188ef25ff3c7e127d747","datavalue":{"value":{"amount":"+0.86068773","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q303689$F4B29230-40E1-4402-A714-C84DBC7E7A4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"581b7c0f340e1f2b89e67b6e0f587d8a140c8906","datavalue":{"value":{"entity-type":"item","numeric-id":918695,"id":"Q918695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"197a8905524288189cc772cb9648aefaaa9bc716","datavalue":{"value":{"amount":"+0.8457216","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q303689$6A1D5B49-85ED-409B-AA7F-9819D25F5072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f597786fe1b54a9270cab3016e673128c43c4fd3","datavalue":{"value":{"entity-type":"item","numeric-id":1108065,"id":"Q1108065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b855e1552ca2fa7ee5d3e1d5c0915357b0a4da19","datavalue":{"value":{"amount":"+0.8345558","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q303689$226407DD-7D7C-4DB7-82E4-C45CEB45D900","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e55878593984453950ecaa314aba80ca20694887","datavalue":{"value":{"entity-type":"item","numeric-id":3792285,"id":"Q3792285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6be72cd532c8c927b22cb8b65646cd0b53adb321","datavalue":{"value":{"amount":"+0.8303265","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q303689$3442060F-E5FD-4C8D-978E-F634AC66CC3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4be528ef772dd09183db1b4c5f84d6dd6e6b6a06","datavalue":{"value":{"entity-type":"item","numeric-id":4955319,"id":"Q4955319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50edcca2bed96ddff52dbd3856e9af809b1f5f26","datavalue":{"value":{"amount":"+0.8165076","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q303689$E7323ACF-8701-4928-AF02-3C23E5A78F64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ae5a8dba6f609e0a05f2b5d43c42945b863e975","datavalue":{"value":{"entity-type":"item","numeric-id":3361879,"id":"Q3361879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1656be78cebb604940ee7bcf95d0375b037c2a4d","datavalue":{"value":{"amount":"+0.80766845","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q303689$9C83D79D-806B-4239-B79F-0E3899831EE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6819b6ce17e80b616d6f953dbf7b3ed84db556b","datavalue":{"value":{"entity-type":"item","numeric-id":4535566,"id":"Q4535566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82506060e14349e3010700a9edd0fe032ed7f96e","datavalue":{"value":{"amount":"+0.7981961","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q303689$05B29119-E19D-41E4-B826-E25692E5BA31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"056fcb1c6756d14da5e037ec29edcf0837c6976e","datavalue":{"value":{"entity-type":"item","numeric-id":4733444,"id":"Q4733444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f4fa6e3aaa1df47ad6a56670a5c34b963fb44bb","datavalue":{"value":{"amount":"+0.7855668","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q303689$80B65C5E-C47C-483F-88A3-3209A43E6E0D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal covers in the relational database model","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Optimal_covers_in_the_relational_database_model"}}}}}