BlogKontaktTagcloud

WikiWay2.0

WikiWay2.0 ist da! Mit WikiWay2.0 ist es möglich die kürzeste Verbindung zwischen zwei Wikipedia-Artikeln zu finden. So ist es zum Beispiel erstmals möglich die Verbindung zwischen einem Gürteltier und Bier aufzuzeigen. Dieses interessante Wissen wahr bisher gelangweilten Informatikern (ich nenne keine Namen!), die diese Informationen in müsamer Handarbeit zusammentrugen, vorbehalten.

WikiWay2.0 ist auch ganz schön Web2.0: Da werden Scriptsprachen verwendet (PHP, Javascript), wie wild XMLHTTPRequests verschickt, Bilder "gemashupt" und natürlich ist das ganze auch noch ganz schön Beta. Leider ist Rechenleistung noch immer nicht unendlich und deshalb kann eine Anfrage manchmal ganz schön lange gehen, das Warten lohnt sich aber fast immer.

Und wer jetzt den Sinn dieser ganzen Applikation noch nicht versteht - das ist nicht so schlimm, ist schliesslich Web2.0.
Ähnliche Beiträge:
Synchroner Aufruf mit XMLHttpRequest in Firefox
Viele Daten II
Viele Daten
All new webtuesday
AJAX-Chat in PHP mit UNIX IPC
Comments (8)  Permalink

Synchroner Aufruf mit XMLHttpRequest in Firefox

Ein synchroner XMLHttp-Aufruf in JavaScript ist theoretisch nicht so schwer. Die Dokumentation ist, wohl weil synchrone Aufrufe im Vergleich zu asynchronen relativ selten benötigt werden, eher spärlich und teilweise verwirrend. Das grösste Problem ist dass das XMLHttpRequest-Objekt sind nicht in allen Browsern gleich verhält. So lässt sich der untenstehende Request im Konqueror (und wohl auch in älteren Internet Explorern und Safari) ausführen, obwohl der Aufbau eigentlich falsch ist.

//Not valide Request!
xmlHttp.open('GET', 'json.php?name='+name, false);
xmlHttp.onreadystatechange = function () {
if (xmlHttp.readyState == 4) {
var resp = eval(xmlHttp.responseText);
saveVar.c = resp['id'];
if(vonNr.c && zuNr.c){
foundIDs();
}
}
};
xmlHttp.send(null);
Diese direkte Umwandlung des asynchronen Request in eine Synchronene ist nicht zulässig und funktioniert deshalb im Firefox (und vermutlich in anderen Browser die den Mozilla-Kern verwenden) nicht. Der korrekte asynchrone Aufruf sieht wie folgt aus:

xmlHttp.open('GET', 'json.php?name='+name, false);
xmlHttp.send(null);

var resp = eval(xmlHttp.responseText);
saveVar.c = resp['id'];
if(vonNr.c && zuNr.c){
foundIDs();
}
Wobei in diesem Fall die Methode send blockierend ist und auf die Antwort vom Server wartet. Der nachfolgende Code wird erst nach dem send eine Antwort erhalten hat ausgeführt.
Ähnliche Beiträge:
Parallel Request mit AJAX und PHP
Faster google maps with JSON
Web-Continuations - Technolgie 2007
"Defekte" for-in-Schleife in JavaScript
Assoziative Array nach Value sortieren
Comments (2)  Permalink

Suchen in Graphen und Bäumen mit SQL

Kann man Graphen und Bäume mit SQL durchsuchen? Ja, man kann. Wenn auch mit einigen Einschränkungen, insbesondere muss die Suchtiefe bereits von Beginn weg festgelegt werden.


Aber erst einmal von vorne. Ein Baum (oder Graph) wird in einer Datenbank meist in einer Tabelle abgelegt die über (mindestens) zwei Felder verfügt. Zum einen währen dies ein Feld für die ID des Elternknotens und ein Feld für die ID des Kindknotens. Jeder Knoten kann nun beliebig viele Einträge in dieser Tabelle haben.

