标签: functional-dependencies

我正试图实现Fisher-Yates对某些数据的改组.该算法易于实现一维数组.但是,我需要能够在二维矩阵中混洗数据.

我认为可以很好地推广到更高维数组的方法是将我任意尺寸的矩阵转换为索引的一维数组,对其进行混洗,然后通过将该索引数组的每个索引处的元素与元素交换来重新组织矩阵在索引数组元素的索引处.换句话说,采用2x2矩阵,例如:

1  2
3  4

我会把它转换成这个"数组":

[(0, (0,0)),  (1, (0,1)),  (2, ((1,0)),  (3, (1,1))]

然后,我会按照正常情况进行争夺,比方说,

[(0, (1,0)),  (1, (0,1)),  (2, ((1,1)),  (3, (0,0))]

重组后,原始矩阵将变为:

2  3
4  1

我的基本方法是我想要一个类似于以下类型的类:

class Shufflable a where
  indices    :: a -> Array Int b
  reorganize :: a -> Array Int b -> a

然后我将有一个函数来执行看起来像这样的shuffle:

fisherYates :: (RandomGen g) => g -> Array Int b -> (Array Int b, g)

我认为(减去RandomGen管道)我应该可以改变这样一个可洗牌的东西:

shuffle :: (Shufflable a, RandomGen g) => a -> g -> (a, g) …

请考虑以下代码:

{-# LANGUAGE MultiParamTypeClasses,FlexibleInstances,FunctionalDependencies,UndecidableInstances,FlexibleContexts  #-}
class Foo a c | a -> c
instance Foo Int Float 
f :: (Foo Int a) => Int -> a 
f = undefined

现在,当我在ghci中看到f的推断类型时

> :t f
> f :: Int -> Float

现在如果我添加以下代码

g :: Int -> Float 
g = undefined 

h :: (Foo Int a) => Int -> a 
h = g

我收到了错误

Could not deduce (a ~ Float)

我无法理解这里发生了什么？限制Foo Int a应该限制hto 的类型,Int -> Float如推断类型所示f …

我只是想确保我正确地思考它

1)完全依赖性是指一个或多个主键确定另一个属性

2)部分依赖性是当其中一个主键确定另一个或多个属性时

3)传递依赖性是当nonkey属性确定另一个属性时

我在想它吗？

因此,我正在查看我的数据库备注和材料,试图让自己了解即将采访的一般概念和术语.然而,我已经陷入了依赖,然而无损连接分解.我已经搜遍了所有并且看到了许多mathy方程式,但我正在寻找一个简单而简单的英语响应或示例.

我从http://www.cs.kent.edu/~jin/DM09Fall/lecture6.ppt找到了一个powerpoint,它说明了一个我无法完全理解的例子.它发布在下面.

R = (A, B, C)F = {A ? B, B ? C)
Can be decomposed in two different ways
R1 = (A, B),   R2 = (B, C)
Lossless-join decomposition:
         R1 ? R2 = {B} and B ? BC
Dependency preserving
R1 = (A, B),   R2 = (A, C)
Lossless-join decomposition:
         R1 ? R2 = {A} and A ? AB
Not dependency preserving (cannot check B -> C without computing R1 ? R2)

所以我理解A→B和B→C意味着你们彼此有"参考",而A→B和A→C意味着B和C之间没有参考或联系.

所以,

1. Lossless-join分解是否意味着整体数据仍然完好无损？在这两种情况下,您仍然可以最终获得两种数据,对吧？如果这是错的,请纠正我!:)

2. 在第二次分解中将连接B设置为C有什么意义,这又如何使它不依赖于保留？ …

假设关系R( K, L, M, N, P)和持久的功能依赖关系R是:

 - L  -> P
 - MP -> K
 - KM -> P
 - LM -> N

假设我们将其分解为3个关系,如下所示:

 - R1(K, L, M)
 - R2(L, M, N)
 - R3(K, M, P)

我们如何判断这种分解是否无损？ 我用过这个例子

R1∩R2= {L,M},R2∩R3= {M},R1∩R3= {K,M}我们使用函数依赖,在我看来这不是无损的,但有点混淆.

根据Monad Reader第8期中的文章,我使用功能依赖和类型系列编写了"Instant Insanity"拼图的类型级解决方案:

• fundeps解决方案:http://lpaste.net/113108
• 类型家庭解决方案:http://lpaste.net/113113

fundeps解决方案大约需要200秒.而类型族版本在大约800秒内完成.

是否有任何技术可以使类型族版本更有效地运行？

我试图在final-tagless编码中表达一对相互递归的数据类型.

我能写:

{-# LANGUAGE NoMonomorphismRestriction #-}
{-# LANGUAGE ExplicitForAll #-}
module Test where

  class ExprSYM repr where
    expr :: forall proc. (ProcSYM proc) => proc Int -> repr

  class ProcSYM repr where
    varProc :: forall a. String -> repr a
    intProc :: String -> repr Int
    subjectOf :: forall expr. (ExprSYM expr) => expr -> repr Int

  myProc = intProc "proc A."

但是,当我写:

myExpr = expr myProc

我收到以下错误:

Could not deduce (Test.ProcSYM proc0)
  arising from a use of …

我见过的函数依赖的例子归结为映射container -> element和arguments -> result(如Mult Matrix Vector Vector).它们似乎用类型函数表达得更好.在数据库理论中,更复杂的关系被认为不是这种形式(如a -> b, b -> a).

是否存在使用类型函数无法很好地编写Haskell中FD的使用示例？

考虑以下Haskell代码:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances,
    FunctionalDependencies #-}

class C a b c | a b -> c

instance C (l (i,j)) (r i j)   j
instance C (l i j)   (r (i,j)) j
-- Conflict between the following two lines
instance C (l (i,j)) (r (i,j)) j  
instance C (l i j)   (r i j)   j

这里,GHC在最后两行之间产生功能依赖性错误.如果我删除最后两个实例声明中的任何一个,代码将编译.我尝试使用类型系列的类比,这也产生了冲突.我的第一个问题是:为什么最后两行冲突,而其他声明一起工作得很好？

另外,如果我将最后一行更改为

instance C (l i j)   (r i j)   i

GHC接受该代码.这似乎很奇怪,因为唯一改变的是依赖类型变量c.有人可以解释这种行为吗？

假设我们有一张表：

CREATE TABLE Jobs
    (
      JobID INT PRIMARY KEY ,
      AssignedUser VARCHAR(10) ,
      Zone VARCHAR(10)
    )

我们需要强制执行的约束是这样的：确保没有用户在多个区域中分配作业，即存在功能依赖性AssignedUser => Zone。

如何在 SQL 中强制执行此操作？不幸的是，这是一个遗留表，我们无法更改其结构，但我们可以创建约束来强制完整性。