Blog do projektu Open Source JavaHotel

środa, 28 kwietnia 2010

Recursive SQL and graph theory

Preface

Seems very strange but it is possible to use "recursion" in SQL statements. By recursion I mean the method of defining function (or object) which inside its definition refers to itself. To write recursive SQL statement it is necessary to follow strict rules : http://msdn.microsoft.com/en-us/library/ms186243.aspx


Example
Consider simple table containing distances between cities.
CREATE TABLE CONNECTION (CITY_FROM VARCHAR(100), CITY_TO VARCHAR(100), DISTANCE DECIMAL);

delete from connection;
insert into connection values ('Warszawa', 'Augustów', 242);
insert into connection values ('Warszawa', 'Suwałki', 267);
insert into connection values ('Warszawa', 'Olsztyn', 192);
insert into connection values ('Augustów', 'Suwałki', 32);

insert into connection values ('Warszawa', 'Płock', 103);
insert into connection values ('Płock', 'Grudziądz', 133);
insert into connection values ('Grudziądz', 'Gdańsk',106);

insert into connection values ('Warszawa', 'Mława', 116);
insert into connection values ('Mława','Elbląg', 144);
insert into connection values ('Elbląg', 'Gdańsk', 58);
Now "recursive" statement:
WITH path (city_from, city_to, distance, stops)
    AS ( SELECT  f.city_from,  f.city_to, f.distance, 0
             FROM connection f
             WHERE  city_from='Warszawa'
          UNION ALL
             SELECT p.city_from, f.city_to,   
                    p.distance+f.distance, p.stops+1
             FROM connection f, path p
             WHERE p.city_to=f.city_from )
    SELECT substr(pa.city_from,1,20), substr(pa.city_to,1,20), min(distance) FROM path pa GROUP BY (pa.city_from, pa.city_to);
How it runs ?
The beginning is the statement before UNION ALL. It selects all direct connection from Warszawa.
  • 'Warszawa', 'Augustów', 242;
  • 'Warszawa', 'Suwałki', 267;
  • 'Warszawa', 'Olsztyn', 192
  • 'Warszawa', 'Płock', 103
  • 'Warszawa', 'Mława', 116
Then runs the second part of UNION ALL command. It adds all direct connections of the destinations selected in the previous step. This time it is:
  • 'Augustów', 'Suwałki', 32
  • 'Płock', 'Grudziądz', 133
  • 'Mława','Elbląg', 144
This second part is  "recursive" - it uses 'path'  table which is created in the whole statements.
The third and next steps are repetition of the second step. The only difference is that rows taken are rows added in the previous step (not the whole path table). This time following destinations will be added.
  • 'Elbląg', 'Gdańsk', 58
  • 'Grudziądz', 'Gdańsk',106
The fourth step will bring no rows - there is no destination for 'Gdańsk'  and it ends our 'recursion'.
The final statement selects minimal distance between Warszawa and all cities found.
Warszawa             Augustów                242,
Warszawa             Elbląg                  260,
Warszawa             Gdańsk                  318,
Warszawa             Grudziądz               236,
Warszawa             Mława                   116,
Warszawa             Olsztyn                 192,
Warszawa             Płock                   103,
Warszawa             Suwałki                 267,
During evaluation also 'stops' column is created, although not used. It contains number of cities visited during journey from 'Warszawa' to destination. In the final statement, by replacing minimal(distance) with minimal(stops) we can choose paths with having minimal number of nodes.

What this 'recursion SQL' has in common with graph theory ?

Answer is simple. Connection table describes nodes of directed graph. 'Recursive' statement is an implementation of Breadth-first_search. Distance is a weigth assigned to a node and our 'recursive' statement implements the algorithm of finding the Shortest path problem Shortest_path_problem

Danger.
Unfortunately, there is also a dark side oh this moon.
Consider connection table:
insert into connection values ('Warszawa', 'Augustów', 242);
insert into connection values ('Augustów', 'Warszawa', 242);
Our 'recursive' statement will run infinitely on that table. Using terminology from graph teory our statement is invalid if there is a 'cycle' in the graph, it is valid only for graphs without cycles. What's more important - there is no simply workaround to this problem.

niedziela, 11 kwietnia 2010

Byliśmy na koncercie

