Вертикальное фрагментирование – один из аспектов организации хранения данных в реляционных СУБД. Несмотря на то, что вертикальное фрагментирование известно достаточно давно, его автоматизация проработана существенно хуже, чем у других подходов. Одна из причин такого положения дел – NP-трудность большинства содержательных формулировок данной задачи. Выбор "хорошей" схемы вертикального фрагментирования до сих пор во многом остается искусством и отдается на откуп администратору базы данных.

В докладе представлен обзор идей, алгоритмов и систем, посвященных вертикальному фрагментированию. Прослеживается эволюция идей с 70-х годов и до наших дней. Рассматриваются два широких класса приближенных алгоритмов решения статической задачи вертикального фрагментирования – эвристические и стоимостные. Представлены методы, основанные на близости атрибутов (графовые методы и матричная кластеризация); методы, использующие data mining и другие. Сформулирована задача динамического вертикального фрагментирования, представлено несколько подходов к ее решению. Рассмотрены несколько работ, посвященных вертикальному фрагментированию в индустриальных СУБД.

В заключении представлено современное видение вертикального фрагментирования. Рассматриваются архитектуры современных СУБД, учитывающих вертикальное фрагментирование. Приводится описание того, каким образом колоночные СУБД и современные СУБД в оперативной памяти получают выигрыш от применения этого способа организации хранения данных.

Презентация доклада в формате pdf.

Видеозапись доклада.

Литература:

1. Abadi, D., Boncz, P., Harizopoulos, S.: The Design and Implementation of Modern Column-Oriented Database Systems. Now Publishers Inc., Hanover, MA, USA (2013)
2. Agrawal, S., Narasayya, V., Yang, B.: Integrating vertical and horizontal partitioning into automated physical database design. In: Proceedings of the 2004 ACM SIGMOD international conference on Management of data. pp. 359–370. SIGMOD '04, ACM, New York, NY, USA (2004)
3. Ailamaki, A., DeWitt, D.J., Hill, M.D., Skounakis, M.: Weaving relations for cache performance. In: Proceedings of the 27th International Conference on Very Large Data Bases. pp. 169–180. VLDB '01, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2001)
4. Alagiannis, I., Idreos, S., Ailamaki, A.: H2O: A hands-free adaptive store. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. pp. 1103–1114. SIGMOD '14, ACM, New York, NY, USA (2014)
5. Chakravarthy, S., Muthuraj, J., Varadarajan, R., Navathe, S.B.: An objective function for vertically partitioning relations in distributed databases and its analysis. Distributed and Parallel Databases 2, 183–207 (1994)
6. Hoffer, J.A., Severance, D.G.: The use of cluster analysis in physical data base design. In: Proceedings of the 1st International Conference on Very Large Data Bases. pp. 69–86. VLDB '75, ACM, New York, NY, USA (1975)
7. Jindal, A., Dittrich, J.: Relax and let the database do the partitioning online. In: Castellanos, M., Dayal, U., Lehner, W. (eds.) Enabling Real-Time Business Intelligence, Lecture Notes in Business Information Processing, vol. 126, pp. 65–80. Springer Berlin Heidelberg (2012)
8. Navathe, S., Ceri, S., Wiederhold, G., Dou, J.: Vertical partitioning algorithms for database design. ACM Trans. Database Syst. 9, 680–710 (1984)
9. Papadomanolakis, S., Ailamaki, A.: AutoPart: automating schema design for large scientific databases using data partitioning. In: Scientific and Statistical Database Management, 2004. Proceedings. 16th International Conference on. pp. 383–392 (june 2004)
10. Rosch, P., Dannecker, L., Farber, F., Hackenbroich, G.: A storage advisor for hybrid-store databases. Proc. VLDB Endow. 5(12), 1748 1758 (Aug 2012)