request_url_withoutHTTP=,canonical_url_withHTTP=,canonical_url_withoutHTTP=,request_url_withoutHTTP_realspaces=. Codesnippets (Seite 1 von 5) « Tags « Blog « Bernhard Häussner
Bernhard Häussner
Tags: Artikel mit dem Tag «Codesnippets» durchstöbern

SQL Window-Functions

29.05.2014, 12:27
Ein englischsprachiger Text über Window-Functions hinter LEGO-Fenstern

Ein englischsprachiger Text über Window-Functions hinter LEGO-Fenstern

Vor kurzem bin ich über die Window-Functions gestolpert, eine eher selten verwendete Funktionalität der Abfragesprache SQL. Man kann damit die vorherigen und folgenden Zeilen einer Zeile eines Datenbank-Abfrageergebnisses mit einbeziehen und Aggregatfunktionen auf einen Teil des Ergebnisses anwenden. Da ich sie bisher nicht kannte, habe ich sogleich etwas damit herum gespielt. Dabei sind zwei beispielhafte Anwendungen entstanden. Und weil ich denke, dass viele noch nicht von den Window-Functions gehört haben, werde ich sie im folgenden vorstellen.

Was sind die Window-Functions?

Window-Functions haben einige für SQL eher ungewöhnliche Eigenschaften:

  • Sie wenden eine Aggregatfunktion an, ohne dabei Zeilen im Ergebnis zu gruppieren. Hat man z.B. SUM(foo) OVER () in der Feldliste der Abfrage, erhält man in jeder Ergebniszeile die Summe der foos aller Zeilen.
  • Sie können auf weitere Zeilen relativ zur Position der aktuellen Zeile zugreifen. So gibt etwa LEAD(foo, 3) OVER(ORDER BY id) den Wert von foo drei Zeilen nach der aktuellen Zeile bei Sortierung nach id aus.
  • Sie können Aggregatfunktionen auf Bereiche einschränken. Hat man z.B. SUM(foo) OVER (ORDER BY id) in der Feldliste der Abfrage, erhält man in jeder Ergebniszeile die Summe der foos bis zur aktuellen Zeile.
  • Für die Angabe des Bereichs nach OVER können auch Bereiche von Zeilen oder Partitionen angegeben werden.
  • Window-Functions werden von den WHERE-Bedingungen der Abfrage beeinflusst.
  • Zusätzlich zu Aggregatfunktionen gibt es noch eine Liste spezieller Window-Functions, die nur in diesem Kontext Sinn machen.

An zwei Beispielen zu typischen Anwendungsfällen aus dem Bereich Finanzen und aus dem Bereich Biologie kann die genaue Funktionsweise besser nachvollzogen werden. Wer auch experimentieren will findet hier ein Gist mit lauffähigem Beispielcode für PostgreSQL und Beispieldaten oder ein SQL-Fiddle.

Beispiel Finanzwesen: Kumulative Summe

Das erste Beispiel soll die kumulative Summe sein. In alten Sparbüchern findet sich eine Liste von Kontobewegungen und am Ende stehen zwei Spalten: Eine für den Betrag der Transaktion, also die Veränderung des Kontostandes durch diese Kontobewegung, und eine für den neuen Kontostand nach der Transaktion, also die Summer der Beträge der bisherigen Kontobewegungen. Das wiederholte Aufführen der Summe stammt noch aus vor-digitaler Zeit, um das Aufsummieren zu erleichtern. Die Summen stellen allerdings eine Redundante Information dar, da sie leicht aus den Veränderungen berechnet werden können. In SQL würde man die Transaktionstabelle also z.B. so modellieren:

CREATE TABLE transactions
  ( id         SERIAL primary key
  , account_id INT    not null references accounts(id)
  , value_date DATE   not null
  , amount     MONEY
  )
  ;

Hier steht value_date für den Buchungstag und amount für die vorzeichenbehaftete Veränderung. Die Transaktionen aller Konten werden in einer Tabelle gespeichert, daher die account_id.

Sollen beispielsweise alle Kontostände angezeigt werden, hilft eine einfache Abfrage:

   SELECT t.account_id
        , SUM(t.amount) balance
     FROM transactions  t
 GROUP BY t.account_id
        ;
 account_id | balance  
------------+----------
          1 |   €87,39
          3 | -€134,56
          2 |    €7,66

Hier ist noch nichts überraschendes, nur eine ganz normale Aggregation der Daten. Jetzt soll ein Kontoauszug erstellt werden, bei dem in der letzten Spalte die jeweils der Kontostand nach jeder Transaktion angezeigt wird:

 id | account_id | value_date |  amount  | balance  
