扩展独特的元组找到重新$ P $的关系由BDD psented

本文介绍了扩展独特的元组找到重新$ P $的关系由BDD psented的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

考虑{＆LT; 1,2>，＆LT; 1,3>，＆LT; 1,7>，＆LT; 0,4>}为一组关系的元组R.现在考虑R是再$ psented（通过其成员函数）p $由BDD。也就是说，该BDD重新presentingř取决于变量{X1，X2，Y1，Y2，Y3}其中{X1，X2}被用于重新present每一元组的第一个元素和{Y1，Y2 ，Y3}被用于重新present第二元件。

现在，考虑寻找该组具有在其第一元件的唯一值的元组的问题。对于上面这组关系是{＆LT; 0,4>}。所有其他元素被丢弃，因为它们是一个以上的值具有1中的第一组分

1,2>，＆所述; 1,3>，＆所述; 1,7>，＆所述; 2,3>，＆所述;

作为第二示例与元组的集合{＆所述考虑的关系2,5>，＆LT; 0,4>}。在这种情况下，预期的结果仍是{＆LT; 0,4>}为2不止一次出现的第一个元素

。

的问题也可以看作是抽象掉变量{Y1，Y2，Y3}，使得对于{X1，X2}只有唯一值保持。通过该结果，预期关系可以通过计算所得的BDD的结合输入1被重建。

在综上所述，问题是：它们是必须对R的重新presentation进行，得到的BDD仅用唯一的元组BDD中操作。

请注意，这就是一个genralization <一个href="http://stackoverflow.com/questions/14313049/find-unique-tuples-in-a-relation-re$p$psented-by-a-bdd?answertab=votes#tab-top">question

修改1：下面code反映了执行我到目前为止。不过，我想知道是否有可能得到一个更有效的版本。为了简单起见，我故意省略计算表的处理（关键，以获得更好的时间复杂度）。此外，我使用及放大器;，|和！来表示的同时，析取和上BDDS补充操作

  BDD uniqueAbstract（BDD楼BDD立方体）{
  如果（（f.IsZero（）|| f.IsOne（））及＆安培;！cube.IsOne（））
    返回零（）;
  BDD T =高（F）;
  BDD E =低（F）;
  如果（级（F）==级别（C））{//当前变种是抽象
    BDD uniqueThen = uniqueAbstract（T，高（C））;
    BDD existElse = existAbstract（E，高（C））;

    BDD existThen = existAbstract（T，高（C））;
    BDD uniqueElse = uniqueAbstract（E，高（C））;

    返回（uniqueThen＆安培; existElse！）| （uniqueElse＆安培;！existThen）
  } 其他 {
    BDD uniqueThen = uniqueAbstract（T，C）;
    BDD uniqueElse = uniqueAbstract（E，C）;
    返回ITE（顶部（F），uniqueThen，uniqueElse）;
  }
}

EDIT2：在尝试三种不同的实现仍存在一些性能问题。让我描述他们三人。

AC执行我的方法，让我把它的参考实现 4 。
在接受的答案 3 建议用户meolic的实现。
两个和可用 2 之间的混合方式。

该更新的目的是分析了一下，结果使用了三种方法。随着时间的措施似乎误导性在这个时候判断出来，我决定来评估一套不同的措施的实施。

在递归调用
缓存命中
摘要简单。次数的函数调用得到解决，而无需存在抽象。
摘要复杂：次函数调用得到解决，需要存在抽象的数量。
存在摘要：调用存在抽象的数

结果执行1：（21123毫秒）：独特的抽象的统计数据：递归调用：1728549.000000 高速缓存命中：638745.000000 非摘要：67207.000000 摘要简单：0.000000 摘要复杂：0.000000 存在摘要：1593430.000000

结果执行2：（运行时间：54727毫秒）独特的抽象的统计数据：递归调用：191585.000000 高速缓存命中：26494.000000 摘要简单：59788.000000 摘要复杂：12011.000000 存在摘要：24022.000000

