Databases Reference
In-Depth Information
templates. In Sect. 6 we discuss some search algorithms that might be used to
locate optimal templates.
Before we consider an ordering over templates, we consider ordering over
the terms that make up a template. We want to define the relations
t
1
>
s
t
2
to mean that term
t
1
is a more specific attribute than term
t
2
,and
t
1
≥
s
t
2
to mean that
t
1
is at least as specific as
t
2
. Similarly,
t
1
<
s
t
2
and
t
1
≤
s
t
2
mean “less specific than” and “no more specific than” respectively. We now
define these by introducing “superset ordering”.
3.1 Superset Ordering of Terms and Template Elements
We start by defining a specificity ordering over terms such that each term
matches every word that its antecedent matches, along with zero or more
extra words. We call this superset ordering.
Definition 15.
Let
≥
s
be the ordering over superset specificity. Let t
1
,t
2
be
terms. If µ
(
t
1
)
⊆
µ
(
t
2
)
then t
1
≥
s
t
2
, and we say that t
1
is at least as specific
as t
2
.Ifµ
(
t
1
)
⊂
µ
(
t
2
)
then t
1
>
s
t
2
, and we say that t
1
is more specific
than t
2
.
Examples:
Let FELINE and ANIMAL be two terms (specifically, gazetteers), such
that
µ
(FELINE) =
{
cat, lion, tiger, . . .
}
and
µ
(ANIMAL) =
{
antelope
,
dog,
cat
,...,
lion
,...,
tiger
,...,
zebra
}
.Then
µ
(FELINE)
⊂
µ
(ANIMAL) and so
FELINE
>
s
ANIMAL.
µ
(
α
Λ
(cat)) =
{
cat
}
.
α
Γ
(cat) =
{
FELINE, ANIMAL
}
µ
(
{
FELINE
,
ANIMAL
}
)=
{
cat, lion, tiger, antelope, dog, . . .
}
µ
(
α
Γ
(cat)).
Some specificity orderings are dependent on the categories of the two
terms. For example, by definitions 9 and 10, it is clear that each literal
is a member of all the terms that are attributes of the literal. Therefore
µ
(
λ
)
Therefore
µ
(
α
Λ
(cat))
⊂
K, t
1
≥
s
t
2
.
In other words, terms that represent literals are at least as specific as any
other terms. At the other extreme, the wildcards “*” and “?” match every
word, so we can say that wildcard terms are no more specific than any other
term. I.e. if
t
1
∈ κ
Ω
,then
∀ t
2
∈ K, t
2
≥
s
t
1
.
Having defined an ordering over terms, we now consider sets of terms, and
template elements in particular. Let
T
1
and
T
2
be two template elements. We
say that
T
1
is at least as specific as
T
2
if and only if every literal matched by
any term in
T
1
is also matched by some term in
T
2
:
⊆
µ
(
α
λ
)
∀
κ
∈
K
and therefore if
t
1
∈
κ
Λ
,then
∀
t
2
∈
T
1
≥
s
T
2
⇐⇒ ∀
λ
∈
µ
(
T
1
)
,λ
∈
µ
(
T
2
)
Similarly,
T
1
>
s
T
2
⇐⇒ ∀
λ
∈
µ
(
T
1
)
,λ
∈
µ
(
T
2
)and
∃
λ
∈
µ
(
T
2
)such
that
λ/
∈
µ
(
T
1
)
.
I.e.
T
1
is more specific than
T
2
if every literal matched by a
