Documenti non strutturati sul Web
e Semantica
Dott. Matteo Palmonari
[email protected]
Semantica nelle basi di dati
relazionali
• La semantica di una base di dati è definita in accordo con
la struttura relazionale (algebra relazionale) ed è
determinata, relativamente ai suoi elementi costitutivi
(valori, tuple, relazioni), sostanzialmente da:
• Livello dello schema:
• schema logico
• definisce la macro-organizzazione della
rappresentazione di un dominio
• vincoli di integrità
• definiscono vincoli relazionali di dettaglio tra specifici
oggetti e fatti rappresentati
• Livello delle istanze:
• insieme delle istanze
• costituisce l‘insieme di oggetti e fatti effettivamente
rappresentati come veri nella bas di dati
–Rielaborato da Atzeni et al., Basi di
Dati, Mc-Graw Hill
–2
Semantica, Schemi e Istanze
• Lo schema di una base di dati definisce le regole generali
cui deve aderire ciascun insieme di istanze (per essere
considerato valido); è in questi termini che lo schema
costituisce una parte fondamentale della semantica di
una base di dati
• Tali regole (ad esempio i vincoli di integrità)
• supportano l‘interrogazione delle basi di dati (verifica
della sussistenza o non sussistenza di alcuni fatti nella
base di dati)
• permettono di controllare la validità dello schema
• non permettono di dedurre nuove conoscenze
–Rielaborato da Atzeni et al., Basi di
Dati, Mc-Graw Hill
–3
Query nel modello relazionale
• Il linguaggio di
interrogazione
piùdiffuso per le basi
di dati è SQL
(Structured Query
Language)
• Ragionamento
piuttosto debole
–Rielaborato da Atzeni et al., Basi di
Dati, Mc-Graw Hill
–4
SQL Query Example
• SQL (base/select)
• Principio: soddisfazione/correttezza
• Meccanismo/semantica: algebra
relazionale
–Rielaborato da Atzeni et al., Basi di
Dati, Mc-Graw Hill
–5
Esempi di altri data model
–Rielaborato da Atzeni et al., Basi di
Dati, Mc-Graw Hill
–6
The Object-Oriented
Data Model
Objects/id
Attributes
Methods
Classes
Class Hierachies
Alla base di
JAVA/C++ etc
–Rielaborato da Atzeni et al., Basi di
Dati, Mc-Graw Hill
–7
Object-Oriented Schema (Example)
–Rielaborato da Atzeni et al., Basi di
Dati, Mc-Graw Hill
–8
Cosa succede nel Web?
• Ci sono ancora schemi e istanze?
• Che tipo di interrogazioni si
possono fare?
• Che tipo di ragionamenti si
possono fare?
–Rielaborato da Atzeni et al., Basi di
Dati, Mc-Graw Hill
–9
Web page (Web 1.0)
Rielaborato da Atzeni et al., Basi
di Dati, Mc-Graw Hill
10
Information Retrieval
The information retrieval system has to deal with the
following tasks…
Micro-Introduction to
Information Retrieval &
Search Engines
Slides and material from
Karl Aberer
EPFL-IC, Laboratoire de
systèmes d'informations répartis
Information Retrieval – Document Model
• Generating structured representations of information
items: this process is called feature extraction and can
include simple tasks, such as extracting words from a
text as well as complex methods, e.g. for image or video
analysis.
Information Retrieval – Query Model
• Generating structured representations of information needs: often
this task is solved by providing users with a query language and
leave the formulation of structured queries to them. This is the case
for example for simple keyword based query languages, as used in
Web search engines. Some information retrieval systems also
support the user in the query formulation, e.g. through visual
interfaces.
Information Retrieval – Matching Model
• Matching of information needs with information items: this is the
algorithmic task of computing similarity of information items and
information need and constitutes the heart of the information
retrieval model. Similarity of the structured representations is used
to model relevance of information for users. As a result a selection
of relevant information items or a ranked result can be presented to
the user.
Information Retrieval - Efficiency
Since information retrieval systems deal usually with large
information collections and/or large user communities, the
efficiency of an information retrieval system is crucial. This imposes
fundamental constraints on the retrieval model. Retrieval models
that would capture relevance very well, but are computationally
prohibitively expensive are not suitable for an information retrieval
system.
Text Retrieval (search engines)
The currently most popular information retrieval systems are Web
search engines. To a large degree, they are text retrieval system,
since they exploit only the textual content of Web documents for
retrieval. However, more recently Web search engines also start to
exploit link information and even image information (e.g. Google’s
page Rank). The three tasks of a Web search engine for retrieval
are:
Text Retrieval (search engines)
1. extracting the textual features, which are the words or terms that
occur in the documents. We assume that the web search engine has
already collected the documents from the Web using a Web
crawler.
Text Retrieval (search engines)
2. support the formulation of textual queries. This is usually done by
allowing the entry of keywords through Web forms.
Text Retrieval (search engines)
3. computing the similarity of documents with the query and
producing from that a ranked result. Here Web search engines
use standard text retrieval methods, such as Boolean retrieval and
vector space retrieval.
The Retrieval Model
• Determines
– the structure of the document representation
– the structure of the query representation
– the similarity matching function•
• Relevance
– determined by the similarity matching function
– should reflect right topic, user needs, authority, recency
– no objective measure•
• Quality of a retrieval model depends on how well it
matches user needs !
• Comparison to database querying
– correct evaluation of a class of query language expressions
– can be used to implement a retrieval model
The Retrieval Model
• The heart of an information retrieval system is its
retrieval model. The model is used to capture the
meaning of documents and queries, and determine from
that the relevance of documents with respect to queries.
Although there exist a number of intuitive notions of what
determines relevance one must keep clearly in mind that
it is not an objective measure. The quality of a retrieval
system can principally only be determined through the
degree of satisfaction of its users. This is fundamentally
different to database querying, where there exists a
formally verifiable criterion for the task to be performed:
whether a result set retrieved from a database matches
the conditions specified in a query.
The Vector Space Model
Example
The document model
• the structure of the document representation
– Term-document matrix
Example Vector-Space Retrieval
Introduction
What does Google “understand”?
 Understanding that