结果执行3：（运行时间：20215毫秒）独特的抽象的统计数据：递归调用：268044.000000 高速缓存命中：30668.000000 摘要简单：78115.000000 摘要复杂：46473.000000 存在摘要：92946.000000

编辑3：以下结果执行在ITE 5 的术语的每个逻辑运算之后获得

uniqueAbstractRecRef（21831毫秒）独特的抽象的统计数据：总电话：1723239优化呼叫：0总存在抽象的电话：30955618独特的抽象要求存在摘要：2385915总ITE电话：3574555出的总时间，uniqueAbstractRecRef需要4001毫秒（12.4％）
uniqueAbstractSERec（56761毫秒）独特的抽象的统计数据：总电话：193627优化呼叫：60632总存在抽象的电话：16475806独特的抽象要求存在摘要：24304总ITE电话：1271844出的总时间，uniqueAbstractSERec花费33918毫秒（51.5％）
uniqueAbstractRec（20587毫秒）独特的抽象的统计数据：总电话：270205优化呼叫：78486总存在抽象的电话：13186348独特的抽象要求存在摘要：93060总ITE电话：1256872出的总时间，uniqueAbstractRec需要3354毫秒（10.6％）

解决方案

下面是我的实现。我研究的作者提出的解决方案，并在我看来，这是最好的，如果不是随心所欲的乱堆乱放的只有简单的BDD为基础的解决方案。然而，可能有一些改善，如果该算法在我的方式 - 请检查实施。我用我自己的包装上BDD包，但你不应该有任何麻烦去了解它。

编辑：我已经简化了解决方案，功能Bdd_GetVariableChar（）不再使用

FOR问题

  / *测试解决方案堆栈溢出* /
/ * bdd_termFalse，bdd_termTrue：布尔常量* /
/ * Bdd_isTerminal（F）：检查是否f是布尔常量* /
/ * Bdd_Low（F），Bdd_High（F）：'别人'和'然后'子函数* /
/ * Bdd_Top（F）：F的*文字的功能重新presenting topvar /
/ * Bdd_IsSmaller（F，G）：检查如果f topvar以上的G * topvar /
/ * existentialAbstraction（F，立方体）：\立方体*存在VF的所有V /

Bdd_Edge specialAbstraction（Bdd_Edge楼Bdd_Edge立方体）{
  如果（Bdd_isTerminal（立方体））返回F;
  如果（Bdd_isTerminal（F））返回bdd_termFalse;
  如果（Bdd_IsSmaller（F，立方体））{
    Bdd_Edge E，T;
    E = specialAbstraction（Bdd_Low（F），立方体）;
    T = specialAbstraction（Bdd_High（F），立方体）;
    返回Bdd_ITE（Bdd_Top（F），T，E）;
  }否则，如果（Bdd_IsSmaller（立方体，F））{
    返回bdd_termFalse;
  } 其他 {
    Bdd_Edge E，T;
    立方= Bdd_High（立方体）;
    E = Bdd_Low（F）;
    T = Bdd_High（F）;
    如果（Bdd_isEqv（E，bdd_termFalse））{
      返回specialAbstraction（T，立方体）;
    }否则，如果（Bdd_isEqv（T，bdd_termFalse））{
      返回specialAbstraction（E，立方体）;
    } 其他 {
      Bdd_Edge EX，TX，R;
      EX = existentialAbstraction（E，立方体）;
      TX = existentialAbstraction（T，立方体）;
      如果（Bdd_isEqv（EX，TX））返回bdd_termFalse;
      R = Bdd_ITE（Bdd_ITE（EX，bdd_termFalse，T）
                  bdd_termTrue，
                  Bdd_ITE（德克萨斯州，bdd_termFalse，E））;
      返回specialAbstraction（R，立方体）;
    }
  }
}

