论文部分内容阅读
正则化路径查询是数据库一种重要的查询，它确定是否存在一条路径满足给定的正则表达式。本文以表示偏好知识的CP-nets(条件偏好网)模型出发，研究该模型上的正则化路径查询算法问题。首先从数据库的观点给出了偏好数据库的两类查询，顶点查询和路径查询，并证明了偏好数据库的表达能力强于关系数据库。其次，通过构造正则表达式的语法解析二叉树，求出各自原子表达式诱导的可达关系，从而利用动态规划法递归求解出CP-nets上正则表达式所诱导的可达关系，并证明了算法的正确性，分析了其组合复杂度。最后给出CP-nets上路径查询算法的可能应用场景，它可以使用在用户偏好操作序列的规划中。