实时跟踪移动单元的数据库与平面空间数据库拓扑属性表达

### 实时跟踪移动单元的数据库与平面空间数据库拓扑属性表达 #### 实时跟踪移动单元数据库相关 在实时跟踪移动单元的数据库场景中，对于查询处理有着特定的算法和逻辑。考虑查询“RETRIEVE o FROM Moving - objects WHERE C1 ∧ C2”，其中 C1 和 C2 分别是条件的静态和动态部分。其整体处理算法步骤如下： 1. 利用底层数据库处理查询“RETRIEVE o FROM Moving - objects WHERE C1”，设检索到的对象集合为 O。 2. 利用底层数据库检索 O 中对象正在行驶的路线集合 R。 3. 对于 C2 中出现的每个原子谓词 p 和 R 中的每条路线 r1，使用任何空间索引方案检索区间列表 Int(r1, p)。 4. 使用之前介绍的算法，为每条路线 r1 计算区间列表 Int(r1, q)。 5. 对于每条路线 r1 和在 r1 上行驶的每个对象 o1，使用定理 3 中给出的公式计算其满足 q 的概率。 该算法的复杂度方面，如果 L1, L2, ..., Lk 是与 q 中出现的原子谓词相对应的区间列表，l 是这些列表的长度之和，m 是 q 的长度，那么上述过程的复杂度为 O(lm)。 在相关工作方面，涉及到多个研究领域： - **数据库中的不确定性和不完整信息**：当前工作关注为每个移动对象的位置初始关联何种不确定性，而现有工作主要关注在数据库中引入不确定性后的管理和推理。并且，本文的不确定性处理问题结合了时空方面，这是之前未被研究过的。 - **移动计算中的位置管理**：在蜂窝架构中，当呼叫或向移动用户发送消息时，网络基础设施需要定位用户当前所在的小区。现有工作致力于分配和分布位置数据库，以最小化查找时间和更新开销。不过，小区粒度的不确定性在很多情况下是不够的，例如在卫星网络中，小区直径范围从数百到数千英里。 - **约束数据库**：位置属性可以被视为一种约束或广义元组，满足约束的元组被认为在数据库中。约束数据库已分别应用于时间和空间领域，并且可以作为实现所提出的更新策略和查询处理算法的框架。 与之前工作相比，本文有两个重要扩展：一是引入了新的定量概率模型和处理范围查询的方法，之前采用定性的“可能”和“必须”查询语义；二是将不确定性作为与偏差分开的概念引入，之前的更新策略无法区分两者。本文讨论的位置更新策略在两个方面与之前不同：一是在决定何时发送位置更新消息时考虑了不确定性；二是它们是航位推算策略，每次位置更新消息都会提供不确定性，即偏差的界限。 最后，本文提出了航位推算策略用于更新移动对象的数据库位置和处理运动数据库的范围查询。引入了成本模型来平衡通信、不确定性和偏差之间的权衡，通过为不确定性单位、偏差单位和通信单位分配成本。还介绍了两种航位推算策略：自适应航位推算（adr）和断开连接检测航位推算（dtdr），它们都会根据当前运动模式调整不确定性阈值。通过模拟测试平台比较了 adr、dtdr 和速度航位推算（sdr）的信息成本，结果表明 adr 具有更低的信息成本，甚至可能比 sdr 低六倍。此外，还提出了运动数据库查询处理的概率模型和算法，对于查询“检索当前在给定多边形 P 内的移动对象”，答案是每个对象与当前在 P 内的概率相关联的对象集合。同时，对于移动对象到达时间更新问题，本文关于位置更新问题的结果可以直接应用。 下面是该查询处理算法的流程图： ```mermaid graph TD A[开始] --> B[处理查询 RETRIEVE o FROM Moving - objects WHERE C1] B --> C[获取对象集合 O] C --> D[检索路线集合 R] D --> E[为 C2 中原子谓词和 R 中路线检索 Int(r1, p)] E --> F[计算 Int(r1, q)] F --> ```