和，是的，如果变量排序是固定的上述X Y，该算法能够真正有效得多 - 你可以从最复杂的'其他'块中删除所有的计算，只是返回0

下面是一些测试运行：

  CUBE（以防万一你不熟悉的BDD算法）
  + Y1 Y2 Y3 Y4 Y5

ORIGINAL（排序，上述X Y）
  + * X1 * X2 X3 * X4 X5 Y1 * Y2 Y3 Y4 Y5
  + * X1 X2 * X3 * X4 * X5 Y1 Y2 * Y3 Y4 Y5
  + * X1 X2 * X3 * X4 X5 * Y1 Y2 * Y3 Y4 Y5
  + * X1 X2 * X3 X4 * X5 Y1 * Y2 Y3 * Y4 * Y5
  + * X1 X2 X3 * X4 X5 * Y1 * Y2 * Y3 * Y4 Y5
  + * X1 X2 X3 * X4 X5 * Y1 Y2 Y3 * Y4 * Y5
  X1 + X2 * * * X3 X4 * X5 Y1 Y2 Y3 Y4 * Y5
  + X1 X2 * X3 X4 X5 * Y1 * Y2 * Y4 * Y5
  + X1 X2 X3 * X4 * X5 * Y1 * Y2 * Y3 Y4 * Y5

ABSTRACTION
  + * X1 * X2 X3 * X4 X5
  + * X1 X2 * X3 * X4
  + * X1 X2 * X3 X4 * X5
  X1 + X2 * * * X3 X4 * X5
  + X1 X2 X3 * X4 * X5

ORIGINAL（订购Ÿ以上X）
  + * Y1 * Y2 * Y3 * Y4 * Y5 X1 X2 * X3 X4 X5
  + * Y1 * Y2 * Y3 * Y4 Y5 * X1 X2 X3 * X4 X5
  + * Y1 * Y2 * Y3 Y4 * Y5 X1 X2 X3 * X4 * X5
  + * Y1 * Y2 Y3 * Y4 * Y5 X1 X2 * X3 X4 X5
  + * Y1 Y2 * Y3 Y4 Y5 * X1 X2 * X3 * X4 X5
  + * Y1 Y2 Y3 * Y4 * Y5 * X1 X2 X3 * X4 X5
  + Y1 * Y2 Y3 * Y4 * Y5 * X1 X2 * X3 X4 * X5
  + Y1 * Y2 Y3 Y4 Y5 * X1 * X2 X3 * X4 X5
  + Y1 Y2 * Y3 Y4 Y5 * X1 X2 * X3 * X4 * X5
  + Y1 Y2 Y3 Y4 * Y5 X1 * X2 * X3 * X4 * X5

ABSTRACTION
  + * X1 * X2 X3 * X4 X5
  + * X1 X2 * X3 * X4
  + * X1 X2 * X3 X4 * X5
  X1 + X2 * * * X3 X4 * X5
  + X1 X2 X3 * X4 * X5

ORIGINAL（MIXED ORDER）
  + * X1 * X2 Y1 * Y2 Y3 Y4 Y5 X3 * X4 X5
  + * X1 X2 * Y1 * Y2 * Y3 * Y4 Y5 X3 * X4 X5
  + * X1 X2 * Y1 Y2 * Y3 Y4 Y5 * X3 * X4 X5
  + * X1 X2 * Y1 Y2 Y3 * Y4 * Y5 X3 * X4 X5
  + * X1 X2 Y1 * Y2 Y3 * Y4 * Y5 * X3 X4 * X5
  + * X1 X2 Y1 Y2 * Y3 Y4 Y5 * X3 * X4 * X5
  X1 + X2 * Y1 Y2 Y3 Y4 Y5 * * * X3 X4 * X5
  + X1 X2 * Y1 * Y2 * Y3 * Y4 * Y5 * X3 X4 X5
  + X1 X2 * Y1 * Y2 * Y3 Y4 * Y5 X3 * X4 * X5
  + X1 X2 * Y1 * Y2 Y3 * Y4 * Y5 * X3 X4 X5

