{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T04:10:40Z","timestamp":1791259840046,"version":"4.1.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,11,2]],"date-time":"2016-11-02T00:00:00Z","timestamp":1478044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"French State"},{"name":"\u201cInvestments for the Future\u201d Programme IdEx Bordeaux--CPU","award":["ANR-10-IDEX-03-02"],"award-info":[{"award-number":["ANR-10-IDEX-03-02"]}]},{"name":"CNRS under the MASTODONS-PETASKY initiative"},{"name":"SPEEDDATA research project"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2016,12,23]]},"abstract":"<jats:p>\n            Given a table\n            <jats:italic>T<\/jats:italic>\n            (\n            <jats:italic>Id<\/jats:italic>\n            ,\n            <jats:italic>D<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , \u2026,\n            <jats:italic>\n              D\n              <jats:sub>d<\/jats:sub>\n            <\/jats:italic>\n            ), the skycube of\n            <jats:italic>T<\/jats:italic>\n            is the set of skylines with respect to to all nonempty subsets (subspaces) of the set of all dimensions {\n            <jats:italic>D<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , \u2026,\n            <jats:italic>\n              D\n              <jats:sub>d<\/jats:sub>\n            <\/jats:italic>\n            }. To optimize the evaluation of any skyline query, the solutions proposed so far in the literature either (i) precompute all of the skylines or (ii) use compression techniques so that the derivation of any skyline can be done with little effort. Even though solutions (i) are appealing because skyline queries have optimal execution time, they suffer from time and space scalability because the number of skylines to be materialized is exponential with respect to\n            <jats:italic>d<\/jats:italic>\n            . On the other hand, solutions (ii) are attractive in terms of memory consumption, but as we show, they also have a high time complexity. In this article, we make contributions to both kinds of solutions. We first observe that skyline patterns are monotonic. This property leads to a simple yet efficient solution for full and partial skycube materialization when the skyline with respect to all dimensions, the topmost skyline, is small. On the other hand, when the topmost skyline is large relative to the size of the input table, it turns out that functional dependencies, a fundamental concept in databases, uncover a monotonic property between skylines. Equipped with this information, we show that closed attributes sets are fundamental for partial and full skycube materialization. Extensive experiments with real and synthetic datasets show that our solutions generally outperform state-of-the-art algorithms.\n          <\/jats:p>","DOI":"10.1145\/2955092","type":"journal-article","created":{"date-parts":[[2016,11,4]],"date-time":"2016-11-04T12:49:04Z","timestamp":1478263744000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Skycube Materialization Using the Topmost Skyline or Functional Dependencies"],"prefix":"10.1145","volume":"41","author":[{"given":"Sofian","family":"Maabout","sequence":"first","affiliation":[{"name":"University of Bordeaux, Talence, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carlos","family":"Ordonez","sequence":"additional","affiliation":[{"name":"University of Houston, TX, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Patrick Kamnang","family":"Wanko","sequence":"additional","affiliation":[{"name":"University of Bordeaux, Talence, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicolas","family":"Hanusse","sequence":"additional","affiliation":[{"name":"University of Bordeaux-CNRS, Talence, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,11,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the VLDB Conference.","author":"Agarwal Sameet","year":"1996","unstructured":"Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , and Sunita Sarawagi . 1996 . On the computation of multidimensional aggregates . In Proceedings of the VLDB Conference. Sameet Agarwal, Rakesh Agrawal, Prasad Deshpande, Ashish Gupta, Jeffrey F. Naughton, Raghu Ramakrishnan, and Sunita Sarawagi. 1996. On the computation of multidimensional aggregates. In Proceedings of the VLDB Conference."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the VLDB Conference.","author":"Agrawal Sanjay","unstructured":"Sanjay Agrawal , Surajit Chaudhuri , and Vivek R. Narasayya . 2000. Automated selection of materialized views and indexes in SQL databases . In Proceedings of the VLDB Conference. Sanjay Agrawal, Surajit Chaudhuri, and Vivek R. Narasayya. 2000. Automated selection of materialized views and indexes in SQL databases. In Proceedings of the VLDB Conference."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412343"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2661891"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656550"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/78922.78924"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.131"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250299"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28472-4_9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24627-5_7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375749"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0029-7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063814"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516468"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233333"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739067"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0317-y"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2338626.2338633"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11547686_10"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/645339.650138"},{"key":"e_1_2_1_23_1","volume-title":"The Theory of Relational Databases","author":"Maier David","unstructured":"David Maier . 1983. The Theory of Relational Databases . Computer Science Press, Rockville , MD. David Maier. 1983. The Theory of Relational Databases. Computer Science Press, Rockville, MD."},{"key":"e_1_2_1_24_1","volume-title":"Design of Relational Databases","author":"Mannila Heikki","unstructured":"Heikki Mannila and Kari-Jouko R\u00e4ih\u00e4 . 1992. Design of Relational Databases . Addison-Wesley . Heikki Mannila and Kari-Jouko R\u00e4ih\u00e4. 1992. Design of Relational Databases. Addison-Wesley."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-023X(94)90023-X"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the VLDB Conference.","author":"Morse M. D.","unstructured":"M. D. Morse , J. M. Patel , and H. V. Jagadish . 2007. Efficient skyline computation over low-cardinality domains . In Proceedings of the VLDB Conference. M. D. Morse, J. M. Patel, and H. V. Jagadish. 2007. Efficient skyline computation over low-cardinality domains. In Proceedings of the VLDB Conference."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/645504.656418"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.44"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Carlos Ordonez Wellington Cabrera and Achyuth Gurram. 2016. Comparing columnar row and array DBMSs to process recursive queries on graphs. Information Systems. Accepted.  Carlos Ordonez Wellington Cabrera and Achyuth Gurram. 2016. Comparing columnar row and array DBMSs to process recursive queries on graphs. Information Systems. Accepted.","DOI":"10.1016\/j.is.2016.04.006"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the VLDB Conference.","author":"Pei Jian","year":"2005","unstructured":"Jian Pei , Wen Jin , Martin Ester , and Yufei Tao . 2005 . Catching the best views of skyline: A semantic approach based on decisive subspaces . In Proceedings of the VLDB Conference. Jian Pei, Wen Jin, Martin Ester, and Yufei Tao. 2005. Catching the best views of skyline: A semantic approach based on decisive subspaces. In Proceedings of the VLDB Conference."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189769.1189774"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920948"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687638"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536365"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2389241.2389245"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2188349.2188357"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-007-0083-9"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the VLDB Conference.","author":"Yuan Yidong","year":"2005","unstructured":"Yidong Yuan , Xuemin Lin , Qing Liu , Wei Wang , Jeffrey Xu Yu , and Qing Zhang . 2005 . Efficient computation of the skyline cube . In Proceedings of the VLDB Conference. Yidong Yuan, Xuemin Lin, Qing Liu, Wei Wang, Jeffrey Xu Yu, and Qing Zhang. 2005. Efficient computation of the skyline cube. In Proceedings of the VLDB Conference."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253288"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2955092","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2955092","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:23Z","timestamp":1750222583000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2955092"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,2]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12,23]]}},"alternative-id":["10.1145\/2955092"],"URL":"https:\/\/doi.org\/10.1145\/2955092","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,2]]},"assertion":[{"value":"2015-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}