sql - 多层次组合背包

Question

我有大量用于数据仓库查询的表组合。

示例:

QueryID    Table
--------   ------
1          t1
1          t2
1          t3
--------------
2          t1
2          t3
--------------
3          t4
3          t2
--------------
4          t2
4          t3
4          t4
--------------
5          t3
5          t1

...还有更多...(大约有数千种这样的组合)。 我当前的分析包括从中找出模式，例如最常一起使用的表等。我的下一个分析点是找到可以通过使用最少数量的表来运行的最大查询数，并考虑表的大小。

例如，从上面的数据来看，我们可以通过使用三个表组合(t1，t2，t3)和(t1，t3)和(t2，t3，t4)等来运行至少2个查询。 ...例如，如果表格的大小是

table    size
-----    -----
t1        20 GB
t2        40 GB
t3        10 GB
t4        50 GB

然后

1. (t1,t2,t3) 总计 70 GB 可以运行三个查询
2. (t1,t3) 总计 30 GB 可以运行两个查询
3. (t2,t3,t4) 总计 100 GB 可以运行两个查询

其中 (t1,t3) 是具有最小大小和数量、可以运行两个查询的表的最佳组合。我正在尝试使用 SQL、Excel、R 等多种方法来提出动态解决方案，该解决方案可以采用参数，例如您想要运行的查询数量、您想要容忍的表组合的最大大小等。这里有任何最佳方法或建议将不胜感激。

更新:

查询需要所有参与的表都可以运行。所以我们不能说单独的t1就可以满足两个查询的要求，或者单独的t2就可以满足3个查询的要求。

Answer 1

我不清楚您如何计算一组表的查询数量。我可以看到 t1 有两个查询，t2 有三个查询，t3 有三个查询。如何从表 t1、t2 和 t3 的组合中计算查询数量？

# the data that you posted
quer <- structure(list(QueryID = c(1L, 1L, 1L, 2L, 2L, 3L, 3L, 4L, 4L, 4L), 
    Table = c("t1", "t2", "t3", "t1", "t3", "t4", "t2", "t2", "t3", "t4")), 
    .Names = c("QueryID", "Table"), class = "data.frame", row.names = c(NA, -10L))
size <- structure(list(Table = c("t1", "t2", "t3", "t4"), 
    GB = c(20L, 40L, 10L, 50L)), .Names = c("Table", "GB"), 
    class = "data.frame", row.names = c(NA, -4L))

# perhaps a helpful way to reorganize your query data
both <- merge(quer, size)
size2 <- tapply(both$GB, list(both$QueryID, both$Table), mean)
size2
  t1 t2 t3 t4
1 20 40 10 NA
2 20 NA 10 NA
3 NA 40 NA 50
4 NA 40 10 50

apply(size2, 1, sum, na.rm=TRUE)
  1   2   3   4 
 70  30  90 100