Eine Anfrage an ein Datenbanksystem spezifiziert für die Attribute von Objekten Qualifikationsbedingungen. Werden diese Bedingungen erfüllt, so wird das entsprechende Objekt in die Ergebnismenge aufgenommen. Bei einer Top-k-Anfrage werden Attribute mit Hilfe einer Bewertungsfunktion zu einem skalaren Wert zusammengefasst. Die Ergebnissemenge wird im Anschluss aufsteigend, oder absteigend sortiert, um dann die gemäß der Anfragebedingung besten Objekte auszugeben.
Um Top-k-Anfragen effizient beantworten zu können, sollte vermieden werden, dass die gesamte Objektmenge durchsucht und jeder Rang berechnet wird. Man kann versuchen, die Objekte selbst, oder aber ihren Datenraum zu partitionieren, um so den Suchbereich zu verkleinern. Die entstandenen Partitionen lassen sich den Ebenen eines Entscheidungsbaumes zuordnen, mit dessen Hilfe die Ergebnismenge bestimmt werden kann.
Eine bekannte Methode effizienter Verarbeitungsstrategien auf der Basis von Entscheidungsbäumen ist das Branch-and-Bound-Prinzip. Damit es funktioniert, sind Schranken für jede Partition anzugeben, um eine begrenzende Suche zu ermöglichen. Das zugehörige Verfahren im Kontext von Top-k-Anfragen wird Branch-and-Bound Ranked Search, kurz BRS genannt.
Die verwendete Bewertungsfunktion ist unabhängig von ihrer praktischen Relevanz nur dann für das BRS-Verfahren geeignet, wenn erstens für das Bild jeder Partition unter der Funktion Schranken existieren, die sich dann zweitens auch effizient berechnen lassen. Die Bestimmung solcher Schranken spezieller Funktionsklassen bildet den Kern der vorliegenden Arbeit. Es wird untersucht, welche Funktionen die oben genannten beiden Bedingungen erfüllen und es wird gezeigt, wie sich die Schranken explizit berechnen lassen. Die angeführten Beispiele machen deutlich, warum diese Funktionen für die Praxis so bedeutsam sind. Neben dem Problem der Maximierung einer Bewertungsfunktion wird auch ihre Minimierung, also die Suche nach den kleinsten Objekten im Fokus stehen. Beide vorgestellten Funktionsklassen sind geeignete Kandidaten für das Branch-and-Bound-Prinzip.