Functional Dependencies

From BITPlan Wiki
Jump to navigation Jump to search

Notation

In Database theory: [math]\{A,B\}\to \{C,D\}[/math] is abbreviated to: [math]AB\to CD[/math]

Simple hierarchical Example

9 single entries for 2022 sorted by social media followers

SPARQL query

try it!

result as of 2022-06-13

A B C D E F G H I J
single language collectionId collection collectionType performerId performer followerCount youtubeVideoId publicationYear
Let Somebody Go English http://www.wikidata.org/entity/Q107597380 Music of the Spheres album http://www.wikidata.org/entity/Q83287 Selena Gomez 65629044 EptPhiK_q0E 2022
As It Was English http://www.wikidata.org/entity/Q111343757 Harry's House album http://www.wikidata.org/entity/Q3626966 Harry Styles 36156370 H5v3kku4y6Q 2022
Let Somebody Go English http://www.wikidata.org/entity/Q107597380 Music of the Spheres album http://www.wikidata.org/entity/Q45188 Coldplay 23541189 EptPhiK_q0E 2022
Bam Bam English http://www.wikidata.org/entity/Q56071495 Camila Cabello singles discography singles discography http://www.wikidata.org/entity/Q47447 Ed Sheeran 17661915 -8VfKZCOo_I 2022
Bam Bam English http://www.wikidata.org/entity/Q111083420 Familia album http://www.wikidata.org/entity/Q47447 Ed Sheeran 17661915 -8VfKZCOo_I 2022
Sacrifice English http://www.wikidata.org/entity/Q110400486 Dawn FM album http://www.wikidata.org/entity/Q2121062 The Weeknd 15549868 VafTMsrnSTU 2022
Out of Time English http://www.wikidata.org/entity/Q110400486 Dawn FM album http://www.wikidata.org/entity/Q2121062 The Weeknd 15549868 2fDzCWNS3ig 2022
Bam Bam English http://www.wikidata.org/entity/Q56071495 Camila Cabello singles discography singles discography http://www.wikidata.org/entity/Q18810940 Camila Cabello 12717885 -8VfKZCOo_I 2022
Bam Bam English http://www.wikidata.org/entity/Q111083420 Familia album http://www.wikidata.org/entity/Q18810940 Camila Cabello 12717885 -8VfKZCOo_I 2022

Functional Dependencies

The functional dependencies in this example are derived from the structure of the SPARQL query

  • A≡single
  • B≡language
  • C≡collectionId
  • D≡collection
  • E≡collectionType
  • F≡performerId
  • G≡performer
  • H≡followerCount
  • I≡youtubeVideoId
  • J≡publicationYear
  • [math]A\to BCFIJ[/math]
  • [math]C\to DE[/math]
  • [math]F\to GH[/math]

[math]R={{\{A,B,C,D,E,F,G,H,I,J\}},{A\to BCFIJ,C\to DE,F\to GH}}[/math]

functional dependencies diagram

The following diagram shows the functional dependencies of this example. The nodes represent the attributes and the edges the dependencies.

Attribute Closures

The attribute closure is the set of all attributes that are "reachable/determinable" from a given attribute node. In this example the results are quite obvious since the functional dependencies form a tree and the reachable nodes are all nodes of the subtree of a given attribute.

attribute closure
A ABCDEFGHIJ
B B
C CDE
D D
E E
F FGH
G G
H H
I I
J J

Keys for the example

There is only a single candidate key: A≡single

It is the only attribute that has the full set of attributes as it's closure. A≡single is also a super key and primary key

With a slightly modified query we'll see that wikidata uses a surrogate key as the primary key for all items. Querying Wikidata's graph data more often than not leads to results that need to be normalized to be useful in the context of relational databases.

Extending the above query with a column for the wikidata Id of the single shows how the surrogate key is related to the single entries.

9 single entries for 2022 sorted by social media followers with wikidata Id link

query

try it!

result

singleId single language collectionId collection collectionType performerId performer followerCount youtubeVideoId publicationYear
http://www.wikidata.org/entity/Q108914561 Let Somebody Go English http://www.wikidata.org/entity/Q107597380 Music of the Spheres album http://www.wikidata.org/entity/Q83287 Selena Gomez 65629044 EptPhiK_q0E 2022
http://www.wikidata.org/entity/Q112316936 Skin of My Teeth English http://www.wikidata.org/entity/Q112270102 Holy Fvck album http://www.wikidata.org/entity/Q41173 Demi Lovato 54350780 HgrC_h8-2FM 2022
http://www.wikidata.org/entity/Q112317311 Yet to Come (The Most Beautiful Moment) English http://www.wikidata.org/entity/Q111849557 Proof album http://www.wikidata.org/entity/Q13580495 BTS 45300000 kXpOEzNZ8hQ 2022
http://www.wikidata.org/entity/Q112317311 Yet to Come (The Most Beautiful Moment) Korean http://www.wikidata.org/entity/Q111849557 Proof album http://www.wikidata.org/entity/Q13580495 BTS 45300000 kXpOEzNZ8hQ 2022
http://www.wikidata.org/entity/Q111397510 As It Was English http://www.wikidata.org/entity/Q111343757 Harry's House album http://www.wikidata.org/entity/Q3626966 Harry Styles 36156370 H5v3kku4y6Q 2022
http://www.wikidata.org/entity/Q112075432 Late Night Talking English http://www.wikidata.org/entity/Q111343757 Harry's House album http://www.wikidata.org/entity/Q3626966 Harry Styles 36156370 RwT77rlp2CE 2022
http://www.wikidata.org/entity/Q112317311 Yet to Come (The Most Beautiful Moment) English http://www.wikidata.org/entity/Q111849557 Proof album http://www.wikidata.org/entity/Q13580495 BTS 27300000 kXpOEzNZ8hQ 2022
http://www.wikidata.org/entity/Q112317311 Yet to Come (The Most Beautiful Moment) Korean http://www.wikidata.org/entity/Q111849557 Proof album http://www.wikidata.org/entity/Q13580495 BTS 27300000 kXpOEzNZ8hQ 2022
http://www.wikidata.org/entity/Q108914561 Let Somebody Go English http://www.wikidata.org/entity/Q107597380 Music of the Spheres album http://www.wikidata.org/entity/Q45188 Coldplay 23541189 EptPhiK_q0E 2022

Normal forms

1st Normal Form

2nd Normal Form

3rd Normal Formm

Boyce Codd Normal Form

Synthesis

Links

Wikipedia

The following graph shows some relevant wikipedia articles. If the nodes are not clickable in your browser you might want to open the svg image in a separate tab to get a clickable version of this graph.

Other