×

zbMATH — the first resource for mathematics

Incremental evaluation of continuous preference queries. (English) Zbl 1440.68059
Summary: Over recent decades, several studies regarding the incorporation of preferences into query languages have been developed in the database research field. The enthusiasm and interest in this research topic is due to its use in important practical applications such as e-commerce and social networks. An example of a solid work in this research field for relational databases is the CPrefSQL language that allows for the execution of queries with conditional preferences. More recently, due to the broad spectrum of new data stream applications, the interest in continuous query processing by the database community has shown a notable increase. The evaluation of preferences in continuous queries poses additional challenges, since data change rapidly in data stream scenarios. In order to aid in dealing with these issues, we proposed an incremental and efficient method for evaluating continuous CPrefSQL queries. We revisited the state of the art algorithms for the evaluation of continuous CPrefSQL queries and compared these with our new approach. We conducted a detailed complexity analysis and an extensive set of experiments with synthetic and real datasets, which shows that our proposed algorithm has considerably superior performance.
MSC:
68P15 Database theory
68P20 Information storage and retrieval of data
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arasu, A.; Babu, S.; Widom, J., The CQL continuous query language: semantic foundations and query execution, VLDB J., 15, 2, 121-142 (2006)
[2] Börzsönyi, S.; Kossmann, D.; Stocker, K., The skyline operator, Proceedings of the International Conference on Data Engineering (ICDE), Heidelberg, Germany, 421-430 (2001)
[3] Boutilier, C.; Brafman, R. I.; Domshlak, C.; Hoos, H. H.; Poole, D., CP-Nets: a tool for representing and reasoning with conditional ceteris paribus preference statements, J. Artif. Intel. Res., 21, 135-191 (2004) · Zbl 1080.68685
[4] Brafman, R. I.; Domshlak, C., Introducing variable importance tradeoffs into CP-nets, Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), Edmonton, Canada, 69-76 (2002)
[5] Brafman, R. I.; Domshlak, C.; Shimony, S. E., On graphical modeling of preference and importance, J. Artif. Intel. Res., 25, 389-424 (2006) · Zbl 1182.68325
[6] Chan, C.-Y.; Jagadish, H. V.; Tan, K.-L.; Tung, A. K.H.; Zhang, Z., Finding k-dominant skylines in high dimensional space, ACM SIGMOD International Conference on Management of Data, Chicago, USA, 503-514 (2006)
[7] Chaudhuri, S.; Gravano, L., Evaluating top-k selection queries, Proceedings of the International Conference on Very Large Data Bases (VLDB), Edinburgh, Scotland, 399-410 (1999)
[8] Chomicki, J., Preference formulas in relational queries, ACM Tran. Database Syst., 28, 4, 427-466 (2003)
[9] Chomicki, J., Logical foundations of preference queries, IEEE Data Eng. Bull., 34, 2, 4-11 (2011)
[10] Chomicki, J.; Ciaccia, P.; Meneghetti, N., Skyline queries, front and back, ACM SIGMOD Record, 42, 3, 6-18 (2013)
[11] de Amo, S.; Bueno, M. L.d. P., Continuous processing of conditional preference queries, Simpósio Brasileiro de Banco de Dados (SBBD), Florianópolis, Brasil (2011)
[12] de Amo, S.; Ribeiro, M. R., CPref-SQL: A query language supporting conditional preferences, Proceedings of the ACM Symposium on Applied Computing (ACM SAC), Honolulu, Hawaii, USA, 1573-1577 (2009)
[13] Höfner, P.; Möller, B., Dijkstra, floyd and warshall meet kleene, Formal Aspects Comput., 24, 4-6, 459-476 (2012) · Zbl 1259.68243
[14] Ilyas, I. F.; Beskales, G.; Soliman, M. A., A survey of top-k query processing techniques in relational database systems, ACM Comput. Surv., 40, 4, 1-58 (2008)
[15] Kahn, A. B., Topological sorting of large networks, Commun. ACM, 5, 11, 558-562 (1962) · Zbl 0106.32602
[16] Kießling, W.; Endres, M.; Wenzel, F., The preference SQL system: an overview, IEEE Data Eng. Bull., 34, 2, 11-18 (2011)
[18] Kontaki, M.; Papadopoulos, A. N.; Manolopoulos, Y., Continuous top-k dominating queries in subspaces, Proceedings of the Panhellenic Conference on Informatics, 31-35 (2008), IEEE: IEEE Samos, Greece
[19] Kontaki, M.; Papadopoulos, A. N.; Manolopoulos, Y., Continuous processing of preference queries in data streams, Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Spindleruv Mlýn, Czech Republic, 47-60 (2010)
[21] Lee, Y. W.; Lee, K. Y.; Kim, M. H., Efficient processing of multiple continuous skyline queries over a data stream, Inf. Sci. (Ny), 221, 316-337 (2013)
[22] Lin, X.; Yuan, Y.; Wang, W.; Lu, H., Stabbing the sky: Efficient skyline computation over sliding windows, Proceedings of the International Conference on Data Engineering (ICDE), Tokyo, Japan, 502-513 (2005)
[23] Lin, X.; Yuan, Y.; Zhang, Q.; Zhang, Y., Selecting stars: The k most representative skyline operator, Proceedings of the International Conference on Data Engineering (ICDE), Istambul, Turkey, 86-95 (2007)
[24] Morse, M.; Patel, J. M.; Grosky, W. I., Efficient continuous skyline computation, Inf. Sci. (Ny), 177, 17, 3411-3437 (2007)
[25] Pereira, F. S.F.; de Amo, S., Evaluation of conditional preference queries, J. Inform. Data Manag., 1, 3, 503-518 (2010)
[26] Petit, L.; de Amo, S.; Roncancio, C.; Labbé, C., Top-k context-aware queries on streams, Proceedings of the International Conference on Database and Expert Systems Applications (DEXA), Vienna, Austria, 397-411 (2012)
[27] Petit, L.; Labbé, C.; Roncancio, C., An algebric window model for data stream management, Proceedings of the ACM International Workshop on Data Engineering for Wireless and Mobile Access (MobiDE), Indianapolis, Indiana, USA, 17-24 (2010)
[28] Ribeiro, M. R.; Pereira, F. S.F.; Dias, V. V.S., Efficient algorithms for processing preference queries, Proceedings of the ACM Symposium on Applied Computing (ACM SAC), Pisa, Italy, 972-979 (2016)
[29] Santoso, B. J.; Chiu, G.-M., Close dominance graph: an efficient framework for answering continuous top-dominating queries, IEEE Trans. Knowl. Data Eng., 26, 8, 1853-1865 (2014)
[30] Sarkas, N.; Das, G.; Koudas, N.; Tung, A. K.H., Categorical skylines for streaming data, Proceedings of the ACM SIGMOD International Conference on Management of Data, Vancouver, BC, Canada, 239-250 (2008)
[31] Tao, Y.; Papadias, D., Maintaining sliding window skylines on data streams, IEEE Transactions on Knowledge and Data Engineering (TKDE), 18, 3, 377-391 (2006)
[32] Wilson, N., Extending cp-nets with stronger conditional preference statements, Proceedings of the AAAI National Conference on Artificial Intelligence, San Jose, California, USA, 735-741 (2004)
[33] Wilson, N., Computational techniques for a simple theory of conditional preferences, Artif. Intel. J., 175, 7-8, 1053-1091 (2011) · Zbl 1225.68250
[35] Yiu, M. L.; Mamoulis, N., Efficient processing of top-k dominating queries on multi-dimensional data, Proceedings of the International Conference on Very Large Data Bases (VLDB), Vienna, Austria, 483-494 (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.