Pattern Based Management:
Data Models and Architectural
Aspects
Anna Maddalena
Dottorato di Ricerca in Informatica
XVIII ciclo
Dipartimento di Informatica e Scienza dell’Informazione
1
- Università di Genova -
Sommario:

Il contesto
 Gestione di pattern
 Il sistema
 Il modello
 Il linguaggio
 Architettura

Obiettivi della tesi
 Modello
 Linguaggi
 Architettura

Scheduling temporale
 Risultati preliminari
2
Il contesto
Analisi
queries
risultati
DBMS
DB1
- Il contesto -
DB2
Flat file
3
Soluzioni tradizionali
Analisi mediante
strumenti OLAP
queries
risultati
Data Warehouse
DBMS
DB1
- Il contesto -
DB2
Flat file
4
Architettura pattern-based
PBMS
Pattern base
queries
risultati
queries
risultati
analisi mediante
sofisticati strumenti di
processing dei dati
DBMS
DB1
- Il contesto -
DB2
Flat file
5
Dati grezzi e patterns

Dati grezzi
 Raccolti da diverse sorgenti
 Enormi volumi di dati
 Eterogenei

Pattern
 Rappresentazione dei dati grezzi compatta e
semanticamente ricca
6
- Il contesto -
Esempi di PATTERN
- Il contesto -
7
PATTERN: classificazione
Patterns
Quando/
Come?
A-priori
A-posteriori
Risultati tradizionali
di data mining
Cosa?
Test
Vincoli di
integrità
Attivi
Regole attive
workflow
- Il contesto -
Generativi
Targets
Tuple con vincoli Utilizzo nel
Regole deduttive pattern matching
8
Gestione di pattern
Il sistema di gestione
 Modello per rappresentare i pattern
 Linguaggio per manipolare i pattern
 Supporto architetturale

- Gestione di pattern -
9
Il sistema di gestione

Pattern-Base Management System
(PBMS) è una tecnologia per
 modellare i pattern come “first class
citizens”
 interrogare pattern
 gestire i pattern in modo efficiente
 gestire pattern eterogenei in modo
uniforme
- Gestione di pattern -
10
Il sistema di gestione
Query
Architettura Integrata
Raw data
Pattern
Processing
Query
PQL
Pattern
Cross-over
Architettura Separata
Raw data
Query tradizionali
(SQL)
- Gestione di pattern -
11
Il modello
Rappresentazione uniforme di pattern
eterogenei
 Caratteristiche pattern

 Struttura
 Misure di qualità
 Pattern complessi

Relazioni tra dati grezzi e pattern
 Mapping
 Validita’
- Gestione di pattern -
12
Il modello: esempi
Corpo

Testa
Regola di associazione: X  Y
S(X) = # di transazioni contenenti X Datasource
Supporto (X  Y) = S(XY)
Confidenza(X  Y) = S(XY)/S(X)
Mapping dati-pattern
Misure

 x (x  testa  x  corpo  x  transazione)
Cluster
Datasource
Struttura
RA 1
RA 2
RA 3
...
RA K
RA 5
RA 6
- Gestione di pattern -
X: rappr
Misure
DeviazioneConfidenza
DeviazioneSupporto
Mapping dati-pattern
RA.testa = rappr.testa
13
Il modello: approcci esistenti


Object Oriented
PMML(Predictive Model Markup Language) (2003), SQL/MM
(2001), Java Data Mining API (2003)
 Rappresentazione di mining model

Common Warehouse Model (2001)
 Scambio metadati

Database induttivi (1996/1997)

PANDA - PAtterns for Next-generation DAtabase systems (20012004)
 Netta separazione fra PBMS e repository dei dati sorgente
 Modello rappresenta pattern e relazioni fra pattern
• Pattern: structure, measure, source, expression
• Relazioni: specialization, composition, refinement
- Gestione di pattern -
14
Il modello: limitazioni

Ad esclusione di PANDA, per tutti gli altri approcci si
evidenziano le seguenti criticità:
 Spesso i dati grezzi e i pattern vengono memorizzati nello stesso
