{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:17:49Z","timestamp":1750306669518,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,5,1]],"date-time":"2014-05-01T00:00:00Z","timestamp":1398902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,5]]},"abstract":"<jats:p>\n            In a probabilistic database, deciding if a tuple\n            <jats:italic>u<\/jats:italic>\n            is\n            <jats:italic>better<\/jats:italic>\n            than another tuple\n            <jats:italic>v<\/jats:italic>\n            has not a univocal solution, rather it depends on the specific\n            <jats:italic>Probabilistic Ranking Semantics<\/jats:italic>\n            (PRS) one wants to adopt so as to combine together tuples' scores and probabilities.\n          <\/jats:p>\n          <jats:p>\n            In deterministic databases it is known that skyline queries are a remarkable alternative to (top-\n            <jats:italic>k<\/jats:italic>\n            ) ranking queries, because they remove from the user the burden of specifying a scoring function that combines values of different attributes into a single score. The skyline of a deterministic relation\n            <jats:italic>R<\/jats:italic>\n            is the set of\n            <jats:italic>undominated<\/jats:italic>\n            tuples in\n            <jats:italic>R<\/jats:italic>\n            -- tuple\n            <jats:italic>u<\/jats:italic>\n            dominates tuple\n            <jats:italic>v<\/jats:italic>\n            iff on all the attributes of interest\n            <jats:italic>u<\/jats:italic>\n            is better than or equal to\n            <jats:italic>v<\/jats:italic>\n            and strictly better on at least one attribute. Domination is equivalent to having\n            <jats:italic>s<\/jats:italic>\n            (\n            <jats:italic>u<\/jats:italic>\n            ) \u2265\n            <jats:italic>s<\/jats:italic>\n            (\n            <jats:italic>v<\/jats:italic>\n            ) for\n            <jats:italic>all<\/jats:italic>\n            monotone scoring functions\n            <jats:italic>s<\/jats:italic>\n            ().\n          <\/jats:p>\n          <jats:p>\n            The skyline of a probabilistic relation\n            <jats:italic>\n              R\n              <jats:sup>p<\/jats:sup>\n            <\/jats:italic>\n            can be similarly defined as the set of\n            <jats:italic>P-undominated<\/jats:italic>\n            tuples in\n            <jats:italic>\n              R\n              <jats:sup>p<\/jats:sup>\n            <\/jats:italic>\n            , where now\n            <jats:italic>u<\/jats:italic>\n            P-dominates\n            <jats:italic>v<\/jats:italic>\n            iff, whatever monotone scoring function one would use to combine the skyline attributes,\n            <jats:italic>u<\/jats:italic>\n            is reputed better than\n            <jats:italic>v<\/jats:italic>\n            by the PRS at hand. This definition, which is applicable to arbitrary ranking semantics and probabilistic correlation models, is parametric in the adopted PRS, thus it ensures that ranking and skyline queries will always return consistent results.\n          <\/jats:p>\n          <jats:p>\n            In this article we provide an overall view of the problem of computing the skyline of a probabilistic relation. We show how, under mild conditions that indeed hold for all known PRSs, checking P-domination can be cast into an optimization problem, whose complexity we characterize for a variety of combinations of ranking semantics and correlation models. For each analyzed case we also provide specific\n            <jats:italic>P-domination rules<\/jats:italic>\n            , which are exploited by the algorithm we detail for the case where the probabilistic model is known to the query processor. We also consider the case in which the probability of tuple events can only be obtained through an oracle, and describe another skyline algorithm for this loosely integrated scenario. Our experimental evaluation of P-domination rules and skyline algorithms confirms the theoretical analysis.\n          <\/jats:p>","DOI":"10.1145\/2602135","type":"journal-article","created":{"date-parts":[[2014,5,27]],"date-time":"2014-05-27T12:56:59Z","timestamp":1401195419000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Domination in the Probabilistic World"],"prefix":"10.1145","volume":"39","author":[{"given":"Ilaria","family":"Bartolini","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Bologna, Bologna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Ciaccia","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Bologna, Bologna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Patella","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Bologna, Bologna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,5,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274605"},{"volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB'06)","author":"Agrawal P.","key":"e_1_2_2_2_1","unstructured":"P. Agrawal , O. Benjelloun , A. Das Sarma , C. Hayworth , S. U. Nabar , T. Sugihara , and J. Widom . 2006. Trio: A system for data, uncertainty, and lineage . In Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB'06) . ACM Press, New York, 1151--1154. P. Agrawal, O. Benjelloun, A. Das Sarma, C. Hayworth, S. U. Nabar, T. Sugihara, and J. Widom. 2006. Trio: A system for data, uncertainty, and lineage. In Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB'06). ACM Press, New York, 1151--1154."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1966385.1966390"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/MPRV.2007.27"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412343"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.102"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0080-z"},{"volume-title":"Proceedings of the 17th International Conference on Data Engineering (ICDE'01)","author":"Borzsonyi S.","key":"e_1_2_2_8_1","unstructured":"S. Borzsonyi , D. Kossmann , and K. Stocker . 2001. The skyline operator . In Proceedings of the 17th International Conference on Data Engineering (ICDE'01) . IEEE Computer Society, 421--430. S. Borzsonyi, D. Kossmann, and K. Stocker. 2001. The skyline operator. In Proceedings of the 17th International Conference on Data Engineering (ICDE'01). IEEE Computer Society, 421--430."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2536669.2536671"},{"volume-title":"Proceedings of the 19th International Conference on Data Engineering (ICDE'03)","author":"Chomicki J.","key":"e_1_2_2_10_1","unstructured":"J. Chomicki , P. Godfrey , J. Gryz , and D. Liang . 2003. Skyline with presorting . In Proceedings of the 19th International Conference on Data Engineering (ICDE'03) . IEEE Computer Society, 717--719. J. Chomicki, P. Godfrey, J. Gryz, and D. Liang. 2003. Skyline with presorting. In Proceedings of the 19th International Conference on Data Engineering (ICDE'03). IEEE Computer Society, 717--719."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2003.814918"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.75"},{"key":"e_1_2_2_13_1","unstructured":"R. G. Cowell P. Dawid S. L. Lauritzen and D. J. Spiegelhalter. 1999. Probabilistic Networks and Expert Systems. Springer.   R. G. Cowell P. Dawid S. L. Lauritzen and D. J. Spiegelhalter. 1999. Probabilistic Networks and Expert Systems. Springer."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.006"},{"volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases (VLDB'04)","author":"Dalvi N. N.","key":"e_1_2_2_15_1","unstructured":"N. N. Dalvi and D. Suciu . 2004. Efficient query evaluation on probabilistic databases . In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB'04) . Morgan Kaufmann, 864--875. N. N. Dalvi and D. Suciu. 2004. Efficient query evaluation on probabilistic databases. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB'04). Morgan Kaufmann, 864--875."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.174"},{"volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07)","author":"Dong X. L.","key":"e_1_2_2_17_1","unstructured":"X. L. Dong , A. Y. Halevy , and C. Yu . 2007. Data integration with uncertainty . In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07) . ACM Press, New York, 687--698. X. L. Dong, A. Y. Halevy, and C. Yu. 2007. Data integration with uncertainty. In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07). ACM Press, New York, 687--698."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.94"},{"key":"e_1_2_2_19_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman San Francisco CA.   M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman San Francisco CA."},{"volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05)","author":"Godfrey P.","key":"e_1_2_2_20_1","unstructured":"P. Godfrey , R. Shipley , and J. Gryz . 2005. Maximal vector computation in large data sets . In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05) . ACM Press, 229--240. P. Godfrey, R. Shipley, and J. Gryz. 2005. Maximal vector computation in large data sets. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05). ACM Press, 229--240."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.192"},{"key":"e_1_2_2_22_1","unstructured":"J. Kleinberg and E. Tardos. 2006. Algorithm Design. Addison-Wesley.   J. Kleinberg and E. Tardos. 2006. Algorithm Design. Addison-Wesley."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687685"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0220-3"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767896"},{"volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07)","author":"Morse M. D.","key":"e_1_2_2_26_1","unstructured":"M. D. Morse , J. M. Patel , and H. V. Jagadish . 2007. Efficient skyline computation over low-cardinality domains . In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07) . ACM Press, New York, 267--278. M. D. Morse, J. M. Patel, and H. V. Jagadish. 2007. Efficient skyline computation over low-cardinality domains. In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07). ACM Press, New York, 267--278."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann","author":"Pearl J.","key":"e_1_2_2_28_1","unstructured":"J. Pearl . 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann , San Francisco, CA . J. Pearl. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco, CA."},{"volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07)","author":"Pei J.","key":"e_1_2_2_29_1","unstructured":"J. Pei , B. Jiang , X. Li , and Y. Yuan . 2007. Probabilistic skylines on uncertain data . In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07) . ACM Press, New York, 15--26. J. Pei, B. Jiang, X. Li, and Y. Yuan. 2007. Probabilistic skylines on uncertain data. In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB'07). ACM Press, New York, 15--26."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367935"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386118.1386119"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.48"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.266"},{"volume-title":"Proceedings of the 16th International Conference on Database Systems for Advanced Applications (DASFAA'11)","author":"Yan D.","key":"e_1_2_2_34_1","unstructured":"D. Yan and W. Ng . 2011. Robust ranking of uncertain data . In Proceedings of the 16th International Conference on Database Systems for Advanced Applications (DASFAA'11) . 254--268. D. Yan and W. Ng. 2011. Robust ranking of uncertain data. In Proceedings of the 16th International Conference on Database Systems for Advanced Applications (DASFAA'11). 254--268."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.90"},{"volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05)","author":"Yuan Y.","key":"e_1_2_2_36_1","unstructured":"Y. Yuan , X. Lin , Q. Liu , W. Wang , J. X. Yu , and Q. Zhang . 2005. Efficient computation of the skyline cube . In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05) . ACM Press, New York, 241--252. Y. Yuan, X. Lin, Q. Liu, W. Wang, J. X. Yu, and Q. Zhang. 2005. Efficient computation of the skyline cube. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05). ACM Press, New York, 241--252."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559897"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2188349.2188356"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2008.4498380"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-009-7050-y"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2602135","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2602135","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:00:47Z","timestamp":1750230047000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2602135"}},"subtitle":["Computing Skylines for Arbitrary Correlations and Ranking Semantics"],"short-title":[],"issued":{"date-parts":[[2014,5]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["10.1145\/2602135"],"URL":"https:\/\/doi.org\/10.1145\/2602135","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2014,5]]},"assertion":[{"value":"2013-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}