9.2 n-ary Relations and their Applications

Question 1

n-ary Relations and its degree and its domains:

Answer 1

Let A1, A2, … , An be sets. An n-ary relation on these sets is a subset of A1 × A2 × ⋯ × An.
The sets A1, A2, … , An are called the domains of the relation, and n is called its degree.

Question 2

a ≡ b (mod m)

Answer 2

Integer a is congruent to integer b modulo m > 0, if a and b give the same remainder when divided by m.
The notation a ≡ b (mod m).

( Alternative defnition: a ≡ b (mod m)
= m|(b −a). idk)

Question 3

The time required to manipulate information in a database depends on?

Answer 3

The time required to manipulate information in a database depends on how this information is
stored.

Question 4

Fields:

Answer 4

entries of n-tuple.

Question 5

Records:

Answer 5

n tuples made up of fields.

Question 6

Database:

Answer 6

It consists of records.

Question 7

The relational data Model:

Answer 7

The relational
data model represents a database of records as an
n-ary relation.

Question 8

Relation used to represent databases:

describe it, what are attributes?

Answer 8

Tables.
Each column corresponds to an attribute of the database.

Attribute = Column Name

Question 9

Primary Key:

Answer 9

A domain of an n-ary relation is called a primary key when the value of the n-tuple from
this domain determines the n-tuple. That is, a domain is a primary key when no two n-tuples in
the relation have the same value from this domain.

Question 10

Intension and extension:

Answer 10

The more permanent part of a database, including the
name and attributes of the database is called its intension.

The foll collection of n-tuples in a relation
is called the extension of the relation.
(Ackermann, 231455, Computer Science, 3.88)
(Adams, 888323, Physics, 3.45)

Question 11

The property that a domain is a primary key is permanent?

Answer 11

Records are often added to or deleted from databases. Because of this, the property that a
domain is a primary key is time-dependent.

To make it permanent, it must serve as primary key to all possible extensions To do so, its required to analyze intentions to understand possible n tuple that can occur as extension.

Question 12

Composite Key:

Answer 12

Combinations of domains can also uniquely identify n-tuples in an n-ary relation. When
the values of a set of domains determine an n-tuple in a relation, the Cartesian product of these
domains is called a composite key

Question 13

Selection Operator:

Answer 13

Let R be an n-ary relation and C a condition that elements in R may satisfy. Then the selection
operator sC maps the n-ary relation R to the n-ary relation of all n-tuples from R that satisfy
the condition C.

Question 14

Projections:

Answer 14

Projections are used to form new n-ary relations by deleting the same fields in every record
of the relation.

The projection P i1 i2,…,im where i1 < i2 < ⋯ < im, maps the n-tuple (a1, a2, … , an) to the
m-tuple (ai1, ai2, … , aim ), where m ≤ n.

In other words, the projection P i1 ,i2,…,im DELETES
n − m of the components of an n-tuple, leaving
the i1th, i2th, … , and imth components

P1,3 (a1, a2, a3, a4) = ( a1, a3)

Projections are formed by omitting certain columns, and then eliminating duplicate
rows.

Question 15

Does the application of projection ever lead to fewer rows?

Answer 15

Fewer rows may result when a projection is applied to the table for a relation. This happens
when some of the n-tuples in the relation have identical values in each of the m components of
the projection, and only disagree in components deleted by the projection.

Question 16

The join Operator:

Answer 16

Let R be a relation of degree m and S a relation of degree n. The join Jp(R, S),
where p ≤ m and p ≤ n, is a relation of degree m + n − p that consists of all
(m + n − p)-tuples (a1, a2, … , am−p, c1, c2, … , cp, b1, b2, … , bn−p), where the m-tuple
(a1, a2, … , am−p, c1, c2, … , cp) belongs to R and the n-tuple (c1, c2, … , cp, b1, b2, … , bn−p)
belongs to S.

In other words, the join operator Jp produces a new relation from two relations by combining all
m-tuples of the first relation with all n-tuples of the second relation, where the last p components
of the m-tuples agree with the first p components of the n-tuples.

Joins are analogous to compositions of relations.

Question 17

SQL:

Answer 17

Structured Query Language

Question 18

Queries in SQL:

Answer 18

SQL uses the FROM clause to identify the n-ary relation the query is applied to, the
WHERE clause to specify the condition of the selection operation, and the SELECT clause to
specify the projection operation that is to be applied. (Beware: SQL uses SELECT to represent
a projection, rather than a selection operation. This is an unfortunate example of conflicting
terminology.)
SELECT Departure_time, Destination
FROM Flights, Table 2
WHERE Destination=’Detroit’

From table1, table2
to perform join operation.

Question 19

Data Mining:

Answer 19

The discipline with the goal to get useful information from the data.

Question 20

By a transaction what do you mean?

Answer 20