sistema di gestione dati
 Soluzioni specifiche per determinate tipologie di pattern
 Nessun mapping fra pattern e dati grezzi da cui sono stati
generati

Approccio O.O.
 Modellazione dei pattern e modellazione di oggetti generici sono
intrinsecamente differenti
–
–
–
–
Nuove componenti (measure, expression),
Nuovi requisiti (mapping fra source e pattern spaces),
Nuove relazioni (refinement),
Nuove operazioni (similarità)
- Gestione di pattern -
15
Il modello: limitazioni

PANDA primo modello per pattern eterogenei, ma ...
 Sincronizzazione fra pattern e dati grezzi
 Ontologie sui dati possono influenzare la generazione dei
pattern
 Possibilità di specificare ontologie sulle componenti dei
pattern
- Gestione di pattern -
16
I linguaggi

Linguaggio unificato per pattern eterogenei
 Manipolazione (inserimento, cancellazione,
modifica)
 Interrogazione (combinazione, sincronizzazione,
verifica validità, similarita’...)

Sfruttando appieno il modello
 Diverse tipologie di pattern
 Caratteristiche pattern
 Relazioni fra pattern
 Mapping pattern-dati (cross-over)
- Gestione di pattern -
17
I linguaggi: esempi

Derivare con il metodo A-priori le regole di associazione relative
all’insieme di transazioni Q1
 Dato un insieme di documenti XML clusterizzarli in base alla similarità
derivata dai loro link usando l’algoritmo di complete-link
 Da un insieme di clickstream sulla navigazione di un sito Web derivare i
profili utente in base alla durata delle loro sessioni





Interrogare il sistema di gestione di pattern per ritrovare tutti quelli
relativi al dataset Q1
Interrogare il sistema di gestione di pattern per estrarre tutte le regole
di associazione riguardanti “X”
Ritrovare nel sistema di gestione di pattern tutti i cluster “simili” a C1
Verificare se un dato pattern P è “valido” per un dataset D
Derivare per transitività tutti i pattern di tipo regole di associazione
utilizzando i pattern memorizzati nel sistema
- Gestione di pattern -
18
I linguaggi: approcci esistenti

Proposte:
 M-SQL (Imielinsky & Virmani, 1999)
 SQL+Mine (Meo,Psaila & Ceri, 1996)
 XML+Mine (Braga, Campi, Klemettinen & Lanzi, 2002)
 Pattern Discovery Algebra (1997)
 Information Discovery Data Mining Suite (2002)
 Linguaggi con vincoli (nei database induttivi solo per pattern
di tipo stringa)

Estensioni della sintassi SQL standard
- Gestione di pattern -
19
I linguaggi:esempio

SQL+Mine (Meo,Psaila & Ceri, 1996)
 MINE RULE SimpleAssociation AS
SELECT DISTINCT 1..n item AS BODY,
1..n item AS HEAD,
SUPPORT, CONFIDENCE
FROM Purchase
GROUP BY transaction
EXTRACTING RULES with SUPPORT: 0,1, CONFIDENCE 0,2



Solo regole di associazione
Algoritmo di mining prefissato
Solo estrazione on-the-fly
- Gestione di pattern -
20
I linguaggi: limitazioni




Mancanza di un linguaggio per la manipolazione e
l’interrogazione di pattern eterogenei
Spesso i linguaggi prevedono solo primitive per
l’estrazione dei pattern dai dati grezzi
Spesso si usano gli stessi linguaggi di interrogazione
sia per pattern che per i dati grezzi
Scarsa integrabilità dei dati grezzi e dei pattern
(cross-over queries)
- Gestione di pattern -
21
Architettura

Centralizzata
 Unica organizzazione
 Unico repository

Distribuita
 Interazione fra varie organizzazioni
 Vari repository
 Web ,P2P, GRID
- Gestione di pattern -
22
Architettura: pattern nel GRID

Architettura GRID
 “a flexible, secure, coordinated resource sharing among dynamic
collections of individuals, institution, and resources – what we
refer to as a Virtual Organizations”

Intelligent GRID:
 acquisizione, processing, rappresentazione, scambio e
