Functional Dependencies
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
query
# WF 2022-06-08
# Singles published in 2022
SELECT
?single ?language ?collectionId ?collection ?collectionType ?performerId ?performer ?followerCount ?youtubeVideoId (year(?publicationDate) as ?publicationYear)
WHERE
{
# instanceof
?singleId wdt:P31 wd:Q134556. # Must be of a single
?singleId rdfs:label ?single.
FILTER(LANG(?single)='en')
#https://www.wikidata.org/wiki/Property:P361 - part of / ist Teil von
?singleId wdt:P361 ?collectionId.
?collectionId rdfs:label ?collection.
FILTER(LANG(?collection)='en')
# https://www.wikidata.org/wiki/Property:P407 language/ Sprache des Werkes
?singleId wdt:P407 ?languageId.
?languageId rdfs:label ?language.
FILTER(LANG(?language)='en')
# https://www.wikidata.org/wiki/Property:P1651 YouTube-Video-Kennung
?singleId wdt:P1651 ?youtubeVideoId.
?collectionId wdt:P31 ?collectionTypeId.
?collectionTypeId rdfs:label ?collectionType.
FILTER(LANG(?collectionType)='en').
# https://www.wikidata.org/wiki/Property:P175 Performer /Interpret
?singleId wdt:P175 ?performerId.
?performerId rdfs:label ?performer
FILTER(LANG(?performer)='en')
# https://www.wikidata.org/wiki/Property:P8687 followers / Follower
#{
#SELECT (max(?followerCount) as ?follower)
#WHERE {
?performerId wdt:P8687 ?followerCount.
#}
#GROUP BY ?performerId
#}
#https://www.wikidata.org/wiki/Property:P577 Publication date / Veröffentlichungsdatum
?singleId wdt:P577 ?publicationDate.
FILTER(year(?publicationDate) = 2022).
} ORDER BY DESC(?followerCount)
LIMIT 9
result
| 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 |
Candidate Keys
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
= 9 single entries for 2022 sorted by social media followers with wikidata Id link
query
# WF 2022-06-08
# Singles published in 2022
SELECT
?singleId ?single ?language ?collectionId ?collection ?collectionType ?performerId ?performer ?followerCount ?youtubeVideoId (year(?publicationDate) as ?publicationYear)
WHERE
{
# instanceof
?singleId wdt:P31 wd:Q134556. # Must be of a single
?singleId rdfs:label ?single.
FILTER(LANG(?single)='en')
#https://www.wikidata.org/wiki/Property:P361 - part of / ist Teil von
?singleId wdt:P361 ?collectionId.
?collectionId rdfs:label ?collection.
FILTER(LANG(?collection)='en')
# https://www.wikidata.org/wiki/Property:P407 language/ Sprache des Werkes
?singleId wdt:P407 ?languageId.
?languageId rdfs:label ?language.
FILTER(LANG(?language)='en')
# https://www.wikidata.org/wiki/Property:P1651 YouTube-Video-Kennung
?singleId wdt:P1651 ?youtubeVideoId.
?collectionId wdt:P31 ?collectionTypeId.
?collectionTypeId rdfs:label ?collectionType.
FILTER(LANG(?collectionType)='en').
# https://www.wikidata.org/wiki/Property:P175 Performer /Interpret
?singleId wdt:P175 ?performerId.
?performerId rdfs:label ?performer
FILTER(LANG(?performer)='en')
# https://www.wikidata.org/wiki/Property:P8687 followers / Follower
#{
#SELECT (max(?followerCount) as ?follower)
#WHERE {
?performerId wdt:P8687 ?followerCount.
#}
#GROUP BY ?performerId
#}
#https://www.wikidata.org/wiki/Property:P577 Publication date / Veröffentlichungsdatum
?singleId wdt:P577 ?publicationDate.
FILTER(year(?publicationDate) = 2022).
} ORDER BY DESC(?followerCount)
LIMIT 9
[None/#%23%20WF%202022-06-08%0A%23%20Singles%20published%20in%202022%0ASELECT%0A%3FsingleId%20%3Fsingle%20%3Flanguage%20%3FcollectionId%20%3Fcollection%20%3FcollectionType%20%3FperformerId%20%3Fperformer%20%3FfollowerCount%20%3FyoutubeVideoId%20%20%28year%28%3FpublicationDate%29%20as%20%3FpublicationYear%29%0AWHERE%0A%7B%0A%20%20%23%20instanceof%0A%20%20%3FsingleId%20wdt%3AP31%20wd%3AQ134556.%20%23%20Must%20be%20of%20a%20single%0A%20%20%3FsingleId%20rdfs%3Alabel%20%3Fsingle.%0A%20%20FILTER%28LANG%28%3Fsingle%29%3D%27en%27%29%0A%0A%20%20%23https%3A//www.wikidata.org/wiki/Property%3AP361%20-%20part%20of%20/%20ist%20Teil%20von%0A%20%20%3FsingleId%20wdt%3AP361%20%3FcollectionId.%0A%20%20%3FcollectionId%20rdfs%3Alabel%20%3Fcollection.%0A%20%20FILTER%28LANG%28%3Fcollection%29%3D%27en%27%29%0A%0A%20%20%23%20https%3A//www.wikidata.org/wiki/Property%3AP407%20language/%20Sprache%20des%20Werkes%0A%20%20%3FsingleId%20wdt%3AP407%20%3FlanguageId.%0A%20%20%3FlanguageId%20rdfs%3Alabel%20%3Flanguage.%0A%20%20FILTER%28LANG%28%3Flanguage%29%3D%27en%27%29%0A%0A%20%20%23%20https%3A//www.wikidata.org/wiki/Property%3AP1651%20YouTube-Video-Kennung%0A%20%20%3FsingleId%20wdt%3AP1651%20%3FyoutubeVideoId.%0A%0A%20%20%3FcollectionId%20wdt%3AP31%20%3FcollectionTypeId.%0A%20%20%3FcollectionTypeId%20rdfs%3Alabel%20%3FcollectionType.%0A%20%20FILTER%28LANG%28%3FcollectionType%29%3D%27en%27%29.%0A%0A%20%20%23%20https%3A//www.wikidata.org/wiki/Property%3AP175%20Performer%20/Interpret%0A%20%20%3FsingleId%20wdt%3AP175%20%3FperformerId.%0A%20%20%3FperformerId%20rdfs%3Alabel%20%3Fperformer%0A%20%20FILTER%28LANG%28%3Fperformer%29%3D%27en%27%29%0A%0A%20%20%23%20https%3A//www.wikidata.org/wiki/Property%3AP8687%20followers%20/%20Follower%0A%20%20%23%7B%0A%20%20%20%20%20%23SELECT%20%28max%28%3FfollowerCount%29%20as%20%3Ffollower%29%0A%20%20%20%20%20%23WHERE%20%7B%0A%20%20%20%20%20%3FperformerId%20wdt%3AP8687%20%3FfollowerCount.%0A%20%20%20%20%20%23%7D%0A%20%20%20%20%20%23GROUP%20BY%20%3FperformerId%0A%20%20%23%7D%0A%20%20%23https%3A//www.wikidata.org/wiki/Property%3AP577%20Publication%20date%20/%20Ver%C3%B6ffentlichungsdatum%0A%20%20%3FsingleId%20wdt%3AP577%20%3FpublicationDate.%0A%20%20FILTER%28year%28%3FpublicationDate%29%20%3D%202022%29.%0A%7D%20ORDER%20BY%20%20DESC%28%3FfollowerCount%29%0ALIMIT%209%0A try it!]
result
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.
- https://en.wikipedia.org/wiki/Category:Database_theory
- https://en.wikipedia.org/wiki/Functional_dependency
- https://en.wikipedia.org/wiki/Database_normalization
- https://en.wikipedia.org/wiki/First_normal_form
- https://en.wikipedia.org/wiki/Second_normal_form
- https://en.wikipedia.org/wiki/Third_normal_form
- https://en.wikipedia.org/wiki/Boyce%E2%80%93Codd_normal_form
- https://en.wikipedia.org/wiki/Lossless_join_decomposition
- https://en.wikipedia.org/wiki/Candidate_key
- https://en.wikipedia.org/wiki/Surrogate_key
- https://en.wikipedia.org/wiki/Superkey