Byliśmy 2 kwietnia 2010 roku na koncercie w ramach tegorocznego Wielkanocnego Festiwalu Ludwiga van Beethovena.

Requiem Hectora Berlioza skomponowane w 1837 to utwór rzadko wykonywany. Wymaga ogromnego składu (nawet do 600 głosów) chóru i orkiestry i to jest zapewne przyczyną rzadkiego pojawiania się tego dzieła w repertuarze. Koncert w Teatrze Wielkim był wyjątkową okazją posłuchania tej muzyki na żywo.

Koncert okazał się jednak rozczarowaniem. Nie potrafię powiedzieć, czy to problem samej partytury czy wykonawstwa. Głównie rozczarowały partie chóralne, zwłaszcza gdy chór śpiewa 'a capella'.  Śpiew brzmiał bardzo słabo, gdzieś się gubił w ogromnej sali Teatru Wielkiego. Czegoś tutaj zabrakło, większej werwy, lepszego przygotowania, może dyrygent (Charles Dutoit) nie potrafił narzucić swojej wizji tego dzieła ogromnemu chórowi (blisko 200 śpiewaków).

Wspaniale zabrzmiała środkowa część dzieła - Lacrymosa. Tutaj chór - śpiewający razem z orkiestrą - wyraźnie się odnalazł i dało to doskonały efekt.

Jedyna partia solowa ma miejsce w Sanctus. Dobrym zamysłem było umieszczenie solisty (Paul Groves) wśród orkiestry i gdy śpiewał "Sanctus benedictus" brzmiało to z pewnej oddali przypominając głos z nieba.

Połączone siły: sławnego dyrygenta, doskonałego solisty, podwójnego chóru Filharmonii Warszawskiej i Teatru Wielkiego, znakomitej orkiestry Sinfonia Varsovia  wzmocnionej o potężną sekcję perkusyjną poniosły jednak ewidentnie porażkę w starciu z monumentalnym dziełem Berlioza. Partytura została wykonana, ale - za wyjątkiem kilku fragmentów - nic nie odcisnęło się w pamięci.

niedziela, 28 marca 2010

Oracle - DB2 migration

Problem
Assume that for very important reason we have to keep some data as base64 encoded data. This data is very often sent as a part of pure xml file and we strongly believe that keeping this data in this format and thus avoiding converting them every time we improve efficiency of our mission critical application.

It is quite easy in Oracle PL/SQL query language to convert this data to human readable format by using utl_raw and UTL_ENCODE functions.
SELECT CUST_ID, utl_raw.CAST_TO_VARCHAR2(UTL_ENCODE.BASE64_DECODE(utl_raw.cast_to_raw(CUST_ADDRESS))) FROM TEST1.CUST_ENCODED_TABLE;

SELECT CUST_ID, utl_raw.CAST_TO_VARCHAR2(UTL_ENCODE.BASE64_DECODE(utl_raw.cast_to_raw(CUST_ADDRESS))) FROM TEST1.CUST_ENCODED_TABLE WHERE utl_raw.CAST_TO_VARCHAR2(UTL_ENCODE.BASE64_DECODE(utl_raw.cast_to_raw(CUST_ADDRESS))) LIKE '%25%';

But after migrating to DB2 there is a little surprise - there is nothing like UTL_RAW and UTL_ENCODE functions and we have a lot of data in base64 encoded format. How to resolve this issue without costly redesigning our application and converting data once again ?

Solution idea
The solution is very simple - UTFs.

Example
Assume that we have created the following table:
 CREATE TABLE TEST.CUST_ENCODED_TABLE
   (    "CUST_ID" VARCHAR2(45),
        "CUST_ADDRESS" VARCHAR2(200)
   );

CUST_ADDRESS contains customer address in base64 encoded format.

Now populate our table with sample data:

DECLARE

    i NUMBER := 1;
    CUST_ID VARCHAR(100);
    CUST_ADDRESS VARCHAR(200);
    CUST_ENCODED VARCHAR(200);
    SEQ NUMBER;

