{"entities":{"Q1069712":{"pageid":1080464,"ns":120,"title":"Item:Q1069712","lastrevid":66786618,"modified":"2026-04-12T12:51:09Z","type":"item","id":"Q1069712","labels":{"en":{"language":"en","value":"Characterizations for functional dependency and Boyce-Codd normal form families"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3936553"}},"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":"Q1069712$2948A420-A282-4561-AB93-F02B1C204474","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7c53cd7658351c14b94267395c8fb41ef3125fd5","datavalue":{"value":{"text":"Characterizations for functional dependency and Boyce-Codd normal form families","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1069712$63C9405C-5DAE-471C-AE99-E377BC9F11C0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b6bed802732618c33fb7b591d4cbc0a7b808f9f5","datavalue":{"value":"0584.68096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069712$79008BD1-6B8D-4D5D-B5AA-42BCAA617932","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d8f80a93ced9f5eb1292d2cd9f8a7c6ecd399b18","datavalue":{"value":"10.1016/0304-3975(83)90019-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069712$4BDA4111-165C-4822-83D9-853A16A80912","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"af8e35b2904b25db6525196fe93da20de9119727","datavalue":{"value":{"entity-type":"item","numeric-id":578942,"id":"Q578942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069712$4E75A310-22EF-4058-8420-FC904D32F857","rank":"normal"},{"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":"Q1069712$36375A4B-8984-4AD8-BFD5-936A73D387C1","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":"Q1069712$8668225F-C3B7-410E-B945-D4851DF0802B","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":"Q1069712$4C427C99-EB22-4E46-8297-7F21AD1525D2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"028f9ca5230c071f906ee836ae6d63e40b91f5ba","datavalue":{"value":"A functional-dependency family (fd-family) is the set of all instances of a relation that satisfy a given set of functional dependencies \\(\\Gamma\\) and is denoted SAT(\\(\\Gamma)\\). A Boyce-Codd-Normal-Form family (BCNF- family) is an fd-family for a set \\(\\Gamma\\) of key functional dependencies. The paper explores characterizations and closure properties of fd- and BCNF-families. The two main tools for the exploration are closed sets of attributes and agreement sets for collection of instances. A set of attributes X is closed under dependencies \\(\\Gamma\\) if X functionally determines no other attributes. \\({\\mathcal C}(\\Gamma)\\) is all the closed sets for dependencies \\(\\Gamma\\). The agreement set Ag(\\({\\mathcal I})\\) for a set of relation instances \\({\\mathcal I}\\) contains all sets of attributes on which some pair of tuples in some relation instance in \\({\\mathcal I}\\) agree.    The first group of results relate closure sets and agreement sets. A key result is that the agreement sets for an fd-family are the closed sets of that family's dependencies: \\(Ag(SAT(\\Gamma))={\\mathcal C}(\\Gamma)\\). The authors also study the smallest fd-family containing an arbitrary set of instances \\({\\mathcal I}\\), denoted \\({\\mathcal F}({\\mathcal I})\\). That fd-family can be characterized in terms of Ag(\\({\\mathcal I})\\) closed under intersection. A similar characterization is shown for BCNF-families, but there Ag(\\({\\mathcal I})\\) is closed under subset.    The authors next turn to generating \\({\\mathcal F}({\\mathcal I})\\) by closure of \\({\\mathcal I}\\) under operations of instances. For fd-families, the necessary operations are subset of an instance, one-to-one renaming of values in an instance, a restricted type of union and partially disconnected augmentation, which adds a tuple of a restricted form to an instance. If \\({\\mathcal F}({\\mathcal I})\\) is constrained to be a BCNF-family, the restrictions on the tuple in the last operation are changed slightly.    The remainder of the paper discusses when the image of fd-families under a relational algebra operator (or the inverse of an operator) is another fd-family. Closure properties under algebraic operators are useful knowledge for determining the dependencies the answer to a query must satisfy, given the dependencies on the relations being queried. Inverse projection prserves fd-families, but not BCNF-families, while the inverse of a restricted form of projection preserves both. The authors also show how to generate any fd-family or BCNF-family from a finite set of instances using inverse projections and intersection.    The most significant results in the paper concern closure under projection. Here, the greatest difference between fd-families and BCNF- families comes out: BCNF-families are preserved under projection while arbitrary fd-families are not. The authors also characterize when the projection of an fd-family is another fd-family, and that characterization provides a decision procedure. Unfortunately, the proofs in this section of the paper depend on the recursively defined relation on tuples that has an almost impenetrable semantics. The authors acknowledge a connection of their relation with tableau operations, a more facile abstraction, and would have greatly aided readers by adopting the latter for their development.    The final results of the paper give BCNF-versions of closure properties of fd-families under join and union.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069712$B64690C3-310C-4E83-890B-8A6B0AB22D20","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069712$29E1321B-683E-40CB-A026-F39C9EF36DCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069712$067DB71D-B244-45D5-B4AE-49555F584895","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4c09ea78484192dfb20180fed0b8ec0fbe50483f","datavalue":{"value":"03D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069712$B1298902-4E15-4676-93FC-E6005F2D7CA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"17763f39d928d56ef4081eb9cbb67fb71c0baf0e","datavalue":{"value":"03E20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069712$2D5A3C52-F677-4A3D-AA87-63EDEF6FD84E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"68fc8ea0b275db2a5db0e59161036988f815bbd8","datavalue":{"value":"3936553","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069712$299D5195-CA58-46EA-B574-7FB37BD05693","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"74473800caa00ca2354e3822045142f9adaae316","datavalue":{"value":"relational database","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069712$47EC4784-698A-49ED-927E-8155E17FA47F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f37a034e647f80843b21640ec1d9b6824b15e6b5","datavalue":{"value":"relational algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069712$78C804D0-3CC6-4631-AB37-A28EAE92B08E","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":"Q1069712$AF4AB960-20E3-4299-9557-5DBBB8508DFD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8d6009c428140585d1ec904dcbafeb35af810691","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90019-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1069712$EAF046D5-D227-4917-BBAB-D5935CA41F64","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"da85ac310add740ec7c3929a25bc8a62904f5877","datavalue":{"value":"W2159869517","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069712$5D01C21D-7666-413D-B6D2-EC28D72C8C4F","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":"Q1069712$BA2928C3-B3C6-42EC-808A-15617F1FA922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"223c5ceee549a94a8ba5c26ff64a6da011e42238","datavalue":{"value":{"entity-type":"item","numeric-id":4050122,"id":"Q4050122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069712$D75D47DF-00F4-412A-839F-07AB97032CF1","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":"Q1069712$D7851D46-2320-46F4-956D-A52DF3BC487A","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":"Q1069712$5032CE49-0DF5-4C32-A25E-720A7A542301","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88091a275fdc1f4c5aea7f91b3337e3696000bf9","datavalue":{"value":{"entity-type":"item","numeric-id":3992694,"id":"Q3992694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069712$7A2DA39C-563B-47C5-AD81-E2279351F157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3eb039d256abc4d7d9b383e6ed71f969c1c4518","datavalue":{"value":{"entity-type":"item","numeric-id":4050126,"id":"Q4050126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069712$8EA36D31-B674-4B79-8B3B-904C22C0B0FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b24a541ac00639598ac3b9e73190baab8921217a","datavalue":{"value":{"entity-type":"item","numeric-id":4162636,"id":"Q4162636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069712$1429F073-D561-4EDA-8A23-8660A5FAB9C9","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":"Q1069712$BB7F60C2-EC63-40F8-AE9C-4F450BFD8E1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bd6c969231e6f49e9de8df2bebdcacfffac1dbf","datavalue":{"value":{"entity-type":"item","numeric-id":3956433,"id":"Q3956433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069712$84473D0F-2D42-4873-8D38-F786FA337536","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88563490af4a3660ead01235121e2c528676d456","datavalue":{"value":{"entity-type":"item","numeric-id":3949997,"id":"Q3949997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069712$F57D4196-2D99-4E84-BE0D-E07DB5181721","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9eea62a86292c8358436d8f446c84d010184c244","datavalue":{"value":{"entity-type":"item","numeric-id":3883573,"id":"Q3883573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069712$8EDF98D3-10FE-4816-99BD-A2A9D5AB21A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b6966e2dcbe5a32a434be40fa566b4aad23501e","datavalue":{"value":{"entity-type":"item","numeric-id":1154819,"id":"Q1154819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069712$F52B570E-2046-411F-A4B3-D553109B5004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef89dbb44b7c37537d3e1e48a97f18f0adc939e6","datavalue":{"value":{"entity-type":"item","numeric-id":3906490,"id":"Q3906490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069712$F0CCA123-2F50-4A2A-A634-6CFE411057E8","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":"Q1069712$0F81D339-EE9C-4310-819E-61213EF65577","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b29a174b4f71ee35e556bfb137ed4a1a5f608b0a","datavalue":{"value":{"entity-type":"item","numeric-id":1346836,"id":"Q1346836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db472ce3a31bc39039e0574fd0d15e7993c2d587","datavalue":{"value":{"amount":"+0.8404453992843628","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":"Q1069712$D25E78BB-B280-4577-BE75-56C99282EDF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4da8e0b6f076e21f3c63ea6457bd7c1d66be55f","datavalue":{"value":{"entity-type":"item","numeric-id":4864790,"id":"Q4864790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db472ce3a31bc39039e0574fd0d15e7993c2d587","datavalue":{"value":{"amount":"+0.8404453992843628","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":"Q1069712$3D61030E-00B8-4610-BE6E-003A2A3DCACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d5ec66fcbce8dbc14b512c989a009c02d4aa640","datavalue":{"value":{"entity-type":"item","numeric-id":4672917,"id":"Q4672917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"349bfec34c22440f4343031e8f11f48fb787e7d1","datavalue":{"value":{"amount":"+0.8023942112922668","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":"Q1069712$6BCB78BA-E055-44CB-BBC7-C01DACC57EB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54d3b11ca4e2358151bef6c2345bfafb90971e3c","datavalue":{"value":{"entity-type":"item","numeric-id":3319796,"id":"Q3319796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9eaa6c986909d750e2e9f4f7bf1a78b86e9abe7c","datavalue":{"value":{"amount":"+0.7988729476928711","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":"Q1069712$A156AAAB-D53E-4E70-8094-28F2365F631C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e194e978069f59f7b44cdf23ee2c5b42166949e3","datavalue":{"value":{"entity-type":"item","numeric-id":1353956,"id":"Q1353956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e71993b44ae62859310e8be373bedcd90ef493d3","datavalue":{"value":{"amount":"+0.7908518314361572","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":"Q1069712$514C3587-60BD-4405-A65E-E8E0173F4708","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Characterizations for functional dependency and Boyce-Codd normal form families","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Characterizations_for_functional_dependency_and_Boyce-Codd_normal_form_families"}}}}}