Top-N-Anfrage

Eine Top-N-Anfrage ist eine Anfrage an ein Informationssystem, die kein vollständiges Ergebnis, sondern nur die N besten (Top-N) oder N ersten (First-N) Ergebnisse liefert. First-N-Anfragen eignen sich beispielsweise zum Browsen in größeren Informationsbeständen, um sich einen Überblick über die Art und Weise der Datensätze zu verschaffen. Eine klassische Anwendung von First-N-Anfragen sind Anfragen an eine Suchmaschine.

First-N-Anfragen

Die Beschränkung der Anfrage auf eine begrenzte Anzahl von Ergebnissen ermöglicht eine Optimierung. Dazu muss das Informationssystem jedoch eine Art von STOP-Operator unterstützen. Bei der Anfragebearbeitung sollte dieser Operator möglichst früh angewandt werden, um unnötigen Datentransfer und Verarbeitungszeit zu vermeiden.

Eine effektive Implementierung eines solchen Operators ist nur in Datenbanken möglich, wo für die in einer Anfragesprache (beispielsweise SQL) formulierten Anfragen interne Anfragepläne erstellt und optimiert werden. Der STOP-Operator enthält im Plan die gewünschte maximale Anzahl N von Datensätzen (Scan-Stop) und zusätzlich gegebenenfalls eine Sortierrichtung der Datensätze (Sort-Stop).

Falls keine Sortierung notwendig ist oder die Datensätze bereits richtig sortiert vorliegen, kann die Verarbeitung nach N Datensätzen abgebrochen werden. Ansonsten liest der Stop-Operator alle Datensätze ein und leitet mit Hilfe einer Vorrangwarteschlange die besten N weiter.

Bei der Platzierung des STOP-Operators im Anfrageplan gibt es verschiedene Strategien. Mit einer konservativen Strategie wird er möglichst früh aber doch so platziert, dass keine Daten, die später eventuell gebraucht werden, abgefangen werden. Eine aggressive Strategie ermöglicht durch eine frühere Platzierung im Anfrageplan stärkere Optimierung. Allerdings sollte die Zahl N groß genug gewählt werden und ein geeigneter RESTART-Operator hinzugefügt werden, um die Anfrage fortzusetzen, wenn nicht genügend Ergebnisse geliefert werden.

Top-N-Anfragen

Zur Ermittlung der besten N Ergebnisse ist eine Form des Rankings notwendig, bei der alle Ergebnisse anhand eines Bewertungskriteriums sortiert werden. Das wesentliche Problem ist in der Regel die Bestimmung des Bewertungskriteriums, mit dem sich einzelne Datensätze vergleichen lassen.

Top-N-Anfragen mit unscharfen Attributen

Wenn in einer Suche Attribute (Eigenschaften) der zu suchenden Objekte unscharf angegeben werden (beispielsweise "Suche ein rundes, rotes Objekt"), besteht die Antwort aus einer unscharfen Menge (siehe Fuzzylogik) von Objekten, denen jeweils eine Bewertung zwischen 0 und 1 zugewiesen ist. So lassen sich zum Beispiel die Attribute von Multimedialen Objekten nicht immer exakt angeben.

Bei mehreren unscharfen Attributen wird entsprechend eine Fuzzy-Logik-Norm der Durchschnitt gebildet, um eine Gesamtbewertung zu bekommen. Ronald Fagin hat einen Algorithmus für solche Anfragen vorgeschlagen, der ein optimales Ergebnis liefert, ohne dass alle Attribute aller Objekte direkt betrachtet werden müssen. Dabei wird davon ausgegangen, dass bei Bedarf direkt auf einzelne Attribute zugegriffen werden kann (random access) und für jedes Attribut eine Sortierung der Objekte vorliegt (sorted access). Der Algorithmus arbeitet in drei Phasen:

  1. Sorted Access: Sukzessiv werden die besten Objekte entsprechend den Ranglisten der einzelnen Attribute abgefragt, also erst das beste Objekt jedes einzelnen Attributs, dann das zweitbeste etc. Der Vorgang wird fortgesetzt, bis N Objekte in allen Listen aufgetaucht sind oder keine Objekte mehr vorhanden sind.
  2. Random Access: Nach der ersten Phase sind N Objekte mit ihren vollständigen Attributen und weitere Objekte mit einigen Attributen bekannt. Für letztere werden die noch fehlenden Attribute durch direkten Zugriff vervollständigt.
  3. Berechnung und Sortierung: Da nun alle Attribute der in der ersten Phase ermittelten Objekte bekannt sind, kann die Gesamtbewertung berechnet werden, nach der die Objekte sortiert werden. Die ersten N Objekte dieser Sortierung sind das Ergebnis der Anfrage.

Siehe auch

Literatur

  • Ronald Fagin: Fuzzy Queries in Multimedia Database Systems. Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 1998
  • Michael J. Carey, Donald Kossmann:, On Saying "Enough Already" in SQL. In: Proceedings of the ACM SIGMOD Conference on Management of Data. 1997