• [page1] links [page2]  page2 is interesting
 Google is able to rank results!
• “The heart of our software is PageRank™, a system for
ranking web pages […] (that) relies on the uniquely
democratic nature of the web by using its vast link
structure as an indicator of an individual page's value.”
http://www.google.com/technology/
–Emanuele Della Valle - http://applied-semantic-web.org
–27
Pagine Web: query model
• Principio: “rilevanza” (documenti rilevanti)
• Meccanismo/semantica:
– Contenuto: indicizzazione (feature extraction):
keywords + testo
– Provenienza: pageRank
–…
• Meccanismi sintattici e basati su criteri di
trust
28
Directories
File system
Web
Directories
Web
Directories
Blogs by topics
Directories: query model
• Principio: “appartenenza alla directory”
(correttezza)
• Meccanismo/semantica:
– Contenuto: documenti appartenenti alle
categorie / relazione di contenimento tra
categorie
• Meccanismi di organizzazione gerarchica
delle informazioni
32
Metadata / Tag / Folksonomies
• Metadati: dati che descrivono altri dati/documenti
– E.g. creatore, autore, ultima modifica etc.
– E.g. contenuto, caratteristiche, etc
• Sistemi di metadati Attributo-Valore
– E.g. creatore: Matteo Palmonari
– Spesso sistematizzati in standard o standard di fatto
• E.g. Dublincore (metadati generici)
– http://dublincore.org/
• E.g. MPEG-7 (audio/video)
– http://mpeg.chiariglione.org/standards/mpeg-7/mpeg-7.htm
• Sistemi di tag
– E.g. Viaggi, Malesia, Mare
Metadata / Attribute-Value
File system
Music
Metadata / Attribute-Value
File system / Images
Metadata / Attribute-Value
Web / Images
Metadata & Search
Web / Images
Metadata & Search
Web / Images / Search: ‘where=malaysia’
Folksonomies
• Tagging systems
– Tags (sort of concepts)
associated with pieces
of information
• E.g. blog posts,
videos, pictures
Folksonomies & Search
Tag Clouds
Folksonomies
Blogs
Folksonomies
• Tagging systems
– Tags (sort of concepts) associated wit pieces of
information
• E.g. blog posts, videos, pictures
– Semantic weaknesses:
1.the ambiguity of tags, for one tag may refer to several
concepts ;
2.the variability of the spelling, for several tags may refer to the
same concept;
3.the lack of explicit representations of the knowledge
contained in folksonomies, ambiguous relations between the
piece of information and the tag;
4.the difficulties to deal with tags from different languages.
Folksonomies: query model
• Principio: “rilevanza”/”correttezza”
• Meccanismo/semantica:
– Associazione tag:
• Per una query con un tag T, si trovano tutti I
documenti relativi a T (annotati con T, annotati con
tags simili a T etc…)
• Costruzione collaborativa dei sistemi di tag
(tag cloud)
• Semantic Ambigua
43
Schema vs Schemaless
• Uno schema per un insieme di dati specifica
vincoli di carattere generale tra i dati
– Tali vincoli organizzano in dati strutture
– I dati organizzati in strutture per mezzo di schemi si
dicono dati strutturati (esempio: dati delle basi di dati
relazionali)
– La struttura fornisce una chiave interpretativa per i
dati
– La struttura può essere utilizzata per definire
interrogazioni corrette rispetto al modello in oggetto
Schema vs Schemaless
• Esprimere vincoli su dati ha un costo:
– Costo di creazione
– Costo di mantenimento
– Costo di gestione
– Costo in termini di efficienza delle
procedure di interrogazione
Schema vs Schemaless
• Sistemi di metadati quali i sistemi di tag
(annotazione) suppliscono alla mancanza di
schema associando informazioni aggiuntive ai
dati
• Tali informazioni possono supportare le
procedure di interrogazione fornendo diverse
dimensioni di ricerca e rendendole più precise
• La semantica di tali dati resta tuttavia più
ambigua e, in generale, imprecisa
Schema vs Schemaless
• Come associare semantica in modo meno
ambiguo sul Web?
• Annotazione dei contenuti sul Web con tecniche
più sofisticate (XML, RDF, Ontologie)
Intensione/Estensione
• Nei dati strutturati è possibile individuare
due aspetti delle informazioni e
conoscenze rappresentate:
– Intensione: vincoli generali di dominio
– Estensione: dati, istanze di oggetti che
soddisfano determinati vincoli
Parte Intensionale
 Studente Voto