BEGIN

    LOOP
        i := i+1;
        SEQ := LTrim(TO_CHAR(i,'999'));
        CUST_ID := 'ID'||SEQ;
        CUST_ADDRESS := 'CITY'||SEQ||' '||'ZIP'||SEQ||' '||'ADDRESS'||SEQ;

        CUST_ENCODED := UTL_RAW.cast_to_varchar2(UTL_ENCODE.BASE64_ENCODE(utl_raw.cast_to_raw(CUST_ADDRESS))); 
        dbms_output.put_line(CUST_ID || ':' || CUST_ADDRESS || ':' || CUST_ENCODED);
        INSERT INTO TEST1.CUST_ENCODED_TABLE VALUES(CUST_ID,CUST_ENCODED); 

        EXIT WHEN i>100;

    END LOOP;
END;

Query examples
SELECT CUST_ID,utl_raw.CAST_TO_VARCHAR2(UTL_ENCODE.BASE64_DECODE(utl_raw.cast_to_raw(CUST_ADDRESS))) FROM TEST1.CUST_ENCODED_TABLE;

SELECT CUST_ID, utl_raw.CAST_TO_VARCHAR2(UTL_ENCODE.BASE64_DECODE(utl_raw.cast_to_raw(CUST_ADDRESS))) FROM TEST1.CUST_ENCODED_TABLE WHERE utl_raw.CAST_TO_VARCHAR2(UTL_ENCODE.BASE64_DECODE(utl_raw.cast_to_raw(CUST_ADDRESS))) LIKE '%25%';
Migrate to DB2
Now let's migrate our table to db2. You can use IBM Migration Toolkit or accomplish it any other way.

After migration run a query - data are encoded as expected.
 db2 "select * from TEST.CUST_ENCODED_TABLE"

..........
ID87 Q0lUWTg3IFpJUDg3IEFERFJFU1M4Nw==
ID88 Q0lUWTg4IFpJUDg4IEFERFJFU1M4OA==
..........

Solution - UDF
Create and compile following simple java class.
import java.io.IOException;

import sun.misc.BASE64Decoder;
import sun.misc.BASE64Encoder;
import COM.ibm.db2.app.UDF;

public class UTL_ENCODE extends COM.ibm.db2.app.UDF {
   
    public static String BASE64_ENCODE(String in) {
        BASE64Encoder encoder = new BASE64Encoder();
        return encoder.encode(in.getBytes());
    }

        public static String BASE64_DECODE (String in) throws IOException {
            BASE64Decoder decoder = new BASE64Decoder();
            byte[] b = decoder.decodeBuffer(in);
            return new String(b);
        }

}
And compile using javac provided together with DB 9.7.
 /opt/ibm/db2/V9.7/java/jdk32/bin/javac UTL_ENCODE.java

Then copy output UTL_ENCODE.class to the /home/db2inst1/sqllib/function directory.
Next step is to create SQL functions.

CREATE OR REPLACE FUNCTION UTL_ENCODE.BASE64_DECODE(VARCHAR(200))
RETURNS varchar(200) EXTERNAL NAME 'UTL_ENCODE!BASE64_DECODE'
FENCED
PARAMETER STYLE JAVA
LANGUAGE JAVA
NO EXTERNAL ACTION ;
Tip: After changing anything in the java code don't forget to run
db2 "CALL SQLJ.REFRESH_CLASSES()"
after copying .class file to functions directory. Otherwise DB2 engine will be using the old version of the function.

Don't forget to grant execute right for just created function.
db2 grant execute on FUNCTION UTL_ENCODE.BASE64_DECODE to /user/
Final
db2 "SELECT CUST_ID,UTL_ENCODE.BASE64_DECODE(CUST_ADDRESS) from TEST1.CUST_ENCODED_TABLE"

ID87   CITY87 ZIP87 ADDRESS87
ID88   CITY88 ZIP88 ADDRESS88

SELECT CUST_ID,UTL_ENCODE.BASE64_DECODE(CUST_ADDRESS) FROM TEST1.CUST_ENCODED_TABLE WHERE UTL_ENCODE.BASE64_DECODE(CUST_ADDRESS) LIKE '%25%';

CUST_ID
--------------------------------------------- -----------
ID25    CITY25 ZIP25 ADDRESS25

poniedziałek, 22 marca 2010

sanctimonious pirate

Very often developers add a lot of assertion or debug code to the program during developing phase but remove it in the production release.

Measure for Measure

LUCIO

    Thou concludest like the sanctimonious pirate that
    went to sea with the Ten Commandments, but scraped
    one out of the table.