----+------------+------------+----------+----------
  1 |          1 | 2014-04-26 |  €100,00 |  €100,00
  2 |          1 | 2014-04-28 |   -€3,96 |   €96,04
  3 |          1 | 2014-04-28 |  -€18,65 |   €77,39
  4 |          1 | 2014-04-29 |   €10,00 |   €87,39
  5 |          2 | 2014-04-26 |   €20,00 |   €20,00
  6 |          2 | 2014-04-29 |  -€12,34 |    €7,66
  8 |          3 | 2014-04-27 | -€234,56 | -€234,56
  7 |          3 | 2014-04-28 |  €100,00 | -€134,56

Die Transaktionen sind jeweils nach Konto und Valuta sortiert. Der naive Ansatz, eine solche Tabelle zu erstellen, wäre es, ein Subquery für jede Zeile auszuführen, in dem die Summe bestimmt wird:

   SELECT t.*
        , (SELECT SUM(u.amount)
             FROM transactions u
            WHERE u.account_id = t.account_id
              AND (u.value_date, u.id)
               <= (t.value_date, t.id)
             ) AS balance
     FROM transactions t
 ORDER BY t.account_id
        , t.value_date
        , t.id
        ;

Dies ist die einfachste und naheliegendste Lösung. Doch bei etwas größeren Datenmengen zeigen sich schnell Performance-Probleme. Das Subquery muss für jeden Datensatz einzeln ausgeführt werden, wo jedesmal alle Datensätze aufs neue aufsummiert werden, was zu einer O(n²)-Laufzeit führt.

Theoretisch müssten wir aber nur den aktuellen Wert von amount auf die balance der vorherigen Zeile summieren. Um das der Datenbank-Engine beizubringen, kommt eine Window-Function ins Spiel:

   SELECT t.*
        , SUM(t.amount) OVER
              ( PARTITION BY t.account_id
                    ORDER BY t.value_date
                           , t.id
               RANGE BETWEEN unbounded preceding
                         AND current row
                           )
                          AS balance
     FROM transactions  t
 ORDER BY t.account_id
        , t.value_date
        , t.id
        ;

Anstatt eines Subqueries wird nun direkt die Aggregatfunktion SUM als Window-Function verwendet. Dazu wird sie eingeschränkt. Das PARTITION übernimmt die Aufgabe von WHERE und filtert die Datensätze von anderen Konten heraus. Mit RANGE gibt man die gewünschten relativen Zeilenkoordinaten an, hier von unbounded preceding (vom Anfang) bis current row (zur aktuellen Spalte).

Mit dieser Optimierung kann auf das Subquery verzichtet werden und die Lauzeit wird akzeptabel.

Beispiel Biologie: Gleitender Mittelwert

Das zweite Beispiel kommt aus der Bioinformatik. Bei der Analyse von Proteinen betrachtet man Bereiche mit kleinerer und größerer Hydophobizität. Dazu werden die einzelnen Aminosäuren der Kette einem Hydophobizitätswert zugeordnet. Betrachtet man nun die Reihe dieser Werte je in Isolation ergibt sich ein starkes Rauschen. Daher bildet man für jede Position mit den umgebenden Positionen den Mittelwert, ein guter Anwendungsfall für eine Window-Function.

Ich habe hier kurzerhand die Analyse vom Aquaporin-4 Isoform A, die ich schon vorher in R implementiert hatte, neu in SQL implementiert. Natürlich wird es in der Praxis meistens einfacher sein, einfach in R die entsprechenden Daten zu analysieren, gerade weil Plots auch viel leichter erstellt werden können. Für die Eingabedaten habe ich diese zwei Tabellen verwendet:

CREATE TABLE amino_acids
  ( letter         CHAR  primary key
  , name           VARCHAR(40) not null
  , hydrophobicity REAL
  )
  ;
 
CREATE TABLE aqp4
  ( id         SERIAL primary key
  , nucleotide CHAR   not null references amino_acids(letter)
  )
  ;

Die Tabelle amino_acids enthält die Hydophobizitätswerte der einzelnen Aminosäuren nach der Kyte and Doolittle scale, aqp4 die Abfolge der Aminosäuren im Aquaporin. Nun sollen jeweils mittels einer Window-Function die gleitenden Mittelwerte berechnet werden.

   SELECT amino_acids.*
        , AVG(hydrophobicity)
     OVER (ROWS BETWEEN 5 preceding AND 5 following)
     FROM aqp4
LEFT JOIN amino_acids
       ON amino_acids.letter = aqp4.nucleotide

