Projekt bazy danych do oznaczania

Jak zaprojektowałbyś bazę danych obsługującą następujące funkcje znakowania:

• elementy mogą mieć dużą liczbę tagów
• wyszukiwanie wszystkich elementów oznaczonych danym zestawem tagów musi być szybkie (elementy muszą mieć WSZYSTKIE tagi, więc jest to wyszukiwanie AND, a nie wyszukiwanie OR)
• tworzenie / pisanie elementów może być wolniejsze, aby umożliwić szybkie wyszukiwanie / czytanie

Najlepiej byłoby, gdyby wyszukiwanie wszystkich elementów oznaczonych (przynajmniej) zestawem n podanych znaczników odbywało się za pomocą jednej instrukcji SQL. Ponieważ liczba tagów do wyszukania, a także liczba tagów na dowolnym elemencie są nieznane i mogą być wysokie, używanie funkcji JOIN jest niepraktyczne.

Jakieś pomysły?

Dzięki za wszystkie dotychczasowe odpowiedzi.

Jeśli się jednak nie mylę, podane odpowiedzi pokazują, jak wyszukiwać OR na tagach. (Wybierz wszystkie elementy, które mają jeden lub więcej z n tagów). Szukam wydajnego wyszukiwania AND. (Wybierz wszystkie elementy, które mają WSZYSTKIE znaczniki n - i prawdopodobnie więcej).

O ANDINGU: Wygląda na to, że szukasz operacji „podziału relacyjnego”. Ten artykuł w zwięzły, ale zrozumiały sposób omawia podział relacji.

O wydajności: Podejście oparte na bitmapie wydaje się intuicyjnie odpowiednie do sytuacji. Jednak nie jestem przekonany, że dobrym pomysłem jest implementowanie indeksowania bitmap „ręcznie”, jak sugeruje digiguru: Brzmi to jak skomplikowana sytuacja za każdym razem, gdy dodawane są nowe tagi (?) Ale niektóre DBMS (w tym Oracle) oferują indeksy bitmap, które w jakiś sposób mogą być przydatne, ponieważ wbudowany system indeksowania eliminuje potencjalną złożoność obsługi indeksów; dodatkowo DBMS oferujący indeksy bitmapowe powinien być w stanie uwzględnić je we właściwym czasie podczas wykonywania planu zapytań.

Oto dobry artykuł na temat tagowania schematów bazy danych:

http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/

wraz z testami wydajnościowymi:

http://howto.philippkeller.com/2005/06/19/Tagsystems-performance-tests/

Zauważ, że wnioski są bardzo specyficzne dla MySQL, który (przynajmniej w 2005 roku w czasie, gdy to pisano) miał bardzo słabe właściwości indeksowania pełnego tekstu.

Nie widzę problemu z prostym rozwiązaniem: tabela dla elementów, tabela dla tagów, tabela przestawna do „tagowania”

Indeksy w tabeli krzyżowej powinny wystarczyć do optymalizacji. Wybór odpowiednich elementów byłby

SELECT * FROM items WHERE id IN  
    (SELECT DISTINCT item_id FROM item_tag WHERE  
    tag_id = tag1 OR tag_id = tag2 OR ...)  

ORAZ oznaczanie byłoby

SELECT * FROM items WHERE  
    EXISTS (SELECT 1 FROM item_tag WHERE id = item_id AND tag_id = tag1)  
    AND EXISTS (SELECT 1 FROM item_tag WHERE id = item_id AND tag_id = tag2)  
    AND ...

co wprawdzie nie jest tak wydajne w przypadku dużej liczby porównywanych tagów. Jeśli chcesz zachować liczbę tagów w pamięci, możesz utworzyć zapytanie tak, aby zaczynało się od tagów, które nie są częste, więc sekwencja AND zostanie obliczona szybciej. W zależności od spodziewanej liczby tagów do dopasowania i oczekiwań dopasowania któregokolwiek z nich, może to być OK rozwiązanie, jeśli masz dopasować 20 tagów i spodziewasz się, że jakiś losowy element będzie pasował do 15 z nich, to nadal byłoby to ciężkie w bazie danych.

