Podstawowy język semistrukturalny

• pierwsza krawędź biblio
• druga od końca krawędź section
• przedostatnia krawędź title lub Title lub paragraph
• ostatnia krawędź z podciągiem "heading"

Grafy cykliczne

• ścieżki o dowolnej długości
• nieskończona liczba ścieżek (_*)
• ale skończony zbiór wierzchołków
• trudności znalezienia wyników

Oznaczenia

• e - opis ścieżki
• D - graf danych
• A - automat odpowiadający e
• {x₁, x₂, ...} - wierzchołki w D
  • x₁ - korzeń
• {s₁, s₂, ...} - stany A
  • s₁ - stan początkowy

Obliczenie wyniku

• początkowo Domknięcie = {(x₁,s₁)}
• powtarzaj:
  • niech (x,s) należy do Domknięcie
  • w grafie D krawędź
  • w automacie A przejście
  • dodaj parę (x',s') do Domknięcie
• przerwij, gdy Domknięcie się już nie da powiększyć

Złożoność

• procedura kończy się
• pesymistycznie: O(|A| * |D|)
• w praktyce
  • każdy wierzchołek co najwyżej raz
  • pomijamy fragmenty grafu

Podstawa języka

• opisy ścieżek - braki
• tworzenie nowych wierzchołków
• operacje łączenia
• sprawdzanie wartości

Podstawowa składnia

• Lorel
• UnQL
• OQL

select author: X
from biblio.book.author X

{author: "Roux",
 author: "Combalusier",
 author: "Smith"}

Klauzula where

• zapytanie

  select row: X
  from biblio._ X
  where "Smith" in X.author

• wynik
  • graf
    
  • ssd-wyrażenie

    {row: {author: "Smith",
           date: 1999,
           title: "Database Systems"}, ...}
    

Wprowadzanie zmiennych

select author: Y
from biblio._ X,
     X.author Y,
     X.title Z
where matches(".*(D|d)atabase.*", Z)

Semantyka

• select E from B where C

• trzy kroki

  1. from

     • zbiór powiązań ze zmiennymi
     • np. X, Y, Z

  2. where

     • filtracja
     • w wyniku zbiór
     • {(x₁, y₁, z₁), ..., (x_n, y_n, z_n)}

  3. select

     • konstrukcja ssd-wyrażenia;
     • {E(x₁, y₁, z₁), ..., E(x_n, y_n, z_n)}

Tworzenie wierzchołków

• konstrukcje z użyciem nawiasów
  • zapytanie

    select row: { title: Y, author: Z }
    from biblio.book X, X.title Y, X.author Z

  • wynik

    {row: {title: y1, author: z1},
     ...,
     row: {title: yn, author: zn}}

• podzapytania
  • zapytanie

    select row: (select author: y
                 from X.author Y)
    from biblio.book X

  • wynik
    • graf
      
    • ssd-wyrażenie

      { row: {author: "Roux", author: "Combalusier"},
        row: {author: "Smith"} }

Ogólniejsze formy selekcji

• zapytanie

  select row: (select author: Y, title: T
               from    X.author Y,
                       X.title T)
  from biblio.book X
  where "Roux" in X.author

• wynik
  • graf
    
  • ssd-wyrażenie

    { row: { author: "Roux", title: "Database Systems" },
      row: { author: "Combalusier", title: "Database Systems" }

Operacje łączenia

• schemat relacyjny

  r1(a, b), r2(b, c)

• instancja
  • tabelki (relacje)

    => select * from r1;
     a | b 
    ---+---
     1 | 2
     1 | 3
    (2 rows)
    
    => select * from r2;
     b | c 
    ---+---
     2 | 4
     2 | 3
    (2 rows)
    

  • ssd-wyrażenie

    { r1: { row: {a: 1, b: 2},
            row: {a: 1, b: 3} },
      r2: { row: {b: 2, c: 4},
            row: {b: 2, c: 3} } }

• zapytanie
  • SQL

    => select X.a, Y.c from r1 X, r2 Y where X.b = Y.b;
     a | c 
    ---+---
     1 | 4
     1 | 3
    (2 rows)

  • język semistrukturalny

    select a: A, c: C
    from r1.row X,
         r2.row Y,
         X.a A, X.b B, Y.b B', Y.c C
    where B = B'

Wielokrotne wystąpienia

select row: W
from biblio.paper X, X.refers-to Y, Y.author W,
     X.refers-to Z
where NOT (Y = Z)
  and W in Z.author
  and matches(".*Database.*", X.title)