Da nur ein Protein in der Tabelle gespeichert ist, wird dieses Mal keine Partitionierung benötigt. Interessant ist die Einschränkung der Zeilen mit den Zahlenangaben: Mit OVER (ROWS BETWEEN 5 preceding AND 5 following) werden die fünf vorhergehenden und die fünf nachfolgenden Zeilen in die AVG-Funktion einbezogen.

Mit dem SQL-Code erhält man tatsächlich die selben Werte wie mit der Referenzimplementierung in R:

 letter |     name     | hydrophobicity |         avg          
--------+--------------+----------------+----------------------
 M      | Methionin    |            1.9 |    -1.53333334128062
 S      | Serin        |           -0.8 |    -1.05714287076678
 D      | Aspartat     |           -3.5 |    -1.48750001192093
 -- [...]

Durch die Verwendung einer Window-Function konnte die Einschränkung der Mittelwert-Funktion auf die umliegenden Zeilen sehr elegant ausgedrückt werden.

Zusammenfassung

Die Window-Functions erweitern den Einsatzbereich von SQL-Analysen erheblich um Berechnungen, die sonst so einfach nicht programmiert werden könnten. Wer die genaue Dokumentation nachlesen will, wird beim PostgreSQL-Tutorial zu Window-Functions fündig, im letzen Abschnitt dort finden sich auch die Links zu den entsprechenden Kapiteln im Handbuch. Auf die Window-Functions gekommen bin ich durch einen jOOQ-Artikel zum Thema „Calculate Running Totals“, in diesem Blog finden sich auch Texte zu anderen eher exotischen SQL-Funktionalitäten. Außerdem finden sich hier die Folien zum Vortrag über Window-Functions, den ich am 6. Juni 2014 bei den Sophisticates gehalten habe.

Kommentare: keine

Über Pythons kurze Listennotation

03.07.2011, 20:34
Python-Code mit Listennotation

Python-Code mit Listennotation

Als ich mir Python (3.2) anschaute, musste ich mich zunächst an das Fehlen traditioneller for-Schleifen gewöhnen, doch inzwischen finde ich großen Gefallen an den Iterationsmethoden von Python und an der Listennotation (List Comprehensions).

Zunächst ein einfaches Programm mir dieser Listenverarbeitungssyntax. Folgendes Python-Stück erstellt eine Liste mit den ersten 5 Quadratzahlen von ungeraden Zahlen:

>>> [i**2 for i in range(10) if i%2==1]
[1, 9, 25, 49, 81]

Jetzt ein Beispiel aus der Python-Dokumentation, wie man zwei Vektoren multiplizieren kann:

>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]

Wobei ich anhand dieses Codefetzens zeigen will, dass sich Dinge auf vielerlei Arten und mitunter einfacher machen lassen. Man kann unter Verwendung von zip() über zwei Listen gleichzeitig iterieren: (mit enumerate() ließe sich auch noch über den Index iterieren)

>>> [e1*e2 for e1,e2 in zip(vec1,vec2)]
[8, 12, -54]

An den nächsten Codezeilen sehen wir erstmals, wie schön in Python ähnliche Datentypen die gleichen Operatoren verwenden: Der Intervall-Itarator, welcher von range() zurückgegeben wird, kann als Sequenztyp wie eine Liste zerstückelt werden:

>>> a=5
>>> [i for i in range(200-a*2,200,2)]
[190, 192, 194, 196, 198]
>>> [i*2 for i in range(100)[-a:]]
[190, 192, 194, 196, 198]

Sehr praktisch sind auch die Aggeregatfunktionen all(), any(), max(), min(), sum(), len() da sich mit ihnen viel Boilerplate-Code vermeiden lässt, der so ähnlich aussieht wie dieser:

>>> testlist=[1,8,9]
>>> test=False
>>> for x in testlist:
...     if(x>4):
...         test=True
...         break
...
>>> test
True

Nach dramatischer Verkürzung:

>>> any(x>1 for x in testlist)
True

Interessanterweise bleibt der Effekt von break erhalten. Das kann man prüfen, indem man mit yield-Syntax ein eigenes, iterierbares Objekt erstellt, welches beim iteriert-werden Statusmeldungen ausgibt. Hier wird die 9 nicht mehr getestet:

>>> def worker(l):
...     for i in l:
...         print("Proccessing %02d" % i)
...         yield i>4
...
>>> w2=worker(testlist)
>>> any(w2)
Proccessing 01
Proccessing 08
True

