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