Second Gentleman

    'Thou shalt not steal'?

LUCIO

    Ay, that he razed.

poniedziałek, 8 marca 2010

ODBC, 64 bit Linux

Question
ODBC is associated mostly with Windows platform but there exists also a Linux implementation of this API (http://www.unixodbc.org/). I was interested in answering the questions :
  • How it runs on 64 bit Linux platform.
  • Is it possible to develop multi-platform (Windows/Linux) C++ application having access to any data via ODBC driver provided.
How to answer ?

To answer that questions I had to develop a small wrapper around ODBC API. ODBC API is very complicated, I can hardly imagine any program littered with sequences: 

SQLAllocHandle - SQLSetEnvAttr - SQLConnect - SQLExecDirect - SQLFetch ....

To keep stuff as simple as possible I implemented only columns returned as string. I avoided problem with different data types and complicated C++ - SQL data types conversion. There is also nothing about  transactions, stored procedures, code pages, binding parameters etc. But I believe that this interface can be easily extended to meet more demanding requirements.

Solution, simple wrapper around C ODBC
ODBCDrivers.h
  • getODBCDrivers : retrieves list of  ODBC drivers installed.
  • getODBCDataSources : retrieves list of ODBC data sources.
  • class ODBCConnection 
  •    method open: opens connection
  •    method execute : run SQL statements
  •    method close: closes connection
 ODBCDrivers.cpp

In several places it was necessary to put statement like:

#ifdef WIN32
....
#endif
But test cases (look beneath) does not include anything like that, it is hidden behind facade (wrapper).

Test program

To test that interfaces and answer the questions set up above I created a program as a C++ unit test based on googletest framework.

The test cases are very simple:

Verify number of ODBC drivers available on the host.
testdrivers.cpp

Verify number of ODBC data sources available.
testdatasources.cpp

Main test
  1. Create table
  2. Add some tuples having columns like SYMBOL{number} and NAME{number}
  3. Run some tests and verifications.
testconnection.cpp

Execute the test
I run the test on the following platforms:

Linux 64 bit (RedHat)
  • Test program compiled as 64 bit application
  • Database: Oracle 11g
  • ODBC driver: EasySoft. I was unable to run Oracle ODBC driver.
Windows 64 bit (Windows 7)
  • Test program compiled as 64 bit application (using MS Visual Studio 2008)
  • Database: MySql 
  • ODBC driver: MySql
Windows XP (32 bit)
  • Test program compiled as 32 bit application (using MS Visual Studio 2008 Express)
  • Database: DB2
  • ODBC driver: DB2
Linux 32 bit (Ubuntu)
  • Test program compiled as 32 bit application
  • Database: Progress
  • ODBC driver: Progress
Conclusion
So the answer is positive. It runs as expected on 64 bit linux. Also it is possible to have portable C++ code accessing database via ODBC API. This example is very simple but I dare say that this conclusion can be applied also for more serious applications.

    środa, 3 marca 2010

    Legacy code

    A motto of all developers working with legacy code:

    John Keats, "Hyperion"
    “But cannot I create?  
    “Cannot I form? Cannot I fashion forth  
    “Another world, another universe,  
    “To overbear and crumble this to nought?  
    “Where is another chaos? Where?

    wtorek, 16 lutego 2010

    Byliśmy w teatrze

    Byliśmy 13 lutego w Teatrze Współczesnym  na sztuce  Antoniego Czechowa "Sztuka bez tytułu".

    Wikipedia (po rosyjsku)

    Tekst sztuki (po rosyjsku)

    Jest to pierwsza sztuka napisana przez Czechowa w 1878 roku. Nigdy nie była wystawiona za życia autora, pierwsza inscenizacja miała miejsce dopiero w 1923 roku, wiele lat po śmierci Czechowa. Ponieważ zaginęła strona tytułowa, więc sztuka znana jest pod kilkoma tytułami "Sztuka bez tytułu", "Bez ojcowizny" lub po prostu "Płatonow" od nazwiska głównego bohatera.

    Trudno określić gatunek sztuki. Czasami to komedia, czasami farsa i błazenada, czasami tragedia.

    To bezlitosny obraz rosyjskiej prowincji. Warstwy wyższe pogrążają się w nieróbstwie i rozpuście, ziemianie są głupi i chciwi, służba bezmyślna, Żyd zachłanny i podstępny. Co mają wspólnego to wszechobecne pijaństwo. Młody człowiek (Wengierowicz) z nieodłączną książką w ręku wygłasza frazesy że nic go nie łączy z tym zepsutym światem, ale rychło się okazuje, że jest jego nieodrodną częścią. Mamy nawet lokalnego zbója (Osip), którego jedyną ludzką cechą jest to, że nie są mu obojętne wdzięki niewieście. Jasną postacią wydaje się dziewczęca i naiwna żona Płatonowa, Sasza, ale widownia wybucha śmiechem, gdy nieudolnie usiłuje zrozumieć choć jedno zdanie z książki, mając nadzieję, że w ten sposób zbliży się do poziomu intelektualnego swojego męża. Czechow nie ma litości dla nikogo i nikogo nie oszczędza.

    W sztuce nie ma ani jednej postaci, który by wzbudzała szacunek. Wspominający stare dobre czasy ziemianin Głagoliew po doznaniu zawodu miłosnego ucieka do Paryża, ale to nie jest Paryż artystów, filozofów czy rewolucjonistów pragnących ruszyć z posad bryłę świata, To "Paryż" uciech i hulanek. Miejscowa piękność i znakomitość, wdowa po generale, Wojnicewowa bawi się uczuciem Głagoliewa, ale tylko dlatego, że ma nadzieję, że ten po wykupie jej zadłużonego majątku uchroni ją przed wierzycielami. Gdy ten plany legną w gruzach jakoś nie możemy z siebie wykrzesać żadnego współczucia czy zrozumienia. Wiecznie pijany pułkownik w stanie spoczynku Trylecki wykrzykuje, że gdyby jeszcze odsłużył trzy lata, to by został generałem. W sztuce wspominany jest prawdziwy generał,  ale nie z powodu wojennej chwały, ale dlatego że zostawił wdowę i syna z długami przewyższającymi wartość majątku. Wojenną przeszłość (Sewastopol) przypomina tylko stary woźny sądowy, ale wyraźnie wojenna przeszłość nie wystarcza na środki do życia i musi sobie dorabiać napiwkami za dostarczanie listów. Ziemianin Pietrin namawia swojego przyjaciela Głagoliewa do poślubienia generałowej, ale nie kieruje nim sympatia, a nadzieja, że ten po ożenku wykupi jego weksle.

    Głównym bohaterem jest tutaj Płatonow, wiejski nauczyciel. Płatonow za młodych czasów był Byronem i Hamletem, ale stał się małomiasteczkowym Don Juanem. Z dawnych planów zdobywania świata zostało zdobywanie serc prowincjonalnych piękności. Gdy dowiaduje się o rzekomej śmierci swojej żony wykrzykuje "a ja ją wskrzeszę". Coś jak Don Giovanii z opery Mozarta zuchwale rzucający wyzwanie niebiosom. Ale u Mozarta ziemia się rozstępuje, pojawiają się upiory z czeluści, Don Giovanni prawdziwie poruszył niebo i ziemię. Tutaj nawet nie wiemy, czy Płatonow naprawdę poczuł w sobie moc, czy coś wykrzyknął w pijanym majaczeniu. Zaświaty pozostały obojętne. Czasami coś mu jeszcze zostaje z dawnego zapału, wykrzykuje "zacznij pracować", "skończ studia", "zajmij się swoimi pacjentami", ale nie widzimy, żeby sam korzystał ze swoich rad.

    Czechow nie oszczędza także swoich bohaterek. W "Don Giovannim" Mozarta tytułowy niegodziwiec depcze i łamie serca swoich ofiar, ale one same pozostają piękne i szlachetne ze swoimi zawiedzionymi uczuciami. U Czechowa Sonia, z którą kiedyś Płatonowa łączyło gorące uczucie zamyka się wyniośle w wieży. Ale gdy ku jej zdziwieniu rycerz nie przystępuje do szturmu, to sama schodzi i wciąga "rycerza" na górę. Generałowa Wojnicewa niemal na siłę wprasza się do Płatonowa, ale nie kieruje nią żadne uczucie. Chce po prostu wypróbować na nim siłę swoich wdzięków, tym bardziej, że czuje już upływ mijającego czasu.

    Przedstawienie jest prowadzone bardzo żywo i sprawnie. Trwa blisko cztery godziny (łącznie z przerwami), ale widzów ani na moment nie ogarnia znużenie. Słucha i ogląda się doskonale. Scenografia doskonale wpasowywuje się w nastrój sztuki. Mamy to niby salon w pańskim domu, który po kilku drobnych zmianach zamienia się w mało efektowne podwórze szkoły i nędzne mieszkanie wiejskiego nauczyciela, po czym znowu wracamy do salonu czy gabinetu. Nawet w drugim akcie, w scenie snu Płatonowa, gdy nachodzą go adoratorki, w dalszym ciągu mamy ten sam prowincjonalny salon. Bohaterowie są tak zanurzeni w swoim świecie, że nawet we śnie nie są w stanie wyczarować piękniejszej rzeczywistości.

    Bardzo dobrym zamysłem jest sam początek, przyjęcie w domu generałowej. Gości siadają na krzesłach zwróceni twarzą do widowni, a nie do siebie. W zasadzie nie muszą na siebie patrzeć ani nawet siebie słyszeć, po prostu znają siebie doskonale od lat i wiedzą, że niczego nowego nie usłyszą. Tylko widzowie mogą być tymi kwestiami jeszcze zainteresowania, ale wiemy, że następnego zaproszenia na to przyjęcie byśmy nie przyjęli.

    Podobał się także zamysł trzykrotnego powtórzenia końcowej sceny śmierci Płatonowa. W widowiskach sportowych często powtarza się pewne fragmenty aby widzowie dokładnie obejrzeli i zapamiętali kluczowe momenty gry. Tutaj realizator powtarza, aby narzucić widzom znaczenie: "umarł Płatonow i to jest bardzo ważne". Inaczej byśmy tego nie zauważyli, czy naprawdę coś się stało, czy to tylko kolejna błazenada. Płatonow wcześniej przyłożył sobie pistolet do skroni i łkał "ja chcę żyć". Spektakl się kończy, ale przecież nie dlatego, że jakieś wątki czy dylematy znalazły swoje rozwiązanie. Doskonale wiemy, co będzie dalej, bohaterowie (pomniejszeni o jedną osobę) będą dalej prowadzić swoje życie w ten sam sposób, ale widzów już to nie interesuje.

    Bardzo dobrze, że reżyserka (Agnieszka Glińska) nie próbowała na siłę uwspółcześniać sztuki. Czechow jednak dużo traci, gdy go się wyciąga z XIX-wiecznej  Rosji i przenosi do innego kontekstu. Pomimo tego nie jest to przecież tylko scenka rodzajowa sprzed 150 lat. Dylematy, rozterki i emocje bohaterów są nam bliskie i całkowicie zrozumiałe.

    Aktorzy bardzo dobrze i równo wykonywali swoje role, w zasadzie trudno wskazać jakieś słabe punkty. Oczywiście centralną postacią był Borys Szyc jako Płatonow, zebrał na koniec zasłużone i obfite oklaski. Mnie jednak czegoś zabrakło w tej roli. W miarę rozwoju akcji Płatonow coraz bardziej się stacza, jest coraz bardziej pijany, rozmamłany, niechlujny i cyniczny w stosunku do swoich adoratorek,  trudno zrozumieć, dlaczego jednak ich uczucia pozostają niezmienne. Dobrze byłoby przydać tej postaci choćby cień wdzięku czy uroku, tak abyśmy owego dawnego Płatonowa mogli dojrzeć nie tylko siłą swojej wyobraźni.

    Doskonałą rolę stworzyła także Monika Krzywkowska jako generałowa Wojnicewa. Z jednej strony jako osoba z życiowym doświadczeniem trochę matkuje otaczającej jej młodzieży, a z drugiej strony także jeszcze czegoś od życia oczekuje i tym jasnym punktem ma być sam Płatonow.

    W drugoplanowych rolach widzimy przedstawicieli "starej gwardii" aktorskiej jak Krzysztof Kowalewski, Damian Damięcki, Piotr Garlicki czy Janusz Michałowski.

    Bardzo nam się podobało przedstawienie, zdecydowanie polecamy i zachęcamy.