ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

Application of the pruning technique in dominant query

  • Department of Computer and Control Engineering, Yantai University, Yantai,264005,China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2018.09.006
  • Received Date: 24 May 2018
  • Accepted Date: 18 September 2018
  • Rev Recd Date: 18 September 2018
  • Publish Date: 30 September 2018
    Abstract

  • Abstract

    User preferences can influence the user choices in many cases, and the question of preference query becomes an increasingly important issue in relational databases. In many applications, qualitative preferences can be applied more widely than quantitative preferences. In the existing studies of multi-attribute preferences, preference attributes do not have a dependency relationship, but CP-nets(conditional preference networks) is a graph model that represents multi-attribute qualitative preferences with dependencies. At present, the processing of preference queries mainly uses dominance queries and compares the two outcomes one by one to obtain the outcome that satisfies the user preferences. It can be found that comparing the outcomes in pairs causes great waste of resources. Reduce the number of comparisons of its outcomes is examined. The pruning technique is proposed to be applied to dominance queries, and the path of the flipping sequence is pruned so as to effectively reduce the space for database search.

    Abstract

    User preferences can influence the user choices in many cases, and the question of preference query becomes an increasingly important issue in relational databases. In many applications, qualitative preferences can be applied more widely than quantitative preferences. In the existing studies of multi-attribute preferences, preference attributes do not have a dependency relationship, but CP-nets(conditional preference networks) is a graph model that represents multi-attribute qualitative preferences with dependencies. At present, the processing of preference queries mainly uses dominance queries and compares the two outcomes one by one to obtain the outcome that satisfies the user preferences. It can be found that comparing the outcomes in pairs causes great waste of resources. Reduce the number of comparisons of its outcomes is examined. The pruning technique is proposed to be applied to dominance queries, and the path of the flipping sequence is pruned so as to effectively reduce the space for database search.
    • FullText(HTML)
  • loading
    • References(14)
  • [1]
    LIU J, LIAO S. ExpressiveEfficiency of Two Kinds of Specific CP-Nets[M]. Elsevier Science Inc., 2015.
    [2]
    LIU J L. Research on CP-nets and its expressive power[J]. Acta Automatica Sinica, 2011, 37(3): 290-302.
    [3]
    BRAFMAN R I, DOMSHLAK C. Preference handling-an introductory tutorial[J]. AI Magazine, 2009, 30(1): 58-86.
    [4]
    BOUTILIER C, BRAFMAN R I, DOMSHLAK C, et al. CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[J]. Journal of Artificial Intelligence Research, 2011, 21(1): 135-191.
    [5]
    ZANUTTINI B. Learning conditional preference networks with queries[C]// International Joint Conference on Artificial Intelligence. Morgan Kaufmann Publishers Inc. 2009: 1930-1935.
    [6]
    ZANUTTINI B. Learning conditional preference networks[J]. Artificial Intelligence, 2010, 174(11): 685-703.
    [7]
    CONITZER V. Making decisions based on the preferences of multiple agents[J]. Communications of the ACM, 2010, 53(3): 84-94.
    [8]
    TANG P Z, LIN F Z. Computer-aided proofs of Arrow's and other impossibility theorems [J]. Artificial Intelligence, 2009, 173(11): 1041-1053.
    [9]
    LANG J. Logical preference representation and combinatorial vote[J]. Annals of Mathematics & Artificial Intelligence, 2004, 42(1-3): 37-71.
    [10]
    BRAFMAN R I, DOMSHLAK C, SHIMONY S E. On graphical modeling of preference and importance[J]. Journal of Artificial Intelligence Research, 2006, 25(1): 389-424.
    [11]
    BOUVERET S, ENDRISS U, LANG J. Conditional importance networks: a graphical language for representing ordinal, monotonic preferences over sets of goods[C]// Proceedings of the 21st International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann Publishers Inc. 2009: 67-72.
    [12]
    孙雪姣, 刘惊雷. CP-nets的可满足性及一致性研究[J]. 计算机研究与发展, 2012, 49(4): 754-762.
    SUN X, LIU J L. On the satisfiability and consistency for CP-nets[J]. Journal of Computer Research & Development, 2012, 49(4):754-762.
    [13]
    刘惊雷, 廖士中, 张伟. CP-nets的完备性及一致性研究[J]. 软件学报, 2012, 23(6):1531-1541.
    LIU J L, LIAO S Z, ZHANG W. On the completeness and consistency for CP-nets[J]. Journal of Software, 2012, 23(6):1531-1541.
    [14]
    CORMEN T T, LEISERSON C E, RIVEST R L. Introduction to algorithms [J]. Resonance, 1996, 1(9): 14-24.)
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    LIU J, LIAO S. ExpressiveEfficiency of Two Kinds of Specific CP-Nets[M]. Elsevier Science Inc., 2015.
    [2]
    LIU J L. Research on CP-nets and its expressive power[J]. Acta Automatica Sinica, 2011, 37(3): 290-302.
    [3]
    BRAFMAN R I, DOMSHLAK C. Preference handling-an introductory tutorial[J]. AI Magazine, 2009, 30(1): 58-86.
    [4]
    BOUTILIER C, BRAFMAN R I, DOMSHLAK C, et al. CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[J]. Journal of Artificial Intelligence Research, 2011, 21(1): 135-191.
    [5]
    ZANUTTINI B. Learning conditional preference networks with queries[C]// International Joint Conference on Artificial Intelligence. Morgan Kaufmann Publishers Inc. 2009: 1930-1935.
    [6]
    ZANUTTINI B. Learning conditional preference networks[J]. Artificial Intelligence, 2010, 174(11): 685-703.
    [7]
    CONITZER V. Making decisions based on the preferences of multiple agents[J]. Communications of the ACM, 2010, 53(3): 84-94.
    [8]
    TANG P Z, LIN F Z. Computer-aided proofs of Arrow's and other impossibility theorems [J]. Artificial Intelligence, 2009, 173(11): 1041-1053.
    [9]
    LANG J. Logical preference representation and combinatorial vote[J]. Annals of Mathematics & Artificial Intelligence, 2004, 42(1-3): 37-71.
    [10]
    BRAFMAN R I, DOMSHLAK C, SHIMONY S E. On graphical modeling of preference and importance[J]. Journal of Artificial Intelligence Research, 2006, 25(1): 389-424.
    [11]
    BOUVERET S, ENDRISS U, LANG J. Conditional importance networks: a graphical language for representing ordinal, monotonic preferences over sets of goods[C]// Proceedings of the 21st International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann Publishers Inc. 2009: 67-72.
    [12]
    孙雪姣, 刘惊雷. CP-nets的可满足性及一致性研究[J]. 计算机研究与发展, 2012, 49(4): 754-762.
    SUN X, LIU J L. On the satisfiability and consistency for CP-nets[J]. Journal of Computer Research & Development, 2012, 49(4):754-762.
    [13]
    刘惊雷, 廖士中, 张伟. CP-nets的完备性及一致性研究[J]. 软件学报, 2012, 23(6):1531-1541.
    LIU J L, LIAO S Z, ZHANG W. On the completeness and consistency for CP-nets[J]. Journal of Software, 2012, 23(6):1531-1541.
    [14]
    CORMEN T T, LEISERSON C E, RIVEST R L. Introduction to algorithms [J]. Resonance, 1996, 1(9): 14-24.)
    Recommended articles
    TrendMD
    Volume 48 Issue 9 page: 723-729
    Cover

    Article Metrics

    Article views (60) PDF downloads(128)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return