Chciałem tylko podkreślić, że artykuł, do którego prowadzi @Jeff Atwood ( http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/) ), jest bardzo dokładny (omawia zalety 3 różnych schematów podejścia) i ma dobre rozwiązanie dla zapytań AND, które zwykle będą działać lepiej niż to, co zostało tu wspomniane do tej pory (tj. nie używa skorelowanego podzapytania dla każdego terminu). W komentarzach też sporo dobrych rzeczy.

ps - Podejście, o którym wszyscy tutaj mówią, jest w artykule określane jako rozwiązanie „Toxi”.

Możesz chcieć poeksperymentować z rozwiązaniem, które nie jest ściśle związane z bazą danych, takim jak implementacja Java Content Repository (np. Apache Jackrabbit ) i użyć wyszukiwarki zbudowanej na tej podstawie, takiej jak Apache Lucene .

To rozwiązanie z odpowiednimi mechanizmami buforowania prawdopodobnie zapewniłoby lepszą wydajność niż rozwiązanie stworzone samodzielnie.

Jednak nie sądzę, aby w małej lub średniej aplikacji wymagałbyś bardziej wyrafinowanej implementacji niż znormalizowana baza danych wspomniana we wcześniejszych postach.

EDYTUJ: z twoim wyjaśnieniem bardziej przekonujące wydaje się użycie rozwiązania podobnego do JCR z wyszukiwarką. To znacznie uprościłoby twoje programy na dłuższą metę.

Najłatwiejszą metodą jest utworzenie tabeli tagów .
Target_Type- w przypadku oznaczania wielu tabel
Target- Klucz do oznaczanego rekordu
Tag- Tekst znacznika

Zapytanie o dane mogłoby wyglądać następująco:

