我正在从事一个基于 java-oracle 的项目，在这个项目中我遇到了一个问题，在我看来这个问题需要一个分析解决方案。 我正在寻找基于 SQL 查询或任何算法或任何免费分析工具的解决方案，我可以按照这些工具获得所需的结果。
问题陈述: 假设我有下面的表，其中 A-D 列和最后一列作为 Score，我想为每个列找到一个值标准，当在 SQL where 子句中组合时，该标准将始终为 Score 列提供正值。那么基本上 A-D 列的哪种组合总能给我正分？
columnA|columnB|columnC|columnD|Score
1 40 10 3 -20
0 40 2 3 10
0 10 3 3 20
1 15 3 3 -5
0 10 2 2 -15
0 15 6 3 -10
上述数据集的预期结果:- 上述数据集的视觉解释给出了条件:“ColumnA =0 and columnB >10 and columnC <5 will="" ensure="" score="" always="">0”。 (从视觉上看它的clear columnD没有作用)。
请注意以上数据集是为了简单起见。实际上，我的项目包含大约 40 列和近 2500 行。可以肯定的是，每一列的值范围都是有限的。
这是我开始使用的算法(如果有人认为我的方向正确，则需要输入以进一步完善它):
准备:创建一个包含所有可能表达式的列表，例如 A=0、B>10、C<5(对于 40="" 列，我最终确定了大约="" 150="">
让我们称它为“表达式”变量。
第一次运行的算法:
set totalPositiveRows= select count(*) from my tables where score>0;
设置 totalNegativeRows= select count(*) from my tables where score<>
对于表达式中的每个expr，计算以下三个变量 设置 positivePercentage= 找到满足此 expr 的 totalPositiveRows 的百分比；//如果总计 100 行中有 60 行得分>0 满足 expr，则 positivePercentage=60%
set negativePercentage= find percentage of totalNegativeRows which satisfy this expr; //like if 40 rows out of total 100 rows having score<0 satisfy expr , then negativePercentage=40%
set diffPercentage=positivePercentage-negativePercentage;
Set initialexpr=选择具有最大值 diffPercentage 的 expr set initalPositivePercentage=选择相应的positivePercentage值； set initalNegativePercentage=选择相应的negativePercentage值； 我的想法是，我现在需要继续扩展 initalexpr，直到 initalNegativePercentage 变为 0。
后续运行的算法，直到 initalNegativePercentage 变为 0:-
对于表达式中的每个expr，计算以下三个变量
设置 newexpr=initialexpr+"和 "+expr；
set positivePercentage= 找到满足 newexpr 的 totalPositiveRows 的百分比；
set negativePercentage=求出totalNegativeRows中满足newexpr的百分比；
//计算它减少了多少负百分比？ 设置 positiveReduction=initalPositivePercentage-positivePercentage； 设置 negativeReduction=initalNegativePercentage-negativePercentage; 如果(负减少>=正减少) //记下来 别的 //丢弃它
选择给出最大负减少的表达式，成为新的初始表达式。 Set initialexpr=选择具有最大值 negativeReduction 的 expr set initalPositivePercentage=选择相应的值； set initalNegativePercentage=选择相应的值；
重复上面的算法。
请评论。
最佳答案
下面是一个蛮力解决方案。对于理论计算机科学站点，这也可能是一个很好的问题。我认为这是一个类似于 Boolean satisfiability 的 NP 完全问题，但这只是一个疯狂的猜测。可能有更聪明的方法来解决这个问题，但我认为我找不到。
基本思想是将每个表达式与列的每个不同值交叉连接，然后交叉连接所有列。将使用每个表达式列表查询该表，并为正分和负分生成计数。如果表达式返回预期数量的正分数并且没有负分数，则它是有效的。
这假设您只使用表达式 > , < , 和 = .每个新列或表达式都会使这个问题呈指数级变慢。
测试架构
drop table table1;
create table table1(a number, b number, c number, d number, score number);
insert into table1
select 1, 40, 10, 3, -20 from dual union all
select 0, 40, 2, 3, 10 from dual union all
select 0, 10, 3, 3, 20 from dual union all
select 1, 15, 3, 3, -5 from dual union all
select 0, 10, 2, 2, -15 from dual union all
select 0, 15, 6, 3, -10 from dual;
代码墙
declare
v_inline_view varchar2(32767);
v_inline_views clob;
v_inline_view_counter number := 0;
v_and_expression varchar2(32767);
v_query clob;
v_sqls sys.odcivarchar2list;
v_dynamic_query_counter number := 0;
begin
--#1: Create inline views.
--One for every combination of expression and distinct value, per column.
for inline_views in
(
--Inline view for every possible expression for each column.
select
replace(q'[
(
select *
from
(
--Possible expressions.
select distinct
case
when operator is null then null
else ' AND %%COLUMN%% '||operator||' '||%%COLUMN%%
end %%COLUMN%%_expression
from
--All operators.
(
select '>' operator from dual union all
select '<' operator from dual union all
select '=' operator from dual union all
select null operator from dual
)
--All distinct values.
cross join
(
select distinct %%COLUMN%% from table1
)
)
--where %%COLUMN%%_expression is null or %%COLUMN%%_expression %%EXPRESSION_PERFORMANCE_EXCLUSIONS%%
)
]', '%%COLUMN%%', column_name) inline_view
from user_tab_columns
where table_name = 'TABLE1'
and column_name <> 'SCORE'
order by column_name
) loop
--Assign to temorary so it can be modified.
v_inline_view := inline_views.inline_view;
--#1A: Optimize inline view - throw out expressions if they don't return any positive results.
declare
v_expressions sys.odcivarchar2list;
v_expressions_to_ignore varchar2(32767);
v_has_score_gt_0 number;
begin
--Gather expressions for one column.
execute immediate v_inline_view bulk collect into v_expressions;
--Loop through and test each expression.
for i in 1 .. v_expressions.count loop
--Always keep the null expression.
if v_expressions(i) is not null then
--Count the number of rows with a positive score.
execute immediate 'select nvl(max(case when score > 0 then 1 else 0 end), 0) from table1 where '||replace(v_expressions(i), ' AND ', null)
into v_has_score_gt_0;
--If the expression returns nothing positive then add it to exclusion.
if v_has_score_gt_0 = 0 then
v_expressions_to_ignore := v_expressions_to_ignore||','''||v_expressions(i)||'''';
end if;
end if;
end loop;
--Convert it into an IN clause.
if v_expressions_to_ignore is not null then
--Remove comment, replace placeholder with expression exclusions.
v_inline_view := regexp_replace(v_inline_view, '(.*)(--where)( .* )(%%EXPRESSION_PERFORMANCE_EXCLUSIONS%%)(.*)', '\1where\3 not in ('||substr(v_expressions_to_ignore, 2)||')');
end if;
end;
--Aggregate and count inline views.
if v_inline_view_counter <> 0 then
v_inline_views := v_inline_views||'cross join';
end if;
v_inline_views := v_inline_views||v_inline_view;
v_inline_view_counter := v_inline_view_counter + 1;
end loop;
--#2: Create an AND expression to combine all column expressions.
select listagg(column_name||'_expression', '||') within group (order by column_name)
into v_and_expression
from user_tab_columns
where table_name = 'TABLE1'
and column_name <> 'SCORE';
--#3: Create a that will create all possible expression combinations.
v_query :=
replace(replace(q'[
--8281 combinations
select '
select
'''||expressions||''' expression,
nvl(sum(case when score > 0 then 1 else 0 end), 0) gt_0_score_count,
nvl(sum(case when score <= 0 then 1 else 0 end), 0) le_0_score_count
from table1
where 1=1 '||expressions v_sql
from
(
--Combine expressions
select %%AND_EXPRESSION%% expressions
from
%%INLINE_VIEWS%%
) combined_expressions
]', '%%AND_EXPRESSION%%', v_and_expression), '%%INLINE_VIEWS%%', v_inline_views);
--TEST: It might be useful to see the full query here.
--dbms_output.put_line(v_query);
--#4: Gather expressions.
--With larger input you'll want to use a LIMIT
execute immediate v_query
bulk collect into v_sqls;
--#5: Test each expression.
--Look for any queries that return the right number of rows.
for i in 1 .. v_sqls.count loop
declare
v_expression varchar2(4000);
v_gt_0_score_count number;
v_le_0_score_count number;
begin
execute immediate v_sqls(i) into v_expression, v_gt_0_score_count, v_le_0_score_count;
v_dynamic_query_counter := v_dynamic_query_counter + 1;
--TODO: Dynamically generate "2".
if v_gt_0_score_count = 2 and v_le_0_score_count = 0 then
dbms_output.put_line('Expression: '||v_expression);
end if;
exception when others then
dbms_output.put_line('Problem with: '||v_sqls(i));
end;
end loop;
dbms_output.put_line('Queries executed: '||v_dynamic_query_counter);
end;
/
结果
结果看起来是正确的。它们与您的略有不同，因为“columnB > 10”不正确。
Expression: AND A = 0 AND C < 6 AND D = 3
Expression: AND A = 0 AND C < 6 AND D > 2
Expression: AND A < 1 AND C < 6 AND D = 3
Expression: AND A < 1 AND C < 6 AND D > 2
Queries executed: 441
问题
这种蛮力方法至少在两个方面效率极低。即使对于这个简单的例子，它也需要 6370 次查询。结果可能包括重复项，这些重复项对于减少来说非常重要。或者，也许您会很幸运，并且解决方案太少以至于您可以目睹它们。
您可以采取一些措施来提高查询性能。最简单的方法是单独检查每个条件，如果它没有“获得”任何计数，则将其丢弃。
优化
不返回任何正结果的单个表达式被排除在外。对于示例数据，这将查询执行次数从 6370 次减少到 441 次。
并行运行该过程也可以将性能提高一个数量级。它可能需要一个并行流水线函数。
但即使是 100 倍的性能提升也可能无助于解决 NP 完全问题。您可能需要根据样本数据找到一些额外的“捷径”。
通过取消注释其中一个 dbms_output.put_line 可能有助于打印出生成测试查询的查询声明。添加 count(*)查看将执行多少查询并使用较小的数据集运行，以估计需要多长时间。
如果估计是 10 亿年，而你想不出任何让蛮力法更快工作的技巧，可能是时候在 https://cstheory.stackexchange.com/ 上提问这个问题了。
关于java - 算法或 SQL : to find where conditions for a set of columns which ensures result set has value in a particular column always > 0，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28208530/