Der erste Schritt ist nun noch sehr einfach. Um alle Knoten auf Level 1 zu durchsuchen brauchen wir nicht mehr als eine einfach SQL-Abfrage.
SELECT t.parent AS "Level 0", 
t.child AS "Level 1"
FROM tree AS t
WHERE t.parent = 1
AND t.child = 10;
Wenn wir nun bis Level 2 Durchsuchen wollen müssen wir die Tabelle mit sich selbst verknüpfen. 
SELECT t1.parent AS "Level 0", 
t2.parent AS "Level 1",
t2.child AS "Level 2"
FROM tree AS t1
RIGHT OUTER JOIN tree t2
ON t1.child = t2.parent
WHERE t1.parent = 1
AND (t1.child = 10
t2.child = 10);

Das ganze kann man dann selbstverständlich nach belieben auf die Spitze treiben. Unten mit einer Suche bis zu Level 4.

SELECT t1.parent AS "Level 0", 
t2.parent AS "Level 1",
t3.parent AS "Level 2",
t4.parent AS "Level 3",
t4.child AS "Level 4"
FROM tree AS t1
RIGHT OUTER JOIN tree t2
RIGHT OUTER JOIN tree t3
RIGHT OUTER JOIN tree t4
ON t3.child = t4.parent
ON t2.child = t3.parent
ON t1.child = t2.parent
WHERE t1.parent = 1
AND (t1.child = 10
OR t2.child = 10
OR i3.child = 10
OR i4.child = 10);

Diese Suche hat natürlich einige Nachteile, so ist es beim Fund eines Knotens nicht möglich die Suche abzubrechen. Alle weiteren Knoten müssen durchsucht werde. Dies kann, wenn man nicht alle Lösungswege braucht, aus Sicht der Performance verheerend sein. Ausserdem muss die Suchtiefe vorbestimmt werden. Allerdings sollte es kein Problem darstellen die Suche dynamisch, zur Laufzweit für die entsprechende Suchtiefe zu generieren, so kann man auch eine nicht erfolgreiche Suche mit einer höheren Tiefe noch einmal laufen lassen.

Der Grosse Vorteil bei der Suche auf der Datenbank ist natürlich das man eine grössere Geschwindigkeit ereichen kann, als wenn jeder Knoten zu einem Clientprogramm transferiert werden muss.

Ähnliche Beiträge:
Denormalsieren in MySQL
Viele Daten II
Viele Daten
WikiWay2.0
Synchroner Aufruf mit XMLHttpRequest in Firefox
Comments (1)  Permalink

Denormalsieren in MySQL

Unter Denormalsieren versteht man die "bewusste Rücknahme einer Normalisierung zum Zweck der Verbesserung des Laufzeitverhaltens einer Datenbankanwendung." (Wikipedia) Hin und wieder ist es nötig Daten zu duplizieren um Abfragen schneller zu machen. Doch wie macht man das mit MySQL?

In MySQL gibt es mit dem INSERT...SELECT-Befehl ein mächtiges Werkzeug um Daten aus verschiedenen Tabellen in eine Neue einzufügen. Vor dem Einfügen können die Daten natürlich durch alle in SELECT verfügbaren Möglichkeiten manipuliert werden.

Leider ist es momentan in MySQL nicht möglich auf eine Tabelle im SELECT-Teil zuzugreifen und in die gleiche Tabelle zu schreiben. Deshalb gelingt das unten stehendes Beispiel nicht. (Nicht überprüft.)
 
INSERT INTO pagelinks (pl_to)
SELECT page.page_id
FROM page, pagelinks
WHERE page.page_namespace = pagelinks.pl_namespace
AND pagelinks.pl_title = page.page_title;
Dieses Problem kann allerdings relativ leicht umgangen werden. Man erstellte einfach eine neue Tabelle die ein Abbild jener ist die ergänzt werden soll. Der SQL-Code einer Datenbank kann mit "mysqldump -u benutzer -p datenbank -d tabelle" ausgelesen werden. Der Code muss danach angepasst werden (Tabellennamen ersetzen) und in die Datenbank eingespielt werden. Mit dem INSERT...SELECT-Befehl können danach die neue Tabelle wieder mit Daten aufgefüllt werden. Daraus ergibt sich dann in meinem Fall (mit der neuen Tabelle idlinks und da ich nicht ganz alle Daten brauche).