Select distinct target from tags   
where tag in ([your list of tags to search for here])  
and target_type = [the table you're searching]

AKTUALIZACJA
W oparciu o twoje wymaganie ORAZ warunki, powyższe zapytanie zmieniłoby się w coś takiego

select target
from (
  select target, count(*) cnt 
  from tags   
  where tag in ([your list of tags to search for here])
    and target_type = [the table you're searching]
)
where cnt = [number of tags being searched]

Poparłbym sugestię @Zizzencs, że możesz chcieć czegoś, co nie jest całkowicie (R) skoncentrowane na DB

W jakiś sposób uważam, że używanie zwykłych pól nvarchar do przechowywania tych tagów z odpowiednim buforowaniem / indeksowaniem może przynieść szybsze wyniki. Ale to tylko ja.

Wdrożyłem systemy tagowania wykorzystujące 3 tabele do reprezentowania relacji wiele-do-wielu (Tagi elementów ItemTags), ale przypuszczam, że będziesz mieć do czynienia z tagami w wielu miejscach, mogę powiedzieć, że przy 3 tabelach trzeba być jednocześnie manipulowanym / odpytywanym przez cały czas z pewnością uczyni twój kod bardziej złożonym.

Możesz rozważyć, czy dodatkowa złożoność jest tego warta.

Nie będziesz w stanie uniknąć złączeń i nadal będziesz w pewnym stopniu znormalizowany.

Moje podejście polega na stworzeniu tablicy tagów.

 TagId (PK)| TagName (Indexed)

Następnie masz kolumnę TagXREFID w tabeli elementów.

Ta kolumna TagXREFID jest FK do trzeciej tabeli, nazwę ją TagXREF:

 TagXrefID | ItemID | TagId

Tak więc, aby uzyskać wszystkie tagi dla elementu, wyglądałoby to następująco:

SELECT Tags.TagId,Tags.TagName 
     FROM Tags,TagXref 
     WHERE TagXref.TagId = Tags.TagId 
         AND TagXref.ItemID = @ItemID

Aby uzyskać wszystkie elementy do tagu, użyłbym czegoś takiego:

SELECT * FROM Items, TagXref
     WHERE TagXref.TagId IN 
          ( SELECT Tags.TagId FROM Tags
                WHERE Tags.TagName = @TagName; )
     AND Items.ItemId = TagXref.ItemId;

Aby ORAZ kilka tagów razem, możesz nieznacznie zmodyfikować powyższą instrukcję, aby dodać AND Tags.TagName = @ TagName1 AND Tags.TagName = @ TagName2 itd ... i dynamicznie zbudować zapytanie.

Lubię mieć kilka tabel, które reprezentują surowe dane, więc w tym przypadku masz

Items (ID pk, Name, <properties>)
Tags (ID pk, Name)
TagItems (TagID fk, ItemID fk)

Działa to szybko w czasie zapisu i utrzymuje wszystko w normie, ale możesz również zauważyć, że dla każdego tagu będziesz musiał dwukrotnie łączyć tabele dla każdego kolejnego tagu, który chcesz ORAZ, więc jest czytany powoli.

Rozwiązaniem usprawniającym odczyt jest utworzenie tabeli buforowania na polecenie poprzez skonfigurowanie procedury składowanej, która zasadniczo tworzy nową tabelę reprezentującą dane w spłaszczonym formacie ...

CachedTagItems(ID, Name, <properties>, tag1, tag2, ... tagN)

Następnie możesz rozważyć, jak często tabela Tagged Item musi być aktualizowana, jeśli znajduje się przy każdym wstawianiu, a następnie wywołać procedurę składowaną w zdarzeniu wstawiania kursora. Jeśli jest to zadanie godzinowe, skonfiguruj zadanie godzinowe, aby je uruchamiać.

Teraz, aby uzyskać naprawdę sprytne pobieranie danych, będziesz chciał utworzyć procedurę składowaną do pobierania danych z tagów. Zamiast używać zagnieżdżonych zapytań w ogromnej instrukcji case, chcesz przekazać pojedynczy parametr zawierający listę tagów, które chcesz wybrać z bazy danych, i zwrócić zestaw rekordów Items. Najlepiej byłoby to w formacie binarnym, używając operatorów bitowych.

W formacie binarnym łatwo to wyjaśnić. Powiedzmy, że do elementu przypisane są cztery tagi, możemy to przedstawić binarnie

0000

Jeśli wszystkie cztery tagi są przypisane do obiektu, obiekt wyglądałby tak ...

1111

Gdyby tylko pierwsze dwa ...

1100

Wtedy wystarczy znaleźć wartości binarne z zerami i jedynkami w żądanej kolumnie. Używając operatorów bitowych programu SQL Server, możesz sprawdzić, czy w pierwszej z kolumn znajduje się 1, używając bardzo prostych zapytań.

Sprawdź ten link, aby dowiedzieć się więcej .

Parafrazując to, co powiedzieli inni: trik nie znajduje się w schemacie , ale w zapytaniu .

Naiwny schemat Encji / Etykiet / Znaczników jest właściwą drogą. Ale jak widać, nie jest od razu jasne, jak wykonać zapytanie ORAZ z wieloma tagami.

Najlepszy sposób optymalizacji tego zapytania będzie zależał od platformy, więc zalecałbym ponowne otagowanie pytania w RDBS i zmianę tytułu na coś w rodzaju „Optymalny sposób wykonywania zapytania ORAZ w bazie danych tagowania”.

Mam kilka sugestii dotyczących MS SQL, ale powstrzymam się, jeśli nie jest to platforma, której używasz.

Odmianą powyższej odpowiedzi jest pobranie identyfikatorów tagów, posortowanie ich, połączenie jako ciąg znaków oddzielonych znakiem ^ i haszowanie. Następnie po prostu skojarz hash z elementem. Każda kombinacja znaczników tworzy nowy klucz. Aby przeprowadzić wyszukiwanie AND, po prostu ponownie utwórz hash z podanymi identyfikatorami tagów i wyszukaj. Zmiana tagów na elemencie spowoduje ponowne utworzenie skrótu. Elementy z tym samym zestawem tagów mają ten sam klucz skrótu.

Jeśli masz typ tablicy, możesz wstępnie zagregować potrzebne dane. Zobacz tę odpowiedź w osobnym wątku:

jaka jest użyteczność typu tablicowego?