Damit die Suche im Web schnel­ler wird: Bay­reu­ther Infor­ma­ti­ker erhö­hen die Effi­zi­enz von SPARQL

Die Abfra­ge­spra­che SPAR­QL, die heu­te bei vie­len Recher­chen im Web zum Ein­satz kommt, hat Schwach­stel­len, die den Umgang mit gro­ßen Daten­men­gen ver­lang­sa­men und eine schnel­le, ziel­ge­naue Suche behin­dern. Dies haben Infor­ma­ti­ker der Uni­ver­si­tät Bay­reuth auf­grund von theo­re­ti­schen Ana­ly­sen und empi­ri­schen Tests nach­wei­sen kön­nen. Dem World Wide Web Con­sor­ti­um (W3C), das SPAR­QL im Jahr 2008 als Abfra­ge­spra­che emp­foh­len hat, haben sie kürz­lich eine Pro­blem­lö­sung vorgeschlagen.

Die mei­sten Inter­net-Nut­zer erle­ben das World Wide Web als uner­schöpf­li­che Fund­gru­be für Infor­ma­tio­nen und Unter­hal­tung. Was aber dabei nur weni­gen bewusst ist: Hin­ter allen Tex­ten, Bil­dern und Musik­stücken steht ein hoch­kom­ple­xes System von Datei­for­ma­ten, Pro­gram­men und Abfra­ge­spra­chen. Welt­weit arbei­ten Mathe­ma­ti­ker und Infor­ma­ti­ker dar­an, die­se for­ma­len Grund­la­gen im Inter­es­se der Inter­net-Nut­zer wei­ter­zu­ent­wickeln. Zu ihnen gehö­ren auch Prof. Dr. Wim Mar­tens, Pro­fes­sor für Theo­re­ti­sche Infor­ma­tik an der Uni­ver­si­tät Bay­reuth, und sei­ne Dok­to­ran­din Dipl.-Inf. Kat­ja Lose­mann. In der noch jun­gen Abfra­ge­spra­che SPAR­QL haben sie Schwach­stel­len ent­deckt, die den Umgang mit gro­ßen Daten­men­gen ver­lang­sa­men und die schnel­le, ziel­ge­naue Suche im Inter­net behin­dern. Dem World Wide Web Con­sor­ti­um (W3C) haben sie bereits einen Vor­schlag unter­brei­tet, wie die­ses Pro­blem besei­tigt wer­den soll­te. Eine Kon­fe­renz in Arizona/​USA bot den Infor­ma­ti­kern aus Bay­reuth kürz­lich die Gele­gen­heit, ihre Ideen zur Web-Opti­mie­rung der inter­na­tio­na­len Fach­welt vorzustellen.

SPAR­QL ist seit 2008 eine vom W3C emp­foh­le­ne Abfra­ge­spra­che. Sie ermög­licht die Ver­ar­bei­tung spe­zi­el­ler Daten, die das World Wide Web bes­ser struk­tu­rie­ren: und zwar dadurch, dass sie Infor­ma­ti­ons­quel­len aller Art unter for­ma­len Aspek­ten kennt­lich machen. Dies geschieht mit­hil­fe des Resour­ce Descrip­ti­on Frame­work (RDF), eines Regel­werks, das für die for­ma­le Beschrei­bung von Infor­ma­ti­ons­quel­len die ein­zu­hal­ten­den Stan­dards defi­niert. Es ver­hält sich wie mit den Büchern in einer gro­ßen Biblio­thek. Die­se wer­den viel leich­ter auf­find­bar, wenn Infor­ma­tio­nen über Autoren, Titel und Erschei­nungs­da­tum sowie wei­te­re Schlag­wor­te auf stan­dar­di­sier­te Wei­se in einer Kar­tei erfasst wer­den. In ähn­li­cher Wei­se – nur auf einem viel höhe­ren Abstrak­ti­ons­grad – hel­fen die mit­hil­fe des RDF erzeug­ten Daten, Infor­ma­ti­ons­quel­len im World Wide Web zugäng­lich zu machen. Um die­se Daten ver­ar­bei­ten zu kön­nen, wur­de SPAR­QL ent­wickelt. Die neue Spra­che kommt heu­te bei vie­len Web-Recher­chen zum Ein­satz, ohne dass die Nut­zer etwas davon bemerken.