By a transaction we mean a set of items bought by a customer during a visit to the store,
such as {milk, eggs, bread} or {orange juice, bananas, yogurt, cream}.
Store collects large databases of transactions.

Question 21

Item:

Answer 21

Each product in the store is called an item.

Question 22

ItemSet:

k-itemset:

Answer 22

Collection of itemset.

A k-itemset is an itemset that contains exactly k items.

Question 23

Transaction and basket:

Answer 23

The terms transaction and basket are

used synonymously with the word itemset.

Question 24

What forms a database of transactions:

and how is a transaction represented?

Answer 24

When a store has n items, a1, a2, … , an, for sale,
each transaction can be represented by an n-tuple b1, b2, … , bn, where bi is a binary variable
that tells us whether ai occurs in this transaction. That is, bi = 1 if ai is in this transaction and
bi = 0 otherwise. (Note that we only care whether an item occurs in a transaction and not how
many times it occurs.) We can represent a transaction by an (n + 1)-tuple of the form (transaction number, b1, b2, … , bn). The collection of all these (n + 1)-tuples forms a database of
transactions

Question 25

Support of Itemset:

Answer 25

The count of an itemset I, denoted by 𝜎(I), in a set of transactions T = {t1, t2, … , tk}, where
k is a positive integer, is the number of transactions that contain this itemset. That is,
𝜎(I) = |{ti ∈ T | I ⊆ ti
}|.
The support of an itemset I is the probability that I is included in a randomly selected transaction from T. That is,
support(I) = 𝜎(I)/|T|
.

Question 26

Frequent itemset mining:

Answer 26

The support threshold sis specified for a particular application. Frequent itemset mining
is the process of finding itemsets I with support greater than or equal to s. Such itemsets are
said to be frequent.

Question 27

Association Rule:

Answer 27

If S is a set of items and T is
a set of transactions, an association rule is an implication of the form I → J, where I and J are
disjoint subsets of S.
[ Not analogous to logic]

The strength of an association rule
is measured in terms of its support, the frequency of transactions that contain both I and J,
and
its confidence, the frequency of transactions that contain J when they also contain I. (conditional probability)

If I and J are subsets of a set T of transactions, then
support(I → J) = 𝜎(I ∪ J)/|T|
and
confidence(I → J) = 𝜎(I ∪ J)/𝜎(I)

Check example 15, I U J doesn’t mean I or J, it means operation on Set I and J, union of elements of set I and J.
𝜎({cider, donuts}∪{apples}) = 𝜎({cider, donuts, apples})

Question 28

What does support of association rule tell us:

when its high and when its low.

Answer 28

The support of the association rule I → J, the fraction of transactions that contain both I and J,
is a useful measure because a low support value tells us that the basket containing all items in
I and all items in J is seldom purchased, whereas a high value tells us that they are purchased
together in a large fraction of transactions.

Question 29

What does confidence tell?

Answer 29

The larger the confidence of I → J, the more likely it is for J to
be a subset of a transaction that contains I.

Question 30

Application of Association Rules:

Answer 30

Although we have presented association rules in the context of market baskets, they are
useful in a surprisingly wide variety of applications. For instance, association rules can be used
to improve medical diagnoses, in which itemsets are collections of test results or symptoms and
transactions are the collections of test results and symptoms found on patient records. Association rules, in which itemsets are baskets of key words and transactions are the collections of
words on web pages, are used by search engines. Cases of plagiarism can be found using association rules, in which itemsets are collections of sentences and transactions are the contents
of documents. Association rules also play helpful roles in various aspects of computer security,
including intrusion detection, in which the itemsets are collections of patterns and transactions
are the strings transmitted during network attacks. The interested reader will be able to find
many more such applications by searching the web.

Question 31

Selection operator properties ish..

4

Answer 31

s C1∧C2 (R)=s C1 (s C2(R))
sC1(sC2(R)) = sC2(sC1(R))
sC(R ∩ S) = sC(R) ∩ sC(S)
sC(R − S) = sC(R) − sC(S)

Question 32

Projection properties:

Answer 32

Pi1,i2,…,im (R ∪ S) = Pi1,i2,…,im (R) ∪ Pi1,i2,…,im (S).

Pi1,i2,…,im (R ∩ S) may be different from
Pi1,i2,…,im (R) ∩ Pi1,i2,…,im (S)

Pi1,i2,…,im (R − S) may be different from
Pi1,i2,…,im (R) − Pi1,i2,…,im (S).

Question 33

Suppose that I is an itemset with positive count in a set of
transactions. Find the confidence of the association rule
I → ∅.

Answer 33

1

Question 34

The lift of the association rule I → J, where I and J are

itemsets with positive support in a set of transactions:

Answer 34

The lift of the association rule I → J, where I and J are
itemsets with positive support in a set of transactions,
equals support(I ∪ J)/(support(I)support(J)).