ABSTRACTION
  + * X1 * X2 X3 * X4 X5
  + * X1 X2 * X3 * X4
  + * X1 X2 * X3 X4 * X5
  X1 + X2 * * * X3 X4 * X5
  + X1 X2 X3 * X4 * X5

Consider {<1,2>, <1,3>, <1,7>, <0,4>} as the set of tuples of a relation R. Now consider that R is represented (via its membership function) by a BDD. That is, The BDD representing R depends on variables {x1,x2, y1, y2, y3} where {x1, x2} are used to represent the first element of every tuple and {y1, y2, y3} are used to represent the second element.

Now, consider the problem of finding the set of tuples that have unique values in its first element. For the relation above that set would be {<0,4>}. All the other elements are discarded as they are more than one value having 1 in the first component.

As a second example consider the relation with set of tuples {<1,2>, <1,3>, <1,7>, <2,3>, <2,5>, <0,4>}. In such a case the expected result is still {<0,4>} as 2 appears more than once as first element.

The problem can be also seen as abstracting away the variables {y1,y2,y3} such that only unique values for {x1,x2} remain. With this result, the expected relation can be reconstructed by computing the conjunction of the resulting BDD with the input one.

In summary, the the question is: which are the BDD operations that have to be performed on The representation of R to obtain the BDD with only the unique tuples.

Notice that this is a genralization of this question

EDIT 1:The following code reflects the implementation I have so far. However, I am wondering if it is possible to get a more efficient version. For simplicity I intentionally omit the handling of the computed table (crucial to get better time complexity). Additionally, I use &, | and ! to denote the conjunction, disjunction and complement operations on BDDs.

BDD uniqueAbstract(BDD f, BDD cube) {
  if ((f.IsZero() || f.IsOne()) && !cube.IsOne())
    return zero();
  BDD T = high(f);
  BDD E = low(f);
  if(level(f) == level(c)) { // current var is abstracted
    BDD uniqueThen = uniqueAbstract(T, high(c));
    BDD existElse = existAbstract(E, high(c));

    BDD existThen = existAbstract(T, high(c));
    BDD uniqueElse = uniqueAbstract(E, high(c));

    return (uniqueThen & !existElse) | (uniqueElse & !existThen)
  } else {
    BDD uniqueThen = uniqueAbstract(T,c);
    BDD uniqueElse = uniqueAbstract(E,c);
    return ite(top(f), uniqueThen, uniqueElse);
  }
}

EDIT2: After trying three different implementations there are still some performance issues. Let me describe the three of them.

A C implementation of my approach, let me call it the reference implementation4.
The implementation proposed by user meolic in the accepted answer3.
A hybrid approach between the two and available2.

The goal of this update is to analyze a bit the results from using the three approaches. As time measures seem misleading at this time to judge them, I decided to evaluate the implementations on a different set of measures.

Recursive calls
Cache hits
Abstract simple. Number of times the function call was solved without requiring existential abstraction.
Abstract complex: Number of times the function call was solved requiring existential abstraction.
Exist abstract: Number of calls to the existential abstraction.

The results for implementation 1: (21123 ms): Unique abstraction statistics: Recursive calls: 1728549.000000 Cache hits: 638745.000000 Non abstract: 67207.000000 Abstract simple: 0.000000 Abstract complex: 0.000000 Exist abstract: 1593430.000000

Results for implementation 2: (run time: 54727 ms) Unique abstraction statistics: Recursive calls: 191585.000000 Cache hits: 26494.000000 Abstract simple: 59788.000000 Abstract complex: 12011.000000 Exist abstract: 24022.000000

Results for implementation 3: (run time: 20215 ms) Unique abstraction statistics: Recursive calls: 268044.000000 Cache hits: 30668.000000 Abstract simple: 78115.000000 Abstract complex: 46473.000000 Exist abstract: 92946.000000