Esami
Parte Estensionale 
Estensione del concetto
“voto di studente”
276545
276545
787643
739430
32
30
27
24
Lode Corso
01
e lode 02
e lode 03
04
Intensione/Estensione
Linguaggi formali per rappresentare la conoscenza:
Cosa rappresentare?
Linguaggio (L)
Concetti  Predicati unari P(x)
Relazioni  Predicati binari, ternari ... R(x,y), R(x,y,z)
inferenza
Semantica (M)
Semantica standard su base insiemistica:
Concetti  Insiemi
Relazioni  Insiemi di n-uple
Rappresentazione ESTENSIONALE!
Statica...
Conoscenza
sulla realtà
Intensione/Estensione
Linguaggi formali per rappresentare la conoscenza:
Cosa rappresentare?
Linguaggio (L)
Concetti  Predicati unari P(x)
Relazioni  Predicati binari, terziari ... R(x,y), R(x,y,z)
Semantica (M)
Semantica standard su base insiemistica:
Concetti  Insiemi
Relazioni  Insiemi di n-uple
Rappresentazione ESTENSIONALE!
Statica...
Conoscenza
Intensione/Estensione
Quello che interessa dal punto di vista della possibilità
di fare inferenza è una caratterizzazione della
rappresentazione che tratti concetti e relazioni
indipendentemente dagli oggetti che nella circostanza
specifica entrano a darne la definizione estensionale.
INTENSIONE di concetti e relazioni:
Linguaggio (L)
Proprietà formali di alto livello
Necessità di un linguaggio per definirle
E.g. IN è transitiva
E.g. Inferire IN(x,z)
Da: IN(x,y) + IN(y,z)
inferenza
Semantica (M)
Conoscenza
Intensione e inferenza
Proprietà di alto livello
(aspetti intensionali di una base di conoscenza)
1. Coinvolgono una sola relazione:
e.g. simmetria:
R( x, y) → R( y, x)
2. Coinvolgono più concetti/relazioni:
a - Interdipendenze e interdefinizioni tra relazioni
N ( x, y)∧E ( x, y) ↔ NE( x, y)
N ( x, y)∧IN ( z, y) → N ( x, z )
e.g. Nord Est = Nord ∩ Est
e.g. ?
b - Relazioni tra concetti
e.g. FiguraGeometrica e Triangolo...
Triangolo( x) → FigGeometrica( x)
1- Inferenza: proprietà delle
relazioni
1 – Proprietà delle relazioni
e.g. IN: Transitività...
IN(a,b); IN(b,d); IN(d,e); IN(e,c)
a
a
b
c
1
f
f
IN ( x, y) ∧ IN ( y, z ) → IN ( x, z )
Assioma di L
1
c
e
e
1
b
d
d
1
1- Inferenza: proprietà delle
relazioni
IN: Transitività...
IN(a,b); IN(b,d); IN(d,e); IN(e,c)
a
b
c
d
e
a
1 1 1 1
b
1 1 1
c
d
e
f
f
Altre proprietà?
e.g. antisimmetria?
Più proprietà? (coerenza?)
e.g. antisim + rifl + trans?
1
1
1
antisim + irrifl + trans
⇝⊥
Relazioni tra concetti
Figura geometrica
e.g. FiguraGeometrica e Triangolo...
Triangolo
Sfera
Triangolo IS-A FigGeometrica
Triangolo( x) → FigGeometrica( x)
Triangolo è sussunto da FigGeometrica ?
Triangolo eredita le proprietà di FigGeometrica ?
haPerimetro(x)
∃(y ).FigGeometrica( y) ∧Perimetro( y) ∧PartOf ( y, x)
...
Da 1.a: N ( x, y)∧E ( x, y) ← NE( x, y)
NordEst IS-A Nord ???
...
Schema, Vincoli, Ontologie
• Schema vs Schemaless: un continuoum
• Schema, logicamente: un insieme più o meno
ricco di vincoli
– Schema di database: insieme di vincoli piuttosto
ristretto
– Schema di database più vincoli di integrità: insieme di
vincoli più sofisticato
– Schema di database più vincoli di integrità più
business rules: insieme di vincoli molto sofisticato
(infatti, intrattabile computazionalmente)
– “Ontologie”