PS: In Haskell (von welchem Python seine Listennotation hat) kann man den selben Effekt noch schöner an unendlichen Listen sehen: any (> 5) [0..] ergibt True.

Man kann die Aggregatfunktionen auch auf Strings anwenden, da auch diese iterierbar sind:

>>> any(""),any("ha")
(False, True)
>>> max("Panzer")
'z'

Für eine Suchfunktion (theoretische Informatik...) brauchte ich eine Methode herauszufinden, wie lange das längste Präfix eines Strings ist, welches ein Suffix eben jenes Strings und eines weiteren Buchstaben ist. Was ich zunächst hier mit traditionellen Methoden als 10-zeilige Funktion geschrieben, habe ich dann hier als eine Listenverarbeitung schreiben können:

>>> v="abcabd"
>>> i=5
>>> b="c"
>>> max([0]+[k for k in range(0,i+2) if (v[:i]+b)[-k:]==v[:k]])
3

Oder ich habe gemessen, dass die Diagonale in einem Rechteck 29,4° geneigt ist, aber wie war das Seitenverhältnis? Da sorted() eine lexikographische Ordnung herstellt, kann man mehrere Tupel sortieren, wobei der erste Eintrag das Sortierkriterium ist und die weiteren die Ausgangsdaten. Dann baut man noch eine zweite Listennotaton außen herum zum Formatieren. Hiermit findet man also heraus, dass es wohl 16:9 war:

>>> import math,fractions
>>> ", ".join(["{}:{}".format(b,a) for diff,a,b in sorted(
...     [(abs(math.atan(a/b)-((29.4/360)*2*math.pi)),a,b)
...         for a in range(20) for b in range(20)
...       if b>a>0 and fractions.gcd(a,b)==1 ]
... )[:3]])
'16:9, 7:4, 9:5'

Hier sieht man schon ein Problem der Listennotation: Sie wird schnell unübersichtlich, da dutzende Befehle in einem Ausdruck stehen, und man auch eher von hinten nach vorne lesen muss.

Da man mit dem +-Operator Listen konkatenieren kann, kann auch die sum()-Funktion beliebig viele Listen aus einer Liste konkatenieren. Hiermit werden je 3 Zahlen startend bei 0,9 und 18 in eine Liste geschrieben:

>>> sum([range(i,i+3) for i in range(0,27,9)],[])
[0, 1, 2, 9, 10, 11, 18, 19, 20]

Das einzige, was man hier tun muss, ist sum() eine leere Liste als zweites Argument zu übergeben, da sonst die Listen zum Standartanfangswert 0 addiert werden würden (Exception). Etwas komisch ist dann leider das:

>>> sum((str(i) for i in [1,2,345,6,78]),"")
Traceback (most recent call last):
  File "", line 1, in 
TypeError: sum() can't sum strings [use ''.join(seq) instead]

Und wenn man denkt, man weiß alles über Listen, fängt man mit Mengen an:

>>> noprimes={j for i in range(2, 8) for j in range(i*2, 50, i)}
>>> set(range(2, 50))-noprimes # Primzahlen!
{2, 3, 5, 7, 41, 11, 13, 47, 17, 37, 19, 43, 23, 29, 31}
>>> {chr(i) for i in range(97,97+26)} - set( # Pangram powers!
... "The quick brown fox jumps over the lazy dog" )
set() 

Wie man sieht bilden die Iterator- und Sequenztypen ein mächtiges Instrument, wenn man Python programmiert. Wie vieles kann man sie aber auch missbrauchen.

Kommentare: keine

Einträge für die .bashrc

29.12.2010, 15:12

Die Datei ~/.bashrc enthält code, der bei jedem starten der bash ausgeführt wird. Dies wird verwendet, um aliase zu definieren oder Begrüßungsnachrichten anzuzeigen. (Wobei globale Begrüßungen in der MOTD besser aufgehoben sind. )

Über die Zeit habe ich einige Codefetzen gesammelt, die sich dort nützlich machen:


#Farbiger Promt, damit man z.B. erkennt, wo man eingeloggt ist:
PS1="\@ \[\033[0;35m\]\u@\\h\[\033[0m\]:\w> "

#kleine Spielerei
alias gn8="exit"

# Hiermit kann man die aktuelle Netzwerk-Konfiguration auslesen:
alias myip="/sbin/ifconfig"

# Prozess-Schnellsuche
alias psf='ps aux | grep -v grep | grep '

# Rechner
? () { echo "$*" | bc -l; }

# History: keine doppelten Einträge
export HISTCONTROL=ignoredups