EDIT 3: The following results were obtained after implementing every logical operation in terms of ITE5.

uniqueAbstractRecRef (21831 ms)Unique abstraction statistics:Total calls: 1723239Optimized calls: 0Total exist abstract calls: 30955618Unique abstract calls to exist abstract: 2385915Total ite calls: 3574555Out of the total time, uniqueAbstractRecRef takes 4001 ms (12.4%)
uniqueAbstractSERec (56761 ms)Unique abstraction statistics:Total calls: 193627Optimized calls: 60632Total exist abstract calls: 16475806Unique abstract calls to exist abstract: 24304Total ite calls: 1271844Out of the total time, uniqueAbstractSERec takes 33918 ms (51.5%)
uniqueAbstractRec (20587 ms)Unique abstraction statistics:Total calls: 270205Optimized calls: 78486Total exist abstract calls: 13186348Unique abstract calls to exist abstract: 93060Total ite calls: 1256872Out of the total time, uniqueAbstractRec takes 3354 ms (10.6%)

解决方案

Here is my implementation. I have studied author's proposed solution and it seems to me that it is the best if not the only simple BDD-based solution for arbitrary ordering. However, there may be some improvements if the algorithm is implemented in my way- PLEASE CHECK. I am using my own wrapper over BDD package but you should not have any troubles to understand it.

EDITED: I have simplified the solution, function Bdd_GetVariableChar() is not used anymore.

/* TESTING SOLUTION FOR QUESTION ON STACK OVERFLOW */
/* bdd_termFalse,bdd_termTrue: Boolean constants */
/* Bdd_isTerminal(f): check if f is Boolean constant */
/* Bdd_Low(f),Bdd_High(f): 'else' and 'then' subfunction */
/* Bdd_Top(f): literal function representing topvar of f */
/* Bdd_IsSmaller(f,g): check if topvar of f is above topvar of g */
/* existentialAbstraction(f,cube): \exist v.f for all v in cube */

Bdd_Edge specialAbstraction(Bdd_Edge f, Bdd_Edge cube) {
  if (Bdd_isTerminal(cube)) return f;
  if (Bdd_isTerminal(f)) return bdd_termFalse;
  if (Bdd_IsSmaller(f,cube)) {
    Bdd_Edge E,T;
    E = specialAbstraction(Bdd_Low(f),cube);
    T = specialAbstraction(Bdd_High(f),cube);
    return Bdd_ITE(Bdd_Top(f),T,E);
  } else if (Bdd_IsSmaller(cube,f)) {
    return bdd_termFalse;
  } else {
    Bdd_Edge E,T;
    cube = Bdd_High(cube);
    E = Bdd_Low(f);
    T = Bdd_High(f);
    if (Bdd_isEqv(E,bdd_termFalse)) {
      return specialAbstraction(T,cube);
    } else if (Bdd_isEqv(T,bdd_termFalse)) {
      return specialAbstraction(E,cube);
    } else {
      Bdd_Edge EX,TX,R;
      EX = existentialAbstraction(E,cube);
      TX = existentialAbstraction(T,cube);
      if (Bdd_isEqv(EX,TX)) return bdd_termFalse;
      R = Bdd_ITE(Bdd_ITE(EX,bdd_termFalse,T),
                  bdd_termTrue,
                  Bdd_ITE(TX,bdd_termFalse,E));
      return specialAbstraction(R,cube);
    }
  }
}

And, yes, if variable ordering is fixed with x above y, the algorithm can really be much more efficient - you can remove all the calculations from the most complex 'else' block and just return 0.

Here are some testing runs:

CUBE (JUST IN CASE YOU ARE NOT FAMILIAR WITH BDD ALGORITHMS)
  +  y1 y2 y3 y4 y5

