Seminar 12
Exercise 12/1
Pick a topic of your interest and describe it by 5-10 words.
Open Sketch Engine https://ske.fi.muni.cz/. Go to WebBootCaT. Create a corpus
using the description words as seed. Wait until data are downloaded. Search the word
corpus for collocations.
Solutions can vary.
Definition 1 (Index Relations)
Suppose that we could pick a random page from the index of 𝐸1 and test whether it is
in 𝐸2’s index and symmetrically, test whether a random page from 𝐸2 is in 𝐸1. These
experiments give us fractions 𝑥 and 𝑦 such that our estimate is that a fraction 𝑥 of the
pages in 𝐸1 are in 𝐸2, while a fraction 𝑦 of the pages in 𝐸2 are in 𝐸1. Then, letting |𝐸𝑖|
denote the size of the index of search engine 𝐸𝑖, we have
𝑥|𝐸1| ≈ 𝑦|𝐸2|,
from which we have the form we will use
|𝐸1|
|𝐸2|
≈
𝑦
𝑥
.
Exercise 12/2
Two web search engines 𝐴 and 𝐵 each generate a large number of pages uniformly at
random from their indexes. 30% of 𝐴’s pages are present in 𝐵’s index, while 50% of 𝐵’s
pages are present in 𝐴’s index. What is the number of pages in 𝐴’s index relative to
𝐵’s?
Substituting to the Definition 1 we get the fractions
∙ 3
10 of 𝐴 is in 𝐵
∙ 5
10 of 𝐵 is in 𝐴
and we get the equation
0.3|𝐴| ≈ 0.5|𝐵|
|𝐴|
|𝐵|
≈
0.5
0.3
|𝐴|
|𝐵|
≈
5
3
Definition 2 (Path Similarity)
Similarity between a query XPath 𝑐 𝑞 and a document path 𝑐 𝑑 is calculated as
𝐶𝑅(𝑐 𝑞, 𝑐 𝑑) =
{︃
1+|𝑐 𝑞|
1+|𝑐 𝑑| if 𝑐 𝑞 can be expanded to 𝑐 𝑑 by adding nodes to the path
0 otherwise
1
Definition 3 (Structural Term)
Structural term is defined as an XML-context/term pair denoted by <c,t> of existing
path to a value and the value itself, where the value itself is also a node in the XML
document. For example, an XML document containing only a root element with test.
<root>
test
</root>
contains two structural terms </root/,test> and </,test>.
Exercise 12/3
Consider the following the XML document:
<Course_Catalog>
<Department Code="CS">
<Title>Computer Science</Title>
<Chair>
<Professor>
<First_Name>Jennifer</First_Name>
<Last_Name>Widom</Last_Name>
</Professor>
</Chair>
<Course Number="CS106A" Enrollment="1070">
<Title>Programming Methodology</Title>
<Description>Introduction to the engineering of computer applications
emphasizing modern software engineering principles.
</Description>
<Instructors>
<Lecturer>
<First_Name>Jerry</First_Name>
<Middle_Initial>R.</Middle_Initial>
<Last_Name>Cain</Last_Name>
</Lecturer>
<Professor>
<First_Name>Eric</First_Name>
<Last_Name>Roberts</Last_Name>
</Professor>
<Professor>
<First_Name>Mehran</First_Name>
<Last_Name>Sahami</Last_Name>
</Professor>
</Instructors>
</Course>
<Course Number="CS106B" Enrollment="620">
<Title>Programming Abstractions</Title>
<Description>Abstraction and its relation to programming.</Description>
<Instructors>
<Professor>
<First_Name>Eric</First_Name>
<Last_Name>Roberts</Last_Name>
</Professor>
<Lecturer>
2
<First_Name>Jerry</First_Name>
<Middle_Initial>R.</Middle_Initial>
<Last_Name>Cain</Last_Name>
</Lecturer>
</Instructors>
<Prerequisites>
<Prereq>CS106A</Prereq>
</Prerequisites>
</Course>
</Department>
</Course_Catalog>
1. Write the following expressions:
a) Return all titles (including both departments and courses).
b) Return all course titles that contain the word programming.
c) Return the surnames of all instructors teaching at least one course that contains
the word software in its description.
d) Return the surnames of all professors teaching at least one course that contains
the word software in its description.
2. Calculate the similarity between the queries and the corresponding document paths.
a) //Instructors//Last_Name#Cain
b) //Course/Instructors/Lecturer/Last_Name#Cain
1. a) //Title
b) //Course//Title[contains(current(),’programming’)]
c) //Course[contains(Description,’software’)]/Instructors//Last_Name
d) //Course[contains(Description,’software’)]/Instructors/Professor/Last_Name
2. By Definition 2, a query 𝑐 𝑞 corresponds to document 𝑐 𝑑 if and only if it can be
expanded. Original query for a) can be expanded to
Course_Catalog/Department/Course/Instructors/Lecturer/Last_Name.
Since 𝑐 𝑞 is expandable to 𝑐 𝑑, use the equation from the definition. Substituting for
the query length 𝑐 𝑞 = 2 and the document length 𝑐 𝑑 = 6 to the formula we get
𝐶𝑅(𝑐 𝑞, 𝑐 𝑑) =
1 + |𝑐 𝑞|
1 + |𝑐 𝑑|
=
1 + 2
1 + 6
=
3
7
.
For b) we only change the query length 𝑐 𝑞 = 4 and obtain
𝐶𝑅(𝑐 𝑞, 𝑐 𝑑) =
1 + |𝑐 𝑞|
1 + |𝑐 𝑑|
=
1 + 4
1 + 6
=
5
7
.
3
Exercise 12/4
Count how many structural terms are present in the XML tree:
<Course>
<Title>Programming Abstractions</Title>
<Description>Abstraction and its relation to programming</Description>
<Instructors>
<Professor>
<First_Name>Eric</First_Name>
<Last_Name>Roberts</Last_Name>
</Professor>
</Instructors>
</Course>
To save space, mark each element with its first letter only (D stands for Description, P
for Professor, . . . ). By Definition 3, we count all combinations and write them into the
table:
C T Programming Abstractions C I P F Eric C I P L Roberts
T Programming Abstractions I P F Eric I P L Roberts
Programming Abstractions P F Eric P L Roberts
C D Abstraction . . . F Eric L Roberts
D Abstraction . . . Eric Roberts
Abstraction . . .
There are 16 structural terms in total.
4