A Tutorial Advances in query languages for similarity-based databases
George J. Klir Petr Krajˇca State University of New York (SUNY) Binghamton, New York 13902, USA
[email protected] Palacky University, Olomouc, Czech Republic
!
prepared for International Centre for Information and Uncertainty, Palacky University, Olomouc
! !
! Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
1 / 16
RESIQL
1
RESIQL: relaˇcn´ı datab´azov´y syst´em implementace relaˇcn´ıho datab´azov´eho modelu navrˇzen´eho RB a VV platforma pro dalˇs´ı v´yzkum (algoritmy, z´avislosti, . . . ) ovˇeˇrov´an´ı vlasnost´ı datab´azov´eho modelu implementace v Javˇe ...
2
RESIQL: jazyk dotazovac´ı jazyk pro relaˇcn´ı datab´azov´y syst´em RESIQL ˇc´asteˇcnˇe kompatibiln´ı s SQL (v´yrazn´a inspirace Tutorial D) nˇekter´e ˇc´asti SQL zavrˇzeny (napˇr. SELECT)
Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
2 / 16
ˇ Zivotn´ ı cyklus dotazu I. RESIQL: klient uˇzivatelsk´e rozhran´ı na prvn´ı pohled ,,hloup´a” Swing-ov´a aplikace, kter´a ale um´ı: 1
zpracovat vstup od uˇzivatele a vypsat v´ysledek (vˇse lze volitelnˇe zform´atovat jako text nebo LaTex)
2
syntax-highlighting
3
n´apovˇeda k´odu
4
pr´ace s histori´ı ala BASH (historie pˇr´ıkaz˚ u uloˇzena pˇr´ımo v RESIQL)
5
um´ı poradit s opravou nˇekter´ych chyb
6
. . . (ˇrada dalˇs´ıch nedokumentovan´ych vlasnost´ı)
Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
3 / 16
Parser konverze vstupu do syntaktick´eho stromu vyuˇz´ıv´a se knihovna ANTLR (+ moˇznost pˇrepisovat AST) CREATE TABLE foo (a int, b int); STATEMENTS TABLE ACTION CREATE NAME foo TABLE COLUMNS a int b int Krajˇ ca P. (DAMOL)
– pˇr´ıkaz se vztahuje k tabulk´am – pˇr´ıkaz vytvoˇr tabulku – jm´eno tabulky – seznam sloupc˚ u – jm´eno sloupce – typ sloupce, popˇr. dalˇs´ı vlastnosti
RESIQL
8. 11. 2012
4 / 16
Front End konverze syntaktick´eho stromu do objekt˚ u (typicky POJO) tˇr´ıda QLCompiler podle typu objektu a n´azvu akce vol´a konverzn´ı metodu objekty maj´ı strukturu: public class CreateTableCommand extends GenericCommand { private String tableName; private List
columns; private List<String> primaryKey; ... public static final class ColumnDefinition { private String columnName; private String domain; ... Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
5 / 16
...koneˇcnˇe Akce pˇredchoz´ı objekt de facto popisuje, co se m´a s datab´az´ı dˇelat v dalˇs´ım kroce je objekt pˇreveden na objekt prov´adˇej´ıc´ı danou akci oddˇelen´ı tˇechto dvou krok˚ u umoˇzn ˇuje nˇekter´e operace zamˇen ˇovat (napˇr. SET a DELETE) kaˇzd´a akce dˇed´ı ze tˇr´ıdy QLStatement public abstract class QLStatement implements Closeable { // otestuje, jestli dan´y pˇr´ıkaz je moˇzno prov´est protected void check(IntegrityCheck check) { } // vrac´ı popis probl´em˚ u, kter´e se vyskytly public List<String> getKnownIssues() { ... } // provede dan´y pˇr´ıkaz public abstract QLResult invoke() throws BadRequestException; } Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
6 / 16
Manipulace s datab´az´ı veˇsker´e perzistentn´ı informace (tabulky, indexy, definice pohled˚ u, oper´ator˚ u, . . . ) jsou uloˇzeny stejnˇe jako uˇzivatelsk´a data vˇsechny tyto objekty spravuje tˇr´ıda Database pro kaˇzd´y typ objektu existuje samostastn´y Manager TableManager IndexManager ViewManager OperatorManager ...
pˇres tyto objekty prob´ıhaj´ı vˇsechny operace s databaz´ı spoleˇcn´e rozhran´ı, ˇreˇs´ı z´avislosti mezi objekty, . . . komunikuje pˇr´ımo se storage enginem, kter´y se star´a o uloˇzen´ı dat
Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
7 / 16
Storage engine BerkeleyDB Java Edition key-value store obstar´av´a ˇcistˇe uloˇzen´ı dat do tabulek + indexy vyhled´av´an´ı v datech s pomoc´ı B-strom˚ u zajistˇen´ı transakc´ı potenci´alnˇe nahraditeln´e nˇeˇc´ım jin´ym (InnoDB, Falcon, JDBC datab´aze, . . . )
Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
8 / 16
ˇ Zivotn´ ı cyklus dotazu II. RETRIEVE foo WHERE bar < 10; STATEMENTS RETRIEVE WHERE foo <
– pˇr´ıkaz – v´yraz
bar 10 prvn´ı f´aze zpracov´an´ı dotazu identick´a jako v prvn´ım pˇr´ıpadˇe odliˇsn´y je zp˚ usob zpracov´an´ı v´yrazu (z´asadn´ı ˇc´ast RESIQL)
Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
9 / 16
Kompilace v´yraz˚ u Aforismus (Greenspun’s tenth rule of programming) Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp. syntaktick´y strom je pˇreveden na strom objekt˚ u (instanc´ı tˇr´ıdy AbstractOperator), napˇr. WhereOperator Variable (foo) IntegerComparisonOperator (<) Variable (bar) Constant (10) kaˇzd´y objekt obsahuje: metody pro vyhodnocen´ı v´yrazu informace vztahuj´ıc´ı se k typ˚ um dat (popˇr. souvisej´ıc´ımu kontextu) metody pro dalˇs´ı transformace Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
10 / 16
Kompilace v´yraz˚ u Aforismus (Greenspun’s tenth rule of programming) Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp. syntaktick´y strom je pˇreveden na strom objekt˚ u (instanc´ı tˇr´ıdy AbstractOperator), napˇr. WhereOperator Variable (foo) IntegerComparisonOperator (<) Variable (bar) Constant (10) kaˇzd´y objekt obsahuje: metody pro vyhodnocen´ı v´yrazu informace vztahuj´ıc´ı se k typ˚ um dat (popˇr. souvisej´ıc´ımu kontextu) metody pro dalˇs´ı transformace Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
10 / 16
Kompilace v´yraz˚ u Aforismus (Greenspun’s tenth rule of programming) Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp. syntaktick´y strom je pˇreveden na strom objekt˚ u (instanc´ı tˇr´ıdy AbstractOperator), napˇr. WhereOperator Variable (foo) IntegerComparisonOperator (<) Variable (bar) Constant (10) kaˇzd´y objekt obsahuje: metody pro vyhodnocen´ı v´yrazu informace vztahuj´ıc´ı se k typ˚ um dat (popˇr. souvisej´ıc´ımu kontextu) metody pro dalˇs´ı transformace Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
10 / 16
Vyhodnocen´ı v´yraz˚ u nejdˇr´ıv vyhodnocen´ı v´yraz˚ u v potomc´ıch skal´arn´ı objekty se vyhodnocuj´ı na odpov´ıdaj´ıc´ı ,,javovsk´e” objekty relaˇcn´ı v´yrazy se vyhodnocuj´ı na Cursor: public interface Cursor extends Closeable { public boolean first() throws BadRequestException; public boolean next() throws BadRequestException; public Tuple fetch() throws BadRequestException; ... } relaˇcn´ı oper´atory zpracov´avaj´ı data po ˇr´adc´ıch (pokud je to moˇzn´e) relaˇcn´ı oper´atory vytv´aˇr´ı prostˇred´ı, ve kter´ych jsou vyhodnocov´any dalˇs´ı v´yrazy (napˇr. podm´ınka oper´atoru WHERE) v tomto prostˇred´ı jsou na symboly (odpov´ıd´aj´ıc´ı sloupc˚ um tabulky) nav´azany hodnoty z dan´eho ˇr´adku Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
11 / 16
Optimalizace (1/2) pˇred vyhodnocen´ım v´yrazu se provedou optimalizace transformace stromu objekt˚ u (AbstractOperator) na ekvivalentn´ı aplikace algebraick´ych z´akon˚ u (vˇcetnˇe ˇc´asteˇcn´eho vyhodnocen´ı podv´yraz˚ u) pouˇzit´ı oper´ator˚ u, kter´e nemaj´ı ekvivalentn´ı protˇejˇsek v jazyce RESIQL (napˇr. vyuˇzit´ı index˚ u)
sada pravidel pro pˇrepisov´an´ı pattern matching: DSL zaloˇzen´y na Fluent interface (vl´aˇcc´ıch) jednoduch´y ,,jazyk” (pˇr´ımo v Javˇe) schopn´y popsat z´akladn´ı vzory vyuˇz´ıv´a ˇcistˇe vol´an´ı metod a anonymn´ıch tˇr´ıd
Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
12 / 16
Optimalizace: pˇr´ıklady odstranˇen´ı dvoj´ıho WHERE: foo WHERE bar WHERE baz =⇒ foo WHERE bar ⊗ baz if (StructureCheck.check(operator) .isInstanceOf(WhereOperator.class) .itsArg(0).isInstanceOf(WhereOperator.class) .test()) { ... }
eliminace neutr´aln´ıho prvku (napˇr. 0 + x =⇒ x) if (StructureCheck.check(operator) .isInstanceOf(IntegerOperator.class) .isToken(QLLexer.PLUS) .itsArg(0).isEqual(ZERO INT) .test()) return operator.getArg(1);
Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
13 / 16
Optimalizace: Indexy a podobnostn´ı dotazy (1/2) Definition Podobnost ≈y nad dom´enou Dy je monotonn´ı vzhledem k ostr´emu line´arn´ımu uspoˇr´adn´ı C na mnoˇzinˇe Dy , pokud pro vˇsechny prvky u, v, w ∈ Dy plat´ı u ≈D w ≤ u ≈D v
(1)
pr´avˇe kdyˇz w C v C u nebo u C v C w. bˇeˇznˇe se podobnost odvozuje ze vzd´alenosti hodnot s pouˇzit´ım antitonn´ıho ˇsk´alovan´ı takov´a podobnost je monotonn´ı pokud dom´ena je restrikc´ı R, pak C odpov´ıd´a <
Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
14 / 16
Optimalizace: Indexy a podobnostn´ı dotazy (2/2) Pokud m´ame index (zaloˇzen´y na B-stromu) nad sloupci y1 , . . . , yn , hodnoty c1 ∈ Dy1 , . . . , cn ∈ Dyn , monotonn´ı oper´ator ≈yn , pak lze efektivnˇe z´ıskat ˇr´adky s nejvyˇsˇs´ımi ranky pro dotazy: (y1 = c1 ) ⊗ · · · ⊗ (yn−1 = cn−1 ) ⊗ (yn ≈yn cn ).
(2)
N´ astin algoritmu 1 dva kurzory – jeden pohybuj´ ıc´ı se vpˇred a druh´y vzad 2 na poˇ c´atku jsou oba kurzory nastaveny na ˇr´adek splˇ nuj´ıc´ı podm´ınku y1 = c1 , . . . , yn−1 = cn−1 , and yn = cn (nebo nejbliˇzˇs´ıho souseda) 3 kurzor pohybuj´ ıc´ı se vzad se posune o jeden ˇr´adek zpˇet 4 podm´ ınka (2) je vyhodnocena pro ˇr´adky, na kter´e ukazuj´ı oba kurzory 5 ˇ r´adek s vyˇsˇs´ım rankem je vr´acen a dan´y kurzor se posune o jeden ˇr´adek v dan´em smˇeru algoritmus lze zobecnit pro oper´atory <, ≤, ≥, between. . . . Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
15 / 16
Optimalizace: Indexy a podobnostn´ı dotazy (2/2) Pokud m´ame index (zaloˇzen´y na B-stromu) nad sloupci y1 , . . . , yn , hodnoty c1 ∈ Dy1 , . . . , cn ∈ Dyn , monotonn´ı oper´ator ≈yn , pak lze efektivnˇe z´ıskat ˇr´adky s nejvyˇsˇs´ımi ranky pro dotazy: (y1 = c1 ) ⊗ · · · ⊗ (yn−1 = cn−1 ) ⊗ (yn ≈yn cn ).
(2)
N´ astin algoritmu 1 dva kurzory – jeden pohybuj´ ıc´ı se vpˇred a druh´y vzad 2 na poˇ c´atku jsou oba kurzory nastaveny na ˇr´adek splˇ nuj´ıc´ı podm´ınku y1 = c1 , . . . , yn−1 = cn−1 , and yn = cn (nebo nejbliˇzˇs´ıho souseda) 3 kurzor pohybuj´ ıc´ı se vzad se posune o jeden ˇr´adek zpˇet 4 podm´ ınka (2) je vyhodnocena pro ˇr´adky, na kter´e ukazuj´ı oba kurzory 5 ˇ r´adek s vyˇsˇs´ım rankem je vr´acen a dan´y kurzor se posune o jeden ˇr´adek v dan´em smˇeru algoritmus lze zobecnit pro oper´atory <, ≤, ≥, between. . . . Krajˇ ca P. (DAMOL)
RESIQL
8. 11. 2012
15 / 16
Pˇrehled rozsahem menˇs´ı aˇz stˇrednˇe velk´y projekt pˇribliˇznˇe rok pr´ace na ˇc´asteˇcn´y u ´vazek pouˇzit´e knihovny: BDB JE, ANTLR, Guava, Log4J
RESIQL: RDBMS + klient Poˇcet tˇr´ıd: Poˇcet ˇr´adk˚ u k´odu:
cca 164 cca 13 tis.
Integraˇ cn´ı testy Poˇcet test˚ u: Poˇcet ˇr´adk˚ u k´odu:
Krajˇ ca P. (DAMOL)
83 cca 2 tis.
RESIQL
8. 11. 2012
16 / 16
