一种非确定数据库下的Top-k查询及执行方法

摘要

本发明公开了一种非确定数据库下的Top-k查询及执行方法，其特点是采用公式定义的执行算法对基于ULDB模型的非确定数据库进行Top-k查询，所述执行算法的公式为：V^*=argmax­v∈V∑ω∈PW(v)(Pr(ω))，且对于任意Vi∈V；所述非确定数据库的Top-k查询具体包括：数据库的预处理、状态表的创建、数据的读取、状态表的更新、可能状态的生成和查询结果的确定步骤。本发明与现有技术相比具有动态规划和深度优先搜索的优点，避免了遍历所有可能世界，快速获得查询结果，能够很好的体现出对象间的实际关系，实用价值高。

主权项

一种非确定数据库下的Top‑k查询及执行方法，其特征在于采用公式定义的执行算法对基于ULDB模型的非确定数据库进行Top‑k查询，所述执行算法的公式为：V^*=argmax­v∈V∑ω∈PW(v)(Pr(ω))，且对于任意Vi∈V，其中：V^*为Top‑k返回的某一查询结果； PW={PW₁,…,PW_N}为可能世界；      V={V₁,…,Vn}是一个长度为k对象的向量集合；Pr(Vi)为PW中所有与其对应元素的概率之和；Vi是某个PWj的前k个实例所分别对应的对象，且V覆盖所有PW中所有元素对应的情况。