Prof. Dr. Wim Mar­tens und Kat­ja Lose­mann haben nun her­aus­ge­fun­den, dass SPAR­QL in man­cher Hin­sicht kon­train­tui­tiv ist. Die Spra­che ist anders kon­stru­iert, als mathe­ma­tisch geschul­te Anwen­der es erwar­ten wür­den. Zudem konn­ten sie nach­wei­sen, dass SPAR­QL teil­wei­se inef­fi­zi­ent arbei­tet. Es dau­ert in eini­gen Fäl­len unge­wöhn­lich lan­ge, um mit­tels ein­fa­cher, in SPAR­QL ver­fass­ter Pro­gram­me eine gerin­ge Anzahl von Bytes zu ver­ar­bei­ten. Und sobald es um Daten­men­gen im Tera­byte-Bereich geht, was bei gro­ßen Daten­ban­ken durch­aus üblich ist, ent­ste­hen sogar mit Hoch­lei­stungs­rech­nern extrem lan­ge War­te­zei­ten von meh­re­ren Jahren.

„Mit theo­re­ti­schen Ana­ly­sen und empi­ri­schen Tests ist uns der Beweis gelun­gen, dass die­se Inef­fi­zi­enz nicht durch eine fal­sche oder unge­schick­te Pro­gram­mie­rung zustan­de kommt“, erklärt Mar­tens. „Die Ursa­che liegt viel­mehr in der Abfra­ge­spra­che SPAR­QL selbst, genau­er gesagt: in einem Fea­ture, das erst 2010 ein­ge­führt wur­de. Das W3C hat die­ses Fea­ture bis­her nicht als Stan­dard ein­ge­führt. Und so bestand für uns die Chan­ce, mit einem Opti­mie­rungs­vor­schlag noch recht­zei­tig in die wei­te­re Ent­wick­lung ein­zu­grei­fen.“ Die Zusam­men­ar­beit mit Kat­ja Lose­mann führ­te in kur­zer Zeit zu einem Vor­schlag, der die ent­deck­ten Schwach­stel­len besei­tigt. „Wir sind opti­mi­stisch, dass das W3C auf unse­re Anre­gun­gen auf­ge­schlos­sen reagie­ren wird“, meint die Bay­reu­ther Dok­to­ran­din. „Denn der nor­ma­le Inter­net-Nut­zer, der schnel­le und prä­zi­se Ant­wor­ten auf sei­ne Such­an­fra­gen erwar­tet, wird mit hoher Wahr­schein­lich­keit davon pro­fi­tie­ren – ins­be­son­de­re dann, wenn SPAR­QL und die durch RDF defi­nier­ten Stan­dards sich im Web wei­ter durchsetzen.“

Ihren Opti­mie­rungs­vor­schlag haben die Bay­reu­ther Infor­ma­ti­ker mit Kol­le­gen an der Uni­ver­si­tät von Chi­le und der Päpst­li­chen Katho­li­schen Uni­ver­si­tät von Chi­le – bei­de in der Haupt­stadt Sant­ia­go – abge­stimmt. Dort hat­ten sich drei For­scher eben­falls inten­siv mit SPAR­QL befasst und waren dabei auf die glei­chen Pro­ble­me gesto­ßen. „Dass zwei von­ein­an­der unab­hän­gi­ge For­schungs­teams den­sel­ben Opti­mie­rungs­vor­schlag ein­brin­gen, wird die Erfolgs­aus­sich­ten beim W3C erhö­hen“, glaubt Mar­tens, der sich auch in sei­nen künf­ti­gen For­schungs­ar­bei­ten für Ver­bes­se­run­gen im World Wide Web enga­gie­ren will.

Ver­öf­fent­li­chung:

Kat­ja Lose­mann, Wim Martens:
The com­ple­xi­ty of eva­lua­ting path expres­si­ons in SPARQL,
in: PODS ’12 Pro­ce­e­dings of the 31st Sym­po­si­um on Prin­ci­ples of Data­ba­se Systems,
Asso­cia­ti­on for Com­pu­ting Machi­nery (ACM),
New York 2012, pp. 101–112
DOI: 10.1145/2213556.2213573