|
|
|
| Regular Path Query on CP-nets |
| LIU Jing-Lei1,2, LIAO Shi-Zhong1 |
1School of Computer Science and Technology, Tianjin University, Tianjin 300072
2School of Computer and Control Engineering, Yantai University, Yantai 264005 |
|
|
|
|
Abstract A formal preference knowledge representation framework, conditional preference networks (CP-nets), is introduced, and regular path query on the model is studied. Firstly, two kinds of queries, vertex query and path query,are given from the point of view of the database theory,and the expressive ability of preference database is proved to be stronger than that of relational database. Then, the induced reach ability relations of each atom expressions are obtained by constructing the syntax parse binary tree of regular expression, thereafter, the reach ability relation induced by regular expression of root vertex is obtained by means of dynamic programming. Moreover, the correctness and combined complexity of this algorithm are proved. Finally, a possible application scenario of regular path query is given, which demonstrates it can be applied in the preference planning sequence.
|
|
Received: 30 June 2013
|
|
|
|
|
|
|
|
|
2014, Vol. 27 