INSERT INTO idlinks (il_from,il_to)
SELECT pagelinks.il_from, page.page_id
FROM page, pagelinks
WHERE page.page_namespace = pagelinks.pl_namespace
AND pagelinks.pl_title = page.page_title;
Nun haben wir immer noch ein Problem. Bei vielen Daten bricht die Operation irgendwann mit der Fehlermeldung "ERROR 1206 (HY000): The total number of locks exceeds the lock table size" ab. Dies liegt daran das der InnoDB-Buffer-Pool zu klein ist. Der Puffer kann in der Datei my.cnf wie folgt angepasst werde. (Neustarten der Datenbank nicht vergessen.)

[mysqld]
# Set buffer pool size to 50-80% of your computer's memory
innodb_buffer_pool_size=70M
innodb_additional_mem_pool_size=10M

Danach sollte diese Operation auch recht zügig ablaufen. Denormalisieren von Daten in MySQL ist nicht ganz eifach, mit ein wenig "pröblen" kommt man aber, wie dieser Artikel zeigt, auf gute Resulate.

Ähnliche Beiträge:
Suchen in Graphen und Bäumen mit SQL
Viele Daten II
Viele Daten
MySQL drinks java
Why your database says paging sucks!
Comments (0)  Permalink

Viele Daten II

Nochmals was von meiner krass-viel-daten Projekt. Die Keys nachträglich zu erstellen verschnellert zwar das Einfügen massiv, das Einfügen der Keys dauert aber vermutlich dann etwa gleich lange:

mysql> show processlist;
+----+---------+-----------+---------+---------+--------+-------------------+------------------------------------------------------------------------------------------------------+
| Id | User | Host | db | Command | Time | State | Info |
+----+---------+-----------+---------+---------+--------+-------------------+------------------------------------------------------------------------------------------------------+
| 19 | xyz | localhost | xyz | Query | 340517 | copy to tmp table | ALTER TABLE `pagelinks`
ADD UNIQUE KEY `pl_from` (`pl_from`,`pl_namespace`,`pl_title`),
ADD KEY |
| 45 | root | localhost | wikiway | Query | 0 | NULL | show processlist |
+----+---------+-----------+---------+---------+--------+-------------------+------------------------------------------------------------------------------------------------------+
2 rows in set (0.06 sec)
Also noch etwa 100 Stunden um die Keys zu erstellen. Und leider dauern die Abfragen immer noch zu lange. Desshalb werde ich als nächstes Denormalisieren.
Ähnliche Beiträge:
Viele Daten
WikiWay2.0
Suchen in Graphen und Bäumen mit SQL
Denormalsieren in MySQL
Wikipedia-Suchmaschine
Comments (0)  Permalink

Viele Daten

Viele Daten sind ein Fluch, besonders wenn man nicht die Möglichkeit hat einfach einen dickeren Rechner hinzustellen. Mein Laptop rechnet sich für eine Testinstallation momentan dumm und dämlich. Tagelange Insert-Batch gehören in zwischen zum Normalfall.

Dank dem Tipp von Chregu habe ich heute mal die Key's nachräglich hinzugefügt. Das hat das einfügen einiges schneller gemacht. Das Einfügen der Schlüssel dauert dann aber auch ein Weilchen. Das sieht dann so aus:
Query OK, 1097721 rows affected (2 hours 45 min 31.85 sec)
Records: 1097721 Duplicates: 0 Warnings: 0
Mehr zu Krass-viel-Daten vieleicht irgendwann mal später hier in diesem Blog.
Ähnliche Beiträge:
Viele Daten II
WikiWay2.0
Suchen in Graphen und Bäumen mit SQL
Denormalsieren in MySQL
Wikipedia-Suchmaschine
Comments (0)  Permalink
1-6/6