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
550
questions
54
votes
1
answer
3k
views
“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 ...
- 43.5k
44
votes
6
answers
85k
views
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 ...
- 2,550
35
votes
1
answer
3k
views
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 ...
- 4,590
34
votes
4
answers
80k
views
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 ...
- 459
32
votes
2
answers
85k
views
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 ...
- 2,519
30
votes
9
answers
183k
views
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 ...
- 737
18
votes
6
answers
62k
views
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, ...
- 14.4k
16
votes
1
answer
3k
views
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 ...
- 2,439
15
votes
6
answers
555
views
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 (...
- 54.4k
15
votes
4
answers
60k
views
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 ...
- 165
14
votes
4
answers
66k
views
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 ...
- 363
14
votes
1
answer
141
views
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 -&...
- 63.1k
13
votes
2
answers
2k
views
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 ...
- 35.8k
13
votes
1
answer
461
views
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 ...
- 2,521
12
votes
4
answers
577
views
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 ...
- 6,718
11
votes
2
answers
227
views
Typeclass instance with functional dependencies doesn't work
Playing around with type-classes I came up with the seemingly innocent
class Pair p a | p -> a where
one :: p -> a
two :: p -> a
This seems to work fine, e.g.
instance Pair [a] a where
...
- 54.4k
10
votes
2
answers
27k
views
Finding candidate keys for given relation
R = (A, B, C, D, E)
The functional dependencies are:
A -> B
ED -> A
BC -> E
It then lists the candidate keys as:
ACD, BCD, CDE
How are these candidate keys derived from the above FDs?
...
- 281
10
votes
2
answers
484
views
Why does this Haskell code typecheck with fundeps but produce an untouchable error with type families?
Given some type definitions:
data A
data B (f :: * -> *)
data X (k :: *)
…and this typeclass:
class C k a | k -> a
…these (highly contrived for the purposes of a minimal example) function ...
- 43.5k
9
votes
3
answers
34k
views
Are determinants and candidate keys the same?
At https://web.archive.org/web/20130514174856/http://databases.about.com/cs/specificproducts/g/determinant.htm I found this by Mike Chapple:
Definition: A determinant in a database table is any ...
- 1,273
9
votes
8
answers
2k
views
What kind of normalization rule does this violate?
Suppose I have two tables on a database, T10 and T11, having 10 and 11 columns, respectively, where 10 of the columns are exactly the same on both.
What (if any) normalization rule am I violating?
- 74.3k
9
votes
3
answers
19k
views
Lossless Join and Decomposition From Functional Dependencies
Suppose the relation R( K, L, M, N, P), and the functional dependencies that hold on R are:
- L -> P
- MP -> K
- KM -> P
- LM -> N
Suppose we decompose it into 3 relations as ...
- 115
9
votes
3
answers
6k
views
tdd - creating tests for 3rd party code
How do I create unit tests if the method or procedure I'm testing against relies on a piece of code from a 3rd party? Say, I have a method that uses classes from a third party source that requires ...
- 278
9
votes
2
answers
658
views
Why does my functional dependency conflict disappear when I expand the definition?
I was trying to implement Integers at the type level in Haskell. To start I implemented natural numbers with
data Zero
data Succ a
I then extended this to the integers with
data NegSucc a
I ...
- 4,051
9
votes
1
answer
193
views
Creating a completely dependent concatenation
A nice true fact about concatenation is that if I know any two variables in the equation:
a ++ b = c
Then I know the third.
I would like to capture this idea in my own concat so I use a functional ...
- 4,051
9
votes
2
answers
344
views
Shortening code by exploiting symmetry among multiple type class instances
Context
I'm writing a Haskell module that represents SI prefixes:
module Unit.SI.Prefix where
Each SI prefix has a corresponding data type:
data Kilo = Kilo deriving Show
data Mega = Mega deriving ...
- 285
8
votes
2
answers
647
views
What is the "coverage condition"?
The source for the State transformer in mtl states:
-- ---------------------------------------------------------------------------
-- Instances for other mtl transformers
--
-- All of these instances ...
- 53.5k
8
votes
3
answers
413
views
Bidirectional Functional Dependencies
I have a type class that looks a bit like the following:
class Foo a b | a -> b where
f :: a -> Bool
g :: b -> Bool
h :: a -> b -> Bool
Or at least these are the bits that are ...
- 4,051
8
votes
3
answers
23k
views
Finding a relation in 3NF but not in BCNF
I've been reading many different sources on how to differentiate relations that are in 3NF/BCNF. And I've so far this is my understanding...
I will use this relation as an example...
R = {A, B, C, ...
- 6,559
8
votes
1
answer
392
views
Motivation of having Functional Dependencies
What is the motivation of having functional dependencies in Haskell ?
One example of a functional dependency:
class (Monad m) => MonadSupply s m | m -> s where
next :: m (Maybe s)
It is ...
- 48.1k
8
votes
1
answer
2k
views
Functional Dependency in Haskell
I cannot really get it. Why do we need it at all? I mean if I use the same type parameter, I think that means they should be the same type.
I heard it can help the compiler to avoid the infinite loop....
- 733
7
votes
6
answers
38k
views
Non trivial functional dependency in DBMS
What are the non-trivial functional dependencies in the following table?
A B C
1 1 1
1 1 0
2 3 2
...
- 105
7
votes
4
answers
14k
views
Difference between canonical cover and minimal cover
I know how to calculate a minimal cover--
ensure each functional dependency only has one attribute on the RHS,
remove extraneous/redundant LHS attributes by calculating the closure of each,
examining ...
- 79
7
votes
2
answers
16k
views
Dependency preserving
So I am looking over my database notes and material trying to refresh myself on the general concepts and terminology for upcoming interviews. I have gotten stuck at dependency however and lossless-...
- 3,030
7
votes
3
answers
1k
views
F# application structure logging / repositories etc
I'm gradually switching into F# for a lot of my home projects but I'm a little stumped as to how to wire together complete applications, and more particularly cross-cutting concerns.
In C# if I want ...
- 1,306
7
votes
1
answer
417
views
Haskell: shuffling data without functional dependencies
I'm trying to implement a Fisher-Yates shuffle of some data. This algorithm is easy to implement for one-dimensional arrays. However, I need to be able to shuffle data in a two-dimensional matrix.
An ...
- 22.6k
7
votes
1
answer
284
views
Final-tagless encoding of mutually recursive types
I am trying to express a pair of mutually recursive data types in the final-tagless encoding.
I am able to write:
{-# LANGUAGE NoMonomorphismRestriction #-}
{-# LANGUAGE ExplicitForAll #-}
module ...
- 1,354
7
votes
1
answer
417
views
more efficient type-level computations using type families?
Based on the article in the Monad Reader, Issue #8, I've coded up the type-level solution to the "Instant Insanity" puzzle using both Functional Dependencies and Type Families:
fundeps solution: http:...
- 51.8k
7
votes
1
answer
358
views
How Type inference work in presence of Functional Dependencies
Consider the code below :
{-# LANGUAGE MultiParamTypeClasses,FlexibleInstances,FunctionalDependencies,UndecidableInstances,FlexibleContexts #-}
class Foo a c | a -> c
instance Foo Int Float
f ::...
- 11.2k
7
votes
1
answer
196
views
Functional dependency does not unify when bound in GADT
In the following code:
class FD a b | a -> b
data Foo a where
Foo :: FD a b => b -> Foo a
unFoo :: FD a b => Foo a -> b
unFoo (Foo x) = x
By common sense this should work, since a ...
- 701
7
votes
0
answers
80
views
Functionally dependant wrapped in a newtype
I wonder why the below code does not compile and if there is an implementation mkYVal that GHC would accept.
class C x y | x -> y
newtype YVal x = YVal { getYVal :: forall y . C x y => y }
...
- 6,698
6
votes
2
answers
493
views
Haskell: nonobvious examples of functional dependencies
The examples of functional dependencies I've seen boil down to mapping container -> element, and arguments -> result (as in Mult Matrix Vector Vector). They seem to be better expressed with type ...
- 25.5k
6
votes
1
answer
256
views
Haskell functional dependency a b -> c depending on c?
Consider the following Haskell code:
{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances,
FunctionalDependencies #-}
class C a b c | a b -> c
instance C (l (i,j)) (r i j) j
instance C (l ...
6
votes
2
answers
1k
views
What can type families do that multi param type classes and functional dependencies cannot
I have played around with TypeFamilies, FunctionalDependencies, and MultiParamTypeClasses. And it seems to me as though TypeFamilies doesn't add any concrete functionality over the other two. (But not ...
- 2,540
6
votes
4
answers
6k
views
Lossless Join Decomposition
I am studying for a test, and this is on the study guide sheet. This is not homework, and will not be graded.
Relation Schema R = (A,B,C,D,E)
Functional Dependencies = (AB->E, C->AD, D->B, E->C)
...
- 79
6
votes
3
answers
9k
views
algorithm for computing closure of a set of FDs
I'm looking for an easy to understand algorithm to compute (by hand) a closure of a set of functional dependencies.
Some sources, including my instructor says I should just play with Armstrong's ...
- 83
5
votes
3
answers
11k
views
What does the symbol "⊇" mean?
In the attached picture there's a symbol I don't understand. To understand additive functional dependency I need to know what the symbol means. Please advice?
It's the symbol where it says: "Suppose ...
- 3,984
5
votes
4
answers
10k
views
Decomposition that does not preserve functional dependency
When can a BCNF decomposition not preserve functional dependency... I am trying to figure this out for say R=(V,W,X,Y,Z)
user990246
5
votes
1
answer
5k
views
Lossless decomposition vs Dependency Preservation
Does anyone of them implies the other?
My logic is that if all dependencies are preserved, then there is no loss of information and similarly, if decomposition is lossless then no functional ...
- 697
5
votes
1
answer
404
views
How to get around the Coverage Condition for Functional Dependencies without using -XUndecidableInstances
Wen using functional dependencies, I frequently hit the Coverage Condition. It is possible to lift it with UndecidableInstances, but I usually try to stay away from that extension.
Here is a ...
- 728
5
votes
1
answer
143
views
How can I use a type parameter determined via the functional dependency of an instance constraint as the RHS of an associated type family equation?
I have a typeclass like this:
class (Coercible a b) => Foo a b | a -> b
I would like to declare the following instance of Generic:
data Thing a
where
Thing :: Foo a b => b -> Thing a
...
- 46.4k