conversione in conoscenza utile di dati eterogenei
disponibili a diversi livelli dell’architettura GRID
(HTML/XML/RDF doc., Service response time, service
quality level, ...)
 Knowledge Grid: Knowledge discovery e management
distribuito basato su un architettura di servizi GRID
(service discovery, negotiation, information extraction, ...)
 Semantic GRID: integrazione fra Semantic Web ed
ambiente GRID

Metadati & pattern
- Gestione di pattern -
23
Obiettivi della tesi

Task 1:
sviluppo ed estensione di un modello per la
rappresentazione dei pattern
 Task 2:
definizione di linguaggi per la manipolazione
di pattern
 Task 3:
aspetti architetturali e studio dell’estensibilità
a contesti distribuiti avanzati (es: GRID)
- Obiettivi della tesi -
24
Task 1: Modellazione di pattern

Definizione del modello
 Proposta modello PANDA
 teoria dei database con vincoli per esprimere alcune
componenti dei pattern

Estensione del modello con caratteristiche
avanzate:
 Aspetti temporali: problematiche di sincronizzazione
• teoria delle basi dati temporali applicata al contesto dei
pattern
 Gestione delle ontologie:
• Ontologie sui dati grezzi
• Ontologie sulle componenti dei pattern
- Obiettivi della tesi -
25
Task 2: Linguaggi per pattern

Definizione Pattern Manipulation Language
(PML)
 Inserimento, cancellazione e modifica di pattern

Definizione Pattern Query Language (PQL):
 Calcolo (CPQL)
 Algebra (APQL)
 Equivalenza fra CPQL e APQL
 Studio del potere espressivo dei linguaggi proposti

Rappresentazione di PML e PQL con sintassi
standard (es: SQL o XML)
- Obiettivi della tesi -
26
Task 3: Pattern management in
un contesto distribuito
Definizione di un’architettura per la
gestione dei pattern e dei metadati in un
ambiente distribuito (GRID)
 Revisione del modello e dei linguaggi
proposti nell’ottica distribuita
 Implementazione di un prototipo di un
sistema distribuito pattern-based

- Obiettivi della tesi -
27
Tempistica e fasi di progetto
Marzo
2003- Marzo 2006
Fasi di progetto:
Marzo 2003 – Dicembre 2003: obiettivi raggiunti
Dicembre 2003 - Marzo 2004: obiettivi breve termine
Marzo 2004 – Marzo 2005: obiettivi medio termine
Marzo 2005 – Marzo 2006: obiettivi lungo termine
- Scheduling Temporale -
28
Scheduling temporale
Tasks
Achieved Short
Medium
Long
T1
T2
- Scheduling Temporale -
March 2006
March 2005
March 2004
December 2003
March 2003
T3
Time
29
Obiettivi raggiunti

(Mar. 2003 - Dic. 2003)
Definizione del modello logico per pattern
 I.Bartolini et al. “Toward a Logical Model for Patterns”. ER’03
 E.Bertino, B.Catania, M. Golfarelli, M. Halkidi, A.Maddalena,
S.Skiadopoulos, S. Rizzi, M.Terrovitis, P. Vassiliadis, M.
Varzigiannis, and E.Vrachnos. “The Logical Model for Patterns”.
TR-2003-02, PANDA.

Identificazione operazioni significative per
PML e PQL, con definizione PML e proposta
preliminare di APQL
 “Toward a Language for Pattern Manipulation and Querying”
E. Bertino, B.Catania, A.Maddalena [sottomesso per pubblicazione]
30
Obiettivi a breve termine
(Dic. 2003 - Mar. 2004)

Estensione temporale del modello
 Transaction time e validity time
 Sincronizzazione

Estensione del modello con ontologie
 Ontologie sui dati grezzi
 Ontologie che coinvolgono le componenti dei
pattern

Definizione formale CPQL
 Estensione di un calcolo per oggetti complessi
(Abiteboul&Beeri, Fegaras&Maier)

Definizione formale APQL
- Scheduling Temporale -
31
Obiettivi a medio termine
(Mar.2004 – Mar.2005)

Dimostrazione equivalenza APQL e CPQL
 Analisi di complessità e potere espressivo del
