Stack Overflow
Stack Overflow

Questions tagged [functional-dependencies]

A functional dependency is a constraint between two sets of attributes in a relation, in relational algebra, databases and type systems.

Functional dependencies (FD) are fundamental to the process of normalization.

Given a relation R, a set of attributes X in R is said to functionally determine a set of attributes Y, also in R, (written X → Y) if, and only if, whenever two tuples coincide on all attributes of X, they also coincide on all attributes of Y. Sound, complete and non-redundant axiomatisation of functional dependencies is given by Armstrong rules. Functional dependencies are also used in the Haskell programming language to describe relations between types, to support type level relational programming.

In other words, a dependency FD: X → Y means that the values of Y are determined by the values of X. Two tuples sharing the same values of X will necessarily have the same values of Y.

Enter image description here

544 questions
48
votes
0 answers

“Illegal type synonym family application in instance” with functional dependency

I have a multi-parameter typeclass with a functional dependency: class Multi a b | a -> b I also have a simple, non-injective type synonym family: type family Fam a I want to write an instance of Multi that uses Fam in the second parameter, like…
Alexis King
  • 43,109
  • 15
  • 131
  • 205
44
votes
6 answers

Determine Keys from Functional Dependencies

I'm taking a database theory course, and it's not clear to me after doing the reading how I can infer keys, given a set of functional dependencies. I have an example problem: Find all keys of the relation R(ABCDEFG) with functional dependencies AB →…
David
  • 2,550
  • 7
  • 27
  • 29
34
votes
1 answer

What does a pipe in a class definition mean?

class (Monoid w, Monad m) => MonadWriter w m | m -> w where pass :: m (a,w -> w) -> m a listen :: m a -> m (a,w) tell :: w -> m () What is the meaning of the pipe above? The snippet comes from here.
luntain
  • 4,560
  • 6
  • 37
  • 48
34
votes
4 answers

candidate keys from functional dependencies

Given the Relation R with attributes ABCDE. You are given the following dependencies: A -> B, BC -> E, and ED -> A. I already have the answer which is CDE, ACD, and BCD. I just need to know how to do it. Thanks.
ranzy
  • 459
  • 3
  • 6
  • 10
32
votes
2 answers

Minimal Cover and functional dependencies

Given the following functional dependencies how would I compute the minimal cover: A -> B, ABCD -> E, EF -> GH, ACDF -> EG In the lecture notes it gives the derivation for the minimal cover but I do not understand it. For example for getting rid of…
kachilous
  • 2,499
  • 11
  • 42
  • 56
30
votes
9 answers

Partial Dependency (Databases)

I fabricated a definition that a partial dependency is when fields are indirectly dependent on the primary key or partially dependent but are also dependent on other keys that depend on the primary such that if the field which another field depends…
rert588
  • 737
  • 1
  • 7
  • 19
18
votes
6 answers

Functional dependency and normalization

I am trying to find a great resource to study for functional dependency and normalization. Anyone have any idea where should I look to? I am having difficulty differentiating whether a FD is in 1NF, 2NF or 3NF? I've been reading Wikipedia and used…
aherlambang
  • 14,290
  • 50
  • 150
  • 253
16
votes
1 answer

How does haskell resolve overlapping instances?

Please excuse me if I use the wrong terminology, I am much a beginner in haskell type manipulation... I am trying to use overlapping instances with functional dependencies to do some type-level programming with HLists. Here my objective is to try…
rtpg
  • 2,419
  • 1
  • 18
  • 31
15
votes
6 answers

How to avoid quadratic explosion of typeclass instances?

Consider: {-# OPTIONS -fglasgow-exts #-} data Second = Second data Minute = Minute data Hour = Hour -- Look Ma', a phantom type! data Time a = Time Int instance Show (Time Second) where show (Time t) = show t ++ "sec" instance Show (Time…
Landei
  • 54,104
  • 13
  • 100
  • 195
15
votes
4 answers

How to determine the functional dependencies

I am to create a logical data model based on my own project specification and also determine the functional dependencies. Table User example data: user_id username regDate type subscription 1 JohnS 01-01-2012 Administrator …
Shiraz
  • 165
  • 1
  • 2
  • 6
14
votes
1 answer

All type parameters depending on each other in functional dependencies

Let's say I have a type class with n type parameters and I want any of them to uniquely determine all the other ones. Is it enough to make the dependencies form a cycle like in class Foo a b c | a -> b, b -> c, c -> a (linear) where there is a path…
Petr
  • 62,528
  • 13
  • 153
  • 317
14
votes
4 answers

Normalization Dependencies

Im just trying to make sure that im thinking of it the right way 1)full dependencies are when one or more primary keys determine another attribute 2)partial dependencies are when one of the primary keys determines another attribute or…
user214577
  • 363
  • 1
  • 7
  • 15
13
votes
2 answers

Haskell functional dependency conflict

Why does this result in a conflict? class Foo a b | b -> a where foo :: a -> b -> Bool instance Eq a => Foo a a where foo = (==) instance Eq a => Foo a (a -> a) where foo x f = f x == x Note that the code will compile if I remove the…
Thomas Eding
  • 35,312
  • 13
  • 75
  • 106
13
votes
1 answer

Converting Functional Dependency class to Type Family instances

Is it possible to create type family instances from a fundep class? For example, let's say that I have the class class A a b | a -> b with some instances (imported an external library) and want to create all corresponding instances for the type…
Hjulle
  • 2,471
  • 1
  • 22
  • 34
12
votes
4 answers

Static Guarantee on Key/Value Relationships in Data.Map

I want to make a special smart constructor for Data.Map with a certain constraint on the types of key/value pair relationships. This is the constraint I tried to express: {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, DataKinds…
cdk
  • 6,698
  • 24
  • 51
1
2 3
…
36 37