Projekt bazy danych do oznaczania

171

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).

Christian Berg
źródło

Odpowiedzi:

22

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ń.

Troels Arvin
źródło
4
Muszę powiedzieć, że odpowiedź jest trochę krótkowzroczna, ponieważ użycie typu pola bitowego w bazie danych ogranicza cię do określonej liczby bitów. Nie oznacza to, że każdy element jest ograniczony do określonej liczby tagów, ale że w całym systemie może istnieć tylko określona liczba unikalnych tagów (zwykle do 32 lub 64).
Mark Renouf
1
Zakładając implementację 3nf (Question, Tag, Question_has_Tag) i indeks bitmapy w Tag_id w Question_has_Tag, indeks bitmapy musi zostać odbudowany za każdym razem, gdy do pytania dodano lub usunięto tag. Zapytanie takie jak select * from question q inner join question_has_tag qt where tag_id in (select tag_id from tags where (what we want) minus select tag_id from tags where (what we don't)powinno być w porządku i skalowane w poziomie, zakładając, że w środkowej tabeli istnieją odpowiednie indeksy b-drzewa
Adam Musch,
Link „Ten artykuł” jest nieaktywny. Chciałbym to przeczytać :(
mpen
3
Mark: Ten wygląda dobrze: simple-talk.com/sql/t-sql-programming/… To prawdopodobnie ponownie opublikowana wersja tego, o którym wspomniałem.
Troels Arvin
adres URL artykułu jest już nieaktualny
Sebastien H.
77

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.

Jeff Atwood
źródło
1
Chciałbym również uzyskać bardziej szczegółowe informacje techniczne o tym, jak zaimplementowałeś system tagowania w SO? Myślę, że w podcastie, który powiedziałeś, że trzymasz wszystkie tagi w kolumnie z każdym pytaniem, a następnie serializujesz / deserializujesz je w locie? Chciałbym dowiedzieć się więcej na ten temat i być może zobaczyć fragmenty kodu. Rozejrzałem się i znalazłem jakieś szczegóły, czy jest link, gdzie już to zrobiłeś, zanim zadam pytanie na META?
Marston A.
5
To pytanie w Meta zawiera trochę informacji o schemacie SO: meta.stackexchange.com/questions/1863/so-database-schema
Barrett
Oryginalne linki były martwe, ale myślę, że znalazłem ich nową lokalizację. Możesz chcieć sprawdzić, czy były to artykuły, do których się odnosisz.
Brad Larson
12
Pomimo tego, że został napisany przez @Jeff, nadal jest to w zasadzie tylko odpowiedź na link.
curiousdannii
13

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.

Slartibartfast
źródło
13

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”.

Winston Fassett
źródło
3
Pamiętam, że czytałem ten świetny artykuł, ale niestety link jest teraz martwy. :( Czy ktoś wie o jego lustrze?
localhost
5
link był martwy: <
Aaron,
6

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ę.

Zizzencs
źródło
5

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]
Brad Bruce
źródło
1

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.

chakrit
źródło
0

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.

FlySwat
źródło
0

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 .

digiguru
źródło
0

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.

Portman
źródło
6
Prawdopodobnie nie powinieneś powstrzymywać się od podawania ciekawostek na temat określonej technologii, ponieważ inne osoby próbujące pracować w tej problematycznej domenie mogą faktycznie korzystać z tej technologii i odniosłyby korzyści.
Bryan Rehbein,
0

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.

nitinahuja
źródło
4
Dzięki takiemu podejściu możesz wyszukiwać tylko wpisy z dokładnie tym samym zestawem tagów - to zawsze trywialne. W moim pierwotnym pytaniu chcę znaleźć wpisy, które mają wszystkie tagi, o które pytam, a być może więcej.
Christian Berg