PQL
 Utilizzo della teoria dei linguaggi con vincoli

Query optimization: strategie di riscrittura
 La gestione dei pattern in un’architettura
GRID
- Scheduling Temporale -
32
Obiettivi a lungo termine
(Mar.2005 – Mar.2006)
Definizione testbed GRID per la
gestione di pattern
 Estensione del modello e revisione
secondo il contesto GRID
 Prototipo Pattern-based GRID
Management System (?)

- Scheduling Temporale -
33
Risultati preliminari
Il modello
 I linguaggi per pattern

- Risultati preliminari -
34
Elementi di base
related-to
class
pattern type
member-of
instance-of
dec. tree type
supermarket rules
cluster type
pattern
my clusters
ass. rule type
class layer
type layer
pattern layer
- Risultati preliminari -
35
Pattern types

Basato su un sistema di tipi T:
 Tipi base:
• integers, reals, Booleans, strings, timestamps
 Tipi ricorsivamente definiti mediante costruttori di tipo
• list, set, bag, array, tuple

Esempi
 salary: REAL
 SET(INTEGER)
 TUPLE(x: INTEGER, y: INTEGER)
 personnel: LIST(TUPLE(age: INTEGER, salary: INTEGER))
- Risultati preliminari -
36
Pattern types
related-to
class
pattern type
name
structure schema
member-of
instance-of
source schema
measure schema
pattern
formula
• definisce
• definisceil il“pattern
“sourcespace”
space”
Tipo
delle
misure
che
• descrive
struttura
deiquantifi• tipo
dei la
dati
grezzi
cui i
Relazione
fra
il da
cano
la
qualità
della
rapprepattern,
istanze
delcostruiti
pattern
vengono
“source
space”
sentazione
dati sorgenti
pattern
type deispace”
e il “pattern
raggiunta dal pattern
- Risultati preliminari -
37
Pattern types - esempio
Association rule X  Y
S(X) = # of transactions containing X
Support (X  Y) = S(XY)
Confidence(X  Y) = S(XY)/S(X)
Y
X
n: AssociationRule
ss: TUPLE(head: SET(STRING), body: SET(STRING))
ds: BAG(transaction: SET(STRING))
ms: TUPLE(confidence: REAL, support: REAL)
f:  x (x  head  x  body  x  transaction)
ss
- Risultati preliminari -
ds
38
Patterns
related-to
class
pattern type
member-of
name
structure schema
instance-of
source schema
pattern
measure schema
PID
formula
structure
source
measure
expression
- Risultati preliminari -
39
Patterns - esempio
n: AssociationRule
ss: TUPLE(head: SET(STRING), body: SET(STRING))
ds: BAG(transaction: SET(STRING))
ms: TUPLE(confidence: REAL, support: REAL)
f:  x (x  head  x  body  x  transaction)
pid: 512
s: (head = {'Boots’}, body = {'Socks', 'Hat’})
d: SELECT SETOF(article) AS transaction
FROM sales GROUP BY transactionId
m: (confidence = 0.75, support = 0.55)
e: {transaction :  x (x  {'Boots', 'Socks','Hat'}  x  transaction)}
- Risultati preliminari -
{'Socks', 'Hat’}  {'Boots’}
40
Pattern Space e Data Space
data space
pattern type
dataset
PID
name
source schema
formula
pattern
backward
image
type
source
expression
structure
structure schema
pattern space
41
Classi
related-to
pattern type
name
member-of
name
structure schema
class
instance-of
source schema
pattern
measure schema
PID
formula
structure
source
measure
expression
- Risultati preliminari -
42
Classi - esempio
Dataset 1:
SELECT SETOF(article)
AS transaction
FROM sales_shop1
GROUP BY transactionId
Apriori
Pattern type:
AssociationRule
Dataset 2:
SELECT SETOF(article)
AS transaction
FROM sales_shop2
GROUP BY transactionId
- Risultati preliminari -
Patterns:
Association rules
512, 513, 514
Class: SaleRules
Apriori
Patterns:
Association rules
515, 516, 517
43
Relazioni fra pattern types

Specializzazione (IS-A)

