CP-nets上的正则化路径查询*

从表示偏好知识的条件偏好网(CP-nets)模型出发，研究该模型上的正则化路径查询问题.首先从数据库的观点给出偏好数据库的两类查询(顶点查询和路径查询)，并证明偏好数据库的表达能力强于关系数据库.其次，通过构造正则表达式的语法解析二叉树，求出各自原子表达式诱导的可达关系，从而利用动态规划法求解出CP-nets上正则表达式所诱导的可达关系，并证明算法的正确性，分析其组合复杂度.最后，给出正则化路径查询的可能应用，即可在偏好操作序列的规划中使用.