Hierarchiczny indeks bitmapowy wspierający wykonywanie zapytań w bazach danych z atrybutami zawierającymi zbiory

• Autorzy: Andrzejewski W. , Królikowski Z. , Morzy M. , Morzy T.

Warianty tytułu

EN

Hierarchical bit ma p index for querying databases with set-valued attributes

• Języki publikacji: PL

Abstrakty

PL

Atrybuty zawierające zbiory są naturalnym i wygodnym sposobem modelowania złożonych obiektów świata rzeczywistego. Współczesne relacyjno-obiektowe systemy baz danych umożliwiają przechowywanie zbiorów w postaci pojedynczych atrybutów oraz wspierają w określonym zakresie wydawanie zapytań dotyczących takich atrybutów. Efektywne wykonywanie zapytań w systemie bazy danych jest możliwe między innymi dzięki indeksom, które wydatnie przyspieszają dostęp do danych. W pierwszej części niniejszej pracy przedstawiono przegląd aktualnie dostępnych technik indeksowania zbiorów. W kolejnej części, przedstawiono propozycję nowego indeksu dla baz danych przechowujących zbiory, tj. hierarchicznego indeksu bitmapowego, wspierającego wykonywanie zapytań o nadzbiory, podzbiory, zbiory identyczne, zbiory podobne, jak również uogólnione wersje tych zapytań.

EN

Set attributes are a natural and convenient means for modelling complex objects of the real world. Modern object-relational database systems enable us to store sets as single attributes and provide a limited support for queries on such attributes. Effective execution of queries in database systems is possible due to index structures, which considerably speed up data access In the first part of this paper we make a short revision of already existing set indexing techniques. In the second part we introduce a novel index for set attributes called Hierarchical Bitmap Index, which supports subset, superset, equality and similarity queries, as well as generalized versions of these queries.

Słowa kluczowe

PL

indeksowanie zbiorów; indeks bitmapowy; eksploracja danych

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Archiwum Informatyki Teoretycznej i Stosowanej
• Rocznik: 2005
• Tom: T. 17, z. 3
• Strony: 213--228
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Andrzejewski W.

• Politechnika Poznańska, Instytut Informatyki 60-965 Poznań, ul. Piotrowo 3a, Polska

autor

Królikowski Z.

• Politechnika Poznańska, Instytut Informatyki 60-965 Poznań, ul. Piotrowo 3a, Polska

autor

Morzy M.

• Politechnika Poznańska, Instytut Informatyki 60-965 Poznań, ul. Piotrowo 3a, Polska

autor

Morzy T.

• Politechnika Poznańska, Instytut Informatyki 60-965 Poznań, ul. Piotrowo 3a, Polska

Bibliografia

• [1]Agrawal R . Imielinski T. Swami A.N.. Mining association rules between sets of items in large databases. Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. 1993 Washington DC. str. 207-216.
• [2]Aerawal R.. Srikant R.. Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases. (VLDB). 1994 Santiago de Chile. Chile. Morgan Kaufmann, str. 487-499.
• [3]Araujo M.D.. Navarro G. Ziviani N.. Large text searching allowing errors. Proceedings of the 4th South American Workshop on String Processing. 1997 Carleton. University Press. Valparaiso. Chile, str. 2-20.
• [4]Deppisch U.. S-Tree: A Dynamic Balanced Signature Index for Office Retrieval. Proceedings of the ACM Conference on Research and Development in Information Retrieval. 1986. str. 77-87.
• [5]Falouisos Ch.. Christodoulakis S.. Signature Files: An Access Method for Documents and Its Analitical Performance Evaluation. ACM Transactions on Office Information Systems (TOOIS). 19S4. str. 267-288.
• [6]Fayyad U.M.. Piatetsky-Shapiro G.. Smyth P.. Uthurusams R.. Advances in Knowledge Discovery and Data Mining. 1996 AAAI/MIT Press.
• [7]Graefe G.. Cole R.L.. Fast algorithms for universal quantification in large databases. ACM Transactions on Database Systems, t. 20 nr 2. 1995, str. 187-236.
• [8] Hellerstein J.M.. Pfeffer A . The RD tree: An index structure for sets. Technical Report 1252. 1994 University of Wisconsin at Madison.
• [9]Helmer S.. Moerkotte G.. ,A study of four index structures for set-valued attributes of low cardinality. Technical Report 2/99. 1999 Universität Mannheim.
• [10]Imielinski I. Mannila H.. A database perspective on knowledge discovery. Communications of CM. t. 39 nr 11. 1996. str. 58-64.
• [11]Ishikawa Y.. Kitagawa H.N. Ohbo N.. Evaluation of signature files as set access facilities in oodbs. Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. 1993 Washington D.C.. ACM Press, str. 247-256.
• [12]M. Morzy M.. T. Morzy T.. Manolopoulos Y.. Nanopoulos A.. Hierarchical Bitmap Index: an Efficient and Scalable Indexing Technique for Set-valued Attributes. Proceedings of the 7th Fast- European Conference on Advances in Databases and Information Systems ADBIS'2003. Dresden. Germany. Springer Verlag, str. 236-252.
• [13]Morzy T.. Zakrzewicz M.. Croup bitmap index: ,A structure for association rules retrieval. Proceedings of the 4th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 1998 New York. ACM Press, str. 284-288.Gottlieb D.. Orszag S.A.. Numerical Analisis of Spectral Method. SIAM. Philadelphia 1977