Composizione (PART-OF) & Raffinamento
- Risultati preliminari -
44
Specializzazione
pattern type 1
related-to
class 1
inheritance
related-to
pattern type 2

Basata sulla
gerarchia dei tipi
(subtyping) in T
- Risultati preliminari -

Class 1 può
contenere anche
istanze del pattern
type 2
45
Specializzazione - esempio
n: AssociationRule
ss: TUPLE(head: SET(), body: SET())
ds: BAG(transaction: SET())
ms: TUPLE(confidence: REAL)
f:  x (x  head  x  body  x  transaction)
n: AssociationRuleOverStrings
ss: TUPLE(head: SET(STRING), body: SET(STRING))
ds: BAG(transaction: SET(STRING))
ms: TUPLE(confidence: REAL,support: REAL)
f:  x (x  head  x  body  x  transaction)
46
- Risultati preliminari -
Composizione & Raffinamento
pattern type 1
pattern type 1
part-of
refined-by
pattern type 2

Abilità di riferire
pattern types nello
structure schema
pattern type 2

Abilità di riferire
pattern types nello
source schema
47
- Risultati preliminari -
Composizione & Raffinamento: esempio
n: ClusterOfRules
ss: representative: AssociationRule
ds: SET(rule: AssociationRule)
ms: TUPLE(deviationOnConfidence: REAL,
deviationOnSupport: REAL)
f: rule.ss.head = representative.ss.head
- Risultati preliminari -
composizione
raffinamento
48
Risultati preliminari
Il modello
 I linguaggi per pattern

- Risultati preliminari -
49
Linguaggi per pattern

PML(Pattern Manipulation Language)
 Inserimento, cancellazione, modifica
di pattern

PQL (Pattern Query Language)
 Ritrovamento ed interrogazione di pattern
 Cross-over query: combinano pattern e dati
grezzi
- Risultati preliminari -
50
PML

Extraction
 Direct insertion
 Recomputation
 Deletion
 Restricted
Inserimento
Cancellazione
 Extended

Synchronize
 Insertion into class
 Deletion from class
- Risultati preliminari -
Modifica
Operazioni
su classi
51
PML: inserimento

Extraction
PT1
Mining algorithm
PT2
PT..
P1
C1
Sorgente
dati grezzi

Direct Insertion
name
s

PT1
d
C2
PT2
C..
PT..
P1
m
C1
e
C2
C..
Recomputation
PT1
P2
Sorgente
dati grezzi
- Risultati preliminari -
P1
C1
PT2
C2
PT..
C..
52
PML: cancellazione

Deletion restricted
NO!
X
P1
P4
P3
P2

PT1 PT2 PTN
C1
P1
P3
P2
OK!
PT1 PT2 PTN
P4
X
P1
C2
P3
P3
P2
C1
P3
P2
C2
P3
Deletion extended
XP1
P3
P4
P2
PT1
PT2
PTN
C1
C2
P1
X
P3
P2
- Risultati preliminari -
X
P1
C..
P3
53
PML:sincronizzazione

Synchronize
PT1
Sorgente
dati grezzi
p1
s
d
m m’
X
e
UPDATE
- Risultati preliminari -
54
PML: operazioni su classi

Insertion into class
P5
P4
PT2
PTN
PT1
P2
P3
P1
P1

C2
C1
P3
P2
Deletion from class
P5
P4
PT1
PT2
PTN
P2
P3
P1
C1
P1
X
P3
P2
- Risultati preliminari -
C2
55
PQL

Linguaggio chiuso rispetto a classi di pattern
 Operatori:
 Renaming
 Set-based operators ( , , \)
 Projection
 Selection
 Drill-down
 Roll-up
 Decomposition
 Join
• Natural join
 Cross-over operator
• Drill-through
• Covering
56
- Risultati preliminari -
PQL:projection
Solo per componenti “structure” e “measure”
 “Formula” proiettata sulle componenti rimanenti

