可能性天际线查询解析

### 可能性天际线查询解析 #### 1. 引言 在数据库研究领域，近二十年来，人们对偏好查询和不确定数据库的兴趣与日俱增。引入偏好查询的动机是多方面的： - 提供更具表达力的查询语言，更准确地反映用户意图。 - 为检索到的项目提供排序依据，在满足查询的项目集较大时尤为有用。 - 经典查询可能无结果，而放宽条件的查询可能会匹配到数据库中的项目。 数据库偏好查询方法可分为定性和定量两类： - 定量方法：通过单调评分函数定量表达偏好，整体得分与部分得分正相关。代表方法有 top - k 查询和基于模糊集的方法。 - 定性方法：通过二元偏好关系定义偏好，比定量方法更通用。代表方法有基于支配关系（如帕累托序）的方法，包括偏好 SQL、天际线查询等。 本文采用天际线查询的定性视角，并考虑某些属性值不确定的数据库，即不确定数据库。对于不确定数据库的建模和处理，多数方法基于概率论，但也有一些基于可能性理论。与概率论相比，可能性理论具有以下优势： - 模型的定性性质使确定各候选值的程度更容易。 - 概率论中分布程度之和必须为 1，处理不完全已知的分布较为困难。 不过，本文并非声称可能性框架比概率框架“更好”，而是认为它是一种有趣的替代方案，能捕捉不同类型（定性）的不确定性。 #### 2. 天际线查询基础 天际线查询基于帕累托序。设 {G1, G2, ..., Gn} 为一组原子偏好，t >Gi t′ 表示“元组 t 比元组 t′ 更好地满足偏好 Gi”，t ≥Gi t′ 表示“元组 t 至少与元组 t′ 一样好地满足偏好 Gi”。根据帕累托序，元组 t 支配元组 t′ 当且仅当： ∀i ∈{1, ..., n}, t ≥Gi t′ 且 ∃k ∈{1, ..., n}, t >Gk t′ 即 t 在每个偏好上至少与 t′ 一样好，且在至少一个偏好上严格优于 t′。 以下是一个使用偏好 SQL 语法的示例： 考虑一个汽车关系 car，其模式为 (make, category, price, color, mileage)，扩展如下表所示： | make | category | price | color | mileage | | ---- | ---- | ---- | ---- | ---- | | t1 | Opel | roadster | 4500 | blue | 20,000 | | t2 | Ford | SUV | 4000 | red | 20,000 | | t3 | VW | roadster | 5000 | red | 10,000 | | t4 | Opel | roadster | 5000 | red | 8,000 | | t5 | Fiat | roadster | 4500 | red | 16,000 | | t6 | Renault | sedan | 5500 | blue | 24,000 | | t7 | Seat | sedan | 4000 | green | 12,000 | 查询语句为： ```sql select * from car where mileage ≤20,000 preferring (category = ‘SUV’ else category = ‘roadster’) and (make = ‘VW’ else make = ‘Ford’ else make = ‘Opel’); ``` 该查询的目的是保留在偏好子句意义上不被支配的元组。在此例中，t1、t4、t5 和 t7 被丢弃，因为它们被 t2 和 t3 帕累托支配，最终答案为 {t2, t3}。 #### 3. 可能性数据库 ##### 3.1 可能性理论基础 可能性理论提供了一种定性的不确定性模型，信息通过可能性分布表示，该分布对可能情况进行完全预排序。形式上，可能性分布是一个从域 X 到单位区间 [0, 1] 的函数 π，π(a) 表示 a 是所考虑变量的可能值的程度。在一致信息的情况下，归一化条件要求域中至少有一个值 a0 是完全可能的，即 π(a0) = 1。 当域是离散的时，可能性分布可写为 {π1/a1, ..., πn/ah}，其中 ai 是候选值，πi 是其可能性程度。任何事件 E 由两个度量表征：可能性 Π（表示 E 或多或少可能发生）和必要性 N（表示 E 或多或少肯定会发生），且 N(E) = 1 - Π(E)，其中 E 是 E 的对立事件。以下是一些有用的结果： - Π(E1 ∪E2) = max(Π(E1), Π(E2)) - 若 E1 和 E2 在逻辑上独立，Π(E1 ∩E2) = min(Π(E1), Π(E2)) - N(E1 ∩E2) = min(N(E1), N(E2)) - 若 E1 和 E2 在逻辑上独立，N(E1 ∪E2) = max(N(E1), N(E2)) - Π(E) < 1 ⇒N(E) = 0 这两个度量为常规（非模糊）事件集提供了全序，可根据 Π 对不确定事件排序，根据 N 对完全可能的事件排序。 ##### 3.2 可能性数据库 与常规数据库不同，可能性关系数据库 D 可能有一些属性取不精确值，此时使用可能性分布表示该属性的所有或多或少可接受的候选值。 从语义角度看，可能性数据库 D 可解释为一组常规数据库（也称为世界或解释）W1, ..., Wp，记为 rep(D)，每个数据库的可能性或多或少。这种观点在可能性数据库和常规数据库之间建立了直接的语义联系，为定义针对可能性数据库的查询提供了规范方法。 任何世界 Wi 通过在 D 中出现的每个可能性分布中选择一个候选值获得。其中一个常规数据库（设为 Wk）被认为对应于所建模宇宙的实际状态。每个世界 Wi 对应于一系列独立选择，根据前面的公式，分配给它的程度是原始可能性数据库 D 中每个所选候选值的程度的最小值。因此，至少有一个世界是完全可能的，即可能性程度 Π = 1。 例如，考虑一个可能性数据库 D，包含关系 im，其模式为 IM(#i, ac, date, loc)，扩展如下表所示： | #i | ac | date | loc | | ---- | ---- | ---- | ---- | | i1 | {1/a1, 0.6/a2} | {1/d1, 0.7/d3} | c1 | | i3 | {1/a3, 0.3/a4} | d1 | c2 | 由于关系 im 的第一个元组中 ac（或 date）有两个候选值，第二个元组中 ac 有两个候选值，因此可以得到八个世界 W1, W2, ..., W8，每个世界对应一个常规关系 im1 到 im8： - im1 = {⟨i1, a1, d1, c1⟩, ⟨i3, a3, d1, c2⟩}，Π = 1 - im2 = {⟨i1, a1, d3, c1