# Keine Kommandos vergessen, außer unwichtiges
shopt -s histappend
export HISTSIZE=1000000 HISTFILESIZE=1000000
declare -x HISTIGNORE=exit:gn8

# Aktuelles Verzieichnis via HTTP (Port 8000) freigeben
alias webshare='python -c "import SimpleHTTPServer;SimpleHTTPServer.test()"'

# Manchmal muss man den Editor konfigurieren:
export EDITOR=vim

# Begrüßung:
if [ `date +%H` -lt 12 ]; then
  echo "Moin. "
else
  echo "Tach. "
fi

Die meisten Distributionen definieren schon ein paar aliase und anderes nützliches, weiteres findet sich z.B. auch im debian-Paket "bash-doc" und in diversen schier endlosen Threads im Netz. Man kann z.B. auch häufige Schreibfehler aliasen.

PS: Falls jemand noch ein paar brandheiße Tipps hat, hier gibt es eine Kommentarfunktion ;)

[Update 2011-09-01] Meine aktuelle .bashrc auf gist ist zwar auf Englisch, hat aber noch einiges mehr zu bieten.

Kommentare: keine

Fix subverison error: Valid UTF-8 data followed by invalid UTF-8 sequence

23.06.2010, 16:53

This is a solution to fix problems with SVN when you can't update your working copy for some rather odd reason. Everything you get is an obscure error message like this:

svn: Valid UTF-8 data
(hex: 65 64 69 74 65 64)
followed by invalid UTF-8 sequence
(hex: ad 6c 69 73)

This does not only appear when doing svn update but even pops up while svn status.

Since Subverion can handle binary files this is quite confusing. At luck, after some googling I found out that these errors are caused by file names with e.g. Chinese characters.

Unfortunately the error message can't display the corrupt file name because it contains non-UTF-8 data. So I figured that the „Valid UTF-8 data“ (In this case the hex sequence 0x65, 0x64, 0x69, 0x74, 0x65, 0x64) translates to the string „edited“ using some UTF-8 table.

Since there were way too many files with this string I had to look for the 0xAD 0x6C sequence. This could be the asian symbol 구, but you can't grep for this, because it is not UTF-8 encoded. However we can look for the byte sequence using some perl magic:

find /path/to/workingcopy | perl -n -e "print if /\xAD\x6C/" | less

Note the hex-regexp used here to scan binary content in file names. It outputs a nice (and in this case rather short) list like:

/path/to/workingcopy/folder/of/colleque/edited<AD>list.txt

Interestingly, less tries to expose the binary data. Now you just have to rename the file and you're good to go and able to update your working copy again.

Kommentare: 1 Einträge

Howto: Start using Subversion

31.01.2010, 14:46
Subversion

Subversion

Sometimes you want to start using Subversion code control with an existing project. This tutorial explains the steps required to create a repository and add the files of the existing project.

Start by creating a repository:

svnadmin create /dir/to/store/repo/repository-name

This will create a directory „repository-name“ containing the database of files and revisions.

Then let's add some internal directories to our repository:

svn mkdir file:///dir/to/store/repo/repository-name/trunk \
 -m "Creating repo directory structure"

Now that you have created the repo-directory that should contain all the files, import the existing project files. Start by checking out the empty repo-dir to into your project dir. This will make your project dir a working copy (that is: create a dir named „.svn“ containig some internal info) but won't change anything else.

cd /existing/poject/dir
svn checkout file:///dir/to/store/repo/repository-name/trunk .

Then go on adding (or planing to add) all the files:

svn add *

This command will list all the files that will be loaded into the repository. You can always look at the planned changes with svn st.

You probably want to exclude some files such as configuration files, runtime data. You just have to revert the add-command again:

svn revert runtimedata # exclude whole dir
svn revert config/my.ini # exclude single file

Then apply the changes to your repository (commit it):

svn commit \
-m "initial import"

And that's it. You project is added to the repository without extra files. That can be crucial if your runtime data has a huge file size. If you're paranoid or just curious check the repository for success:

svnlook tree /dir/to/store/repo/repository-name

This should show the imported directory tree. Now you can start making changes to your files and commit them as usual.

vim app.cpp
svn commit -m "typo"
svn log -r 1:HEAD #show full revision history

If you ever got stuck, you may use the built in help:

svn help #list commands
svn help commit #list options
svnlook help tree #works too

I will start using subversion for everything... soon.

Kommentare: 4 Einträge
[ Seite 1 2 3 4 5 ] Nächste Seite »
 
Χρόνογραφ
© 2008-2017 by Bernhard Häussner - Impressum - Login
Kurz-Link zur Homepage: http://1.co.de/