AR1
...
pid: 512
s: (head = {'Boots’}, body = {'Socks', 'Hat’})
d: SELECT SETOF(article) AS transaction
FROM sales GROUP BY transactionId
m: (confidence = 0.75, support = 0.55)
e: {transaction :  x (x  {'Boots',
'Socks','Hat'}  x  transaction)}
...
(<head>,<support>)(AR1)
...
pid: 622
s: (head = {'Boots’})
d: SELECT SETOF(article) AS transaction
FROM sales GROUP BY transactionId
m: (support = 0.55)
e: {transaction :  x (x  {'Boots'}  x 
transaction)}
...
- Risultati preliminari -
57
PQL:selection

Predicati di selezione coinvolgono tutte le
componenti del pattern
 Operatori sui pattern
 Per struttura e misura:
• Identità (=i)
• Shallow (=se) e deep equality (=de)
 Per source ed expression:
• Equivalenza ()
• Contenimento ()
 AND, OR, NOT
- Risultati preliminari -
58
PQL:selection

Esempio:
’Boots’ IN s.head AND m.confidence>0.7(AR1)
AR1
pid: 512
s: (head = {'Boots’}, body = {'Socks', 'Hat’})
d: SELECT SETOF(article) AS transaction
FROM sales GROUP BY transactionId
m: (confidence = 0.75, support = 0.55)
e: {transaction :  x (x  {'Boots',
'Socks','Hat'}  x  transaction)}
pid: 513
s: (head = {'Boots’}, body = {‘Pant’})
d: SELECT SETOF(article) AS transaction
FROM sales GROUP BY transactionId
m: (confidence = 0.60, support = 0.60)
e: {transaction :  x (x  {'Boots', ‘Pant’} 
x  transaction)}
pid: 512
s: (head = {'Boots’}, body = {'Socks', 'Hat’})
d: SELECT SETOF(article) AS transaction
FROM sales GROUP BY transactionId
m: (confidence = 0.75, support = 0.55)
e: {transaction :  x (x  {'Boots',
'Socks','Hat'}  x  transaction)}
59
- Risultati preliminari -
PQL:drill-down e roll-up

Navigazione della gerarchia di
raffinamento
C
ClusterOfRules
Drill-down
refined-by
CR1
Roll-up
rule(C)
ClusterOfRules(A)
A
AssociationRule
AR2
ARN
AR1
AR3
60
PQL:decomposition

Navigazione della gerarchia di
composizione
ClusterOfRules
...
representative: AR1
Ca(CR1)
...
part-of
AR1
AssociationRule
61
PQL:join

Pattern di classi diverse: C1 e C2
 I pattern types devono essere join
compatible
 Data source compatibility
 Structure compatibility

Join predicate F: qualunque condizione di
selezione definita su una componente di un pattern
in C1 e di un pattern in C2

Composition Function: c=(css,cds,cms,cf)
C1 || F,c C2
62
PQL: join - esempio

Proprieta transitiva delle regole di associazione
 Se “AB” e “B C” sono due regole, allora
“AC” è una regola
pid: 512
s: (head = {'Boots’}, body = {'Socks'})
d: Query_1
C1 || C1.ss.body=C2.ss.head , c
C2
m: (confidence = 0.75, support = 0.55)
e: {transaction :  x (x  {'Boots', 'Socks'}  x
 transaction)}
pid: 710
pid: 513
s: (head = {'Boots’}, body = {‘Hat'})
s: (head = {‘Socks’}, body = {‘Hat’})
d: Query_1 |X| Query_2
d: Query_2
m: (confidence = null, support = null)
m: (confidence = 0.60, support = 0.50)
e: {transaction :  x (x  {'Boots', Hat}  x 
transaction)}
64
e: {transaction :  x (x  {‘Socks', ‘Hat’}  x 
transaction)}
- Risultati preliminari -
PQL: cross-over
Mettono in relazione pattern e dati grezzi
 Drill-through: navigazione dal pattern
layer al data layer

 Input: classe
 output: insieme di dati grezzi

Covering: verifica se un pattern è valido
per uno specifico dataset
- Risultati preliminari -
65
PQL: cross-over
Esempi
 Drill-through


A(C)
pid
s
d:query_1
m
e
Query_1
Covering
p
DS
- Risultati preliminari -
(p,d)
?
p
DS
66