ORIGINAL (ORDERED WITH X ABOVE Y)
  +  *x1 *x2 x3 *x4 x5 y1 *y2 y3 y4 y5
  +  *x1 x2 *x3 *x4 *x5 y1 y2 *y3 y4 y5
  +  *x1 x2 *x3 *x4 x5 *y1 y2 *y3 y4 y5
  +  *x1 x2 *x3 x4 *x5 y1 *y2 y3 *y4 *y5
  +  *x1 x2 x3 *x4 x5 *y1 *y2 *y3 *y4 y5
  +  *x1 x2 x3 *x4 x5 *y1 y2 y3 *y4 *y5
  +  x1 *x2 *x3 *x4 *x5 y1 y2 y3 y4 *y5
  +  x1 x2 *x3 x4 x5 *y1 *y2 *y4 *y5
  +  x1 x2 x3 *x4 *x5 *y1 *y2 *y3 y4 *y5

ABSTRACTION
  +  *x1 *x2 x3 *x4 x5
  +  *x1 x2 *x3 *x4
  +  *x1 x2 *x3 x4 *x5
  +  x1 *x2 *x3 *x4 *x5
  +  x1 x2 x3 *x4 *x5

ORIGINAL (ORDERED WITH Y ABOVE X)
  +  *y1 *y2 *y3 *y4 *y5 x1 x2 *x3 x4 x5
  +  *y1 *y2 *y3 *y4 y5 *x1 x2 x3 *x4 x5
  +  *y1 *y2 *y3 y4 *y5 x1 x2 x3 *x4 *x5
  +  *y1 *y2 y3 *y4 *y5 x1 x2 *x3 x4 x5
  +  *y1 y2 *y3 y4 y5 *x1 x2 *x3 *x4 x5
  +  *y1 y2 y3 *y4 *y5 *x1 x2 x3 *x4 x5
  +  y1 *y2 y3 *y4 *y5 *x1 x2 *x3 x4 *x5
  +  y1 *y2 y3 y4 y5 *x1 *x2 x3 *x4 x5
  +  y1 y2 *y3 y4 y5 *x1 x2 *x3 *x4 *x5
  +  y1 y2 y3 y4 *y5 x1 *x2 *x3 *x4 *x5

ABSTRACTION
  +  *x1 *x2 x3 *x4 x5
  +  *x1 x2 *x3 *x4
  +  *x1 x2 *x3 x4 *x5
  +  x1 *x2 *x3 *x4 *x5
  +  x1 x2 x3 *x4 *x5

ORIGINAL (MIXED ORDER)
  +  *x1 *x2 y1 *y2 y3 y4 y5 x3 *x4 x5
  +  *x1 x2 *y1 *y2 *y3 *y4 y5 x3 *x4 x5
  +  *x1 x2 *y1 y2 *y3 y4 y5 *x3 *x4 x5
  +  *x1 x2 *y1 y2 y3 *y4 *y5 x3 *x4 x5
  +  *x1 x2 y1 *y2 y3 *y4 *y5 *x3 x4 *x5
  +  *x1 x2 y1 y2 *y3 y4 y5 *x3 *x4 *x5
  +  x1 *x2 y1 y2 y3 y4 *y5 *x3 *x4 *x5
  +  x1 x2 *y1 *y2 *y3 *y4 *y5 *x3 x4 x5
  +  x1 x2 *y1 *y2 *y3 y4 *y5 x3 *x4 *x5
  +  x1 x2 *y1 *y2 y3 *y4 *y5 *x3 x4 x5

ABSTRACTION
  +  *x1 *x2 x3 *x4 x5
  +  *x1 x2 *x3 *x4
  +  *x1 x2 *x3 x4 *x5
  +  x1 *x2 *x3 *x4 *x5
  +  x1 x2 x3 *x4 *x5

这篇关于扩展独特的元组找到重新$ P $的关系由BDD psented的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

uniqueAbstractRecRef

扩展独特的元组找到重新$ P $的关系由BDD psented

问题描述