8¡§¦'C¡edgf¢DHCI PQ¡§%GD¤rts

§

‡‘ie

ƒfˆŸvƒ

Ñ«×tb

yCˆqy¢Èك˜

ê

§

ñ

ˆqƒ

ñ

ê

§

qy‚ÉE

‡

ˆ

‡de



Ô9å‹e

È

c

v(ˆ~r

e

ƒ

Ñ

ƒ

e

ƒ’ˆ‰ƒ

et‡

v

b‘c’e

˜u

c

˜y@v

c’eXÏ

yvCƒ

Ñ«×tb

yˆqy@Èكf

ê

§

ñ

ˆqƒ

ñ

ê

§

qy‚ÉE

‡

ˆ

‡de



Ô

è

y±yÓ

pt‡dÏt‡

ˆ

y

Ò

y‚v(ˆ

‡¬Ê

y

Õ! 

qy‚ÉE

‡

ˆ

‡de



i

ƒfÈ

ê

§

ÆsutyC

‡

y

i‡de

ˆ‰yC

Ñ¢i

ƒfÈ

ê

§

ʀ‡

y‚É

i

rۃ

p

y

e

y

Ê

yC@ˆ

p

y

Ês‡

yCÉ

i

…

yˆ‰yC

Ñe‡de

yžˆ

p

yÆsutyC‰Ð

‡¬e

ˆ

p

yXu

e

‰y

i

ˆq

‡

vˆqy

…

v

cfi

y

Ô

0

yCÈكf‰y

i

ˆ

c

ˆ

‡¬e

Çˆ

p

y

Ñ¢c’‡de

qy

i

u

b

ˆŸƒfȧˆ

p

y

i

y~v(ˆ

‡

ƒ

e

r¥É¤y›‰y‚v

cfb¬b¤c

ˆqy

i

ˆŸÈكfev

p

y‚v



‡de



É

p

yˆ

p

yC

cªê

§

ƘuwyC‰Ð

pwcfiXcÇê

§

qy‚ÉE

‡

ˆ

‡de



‡de

ˆ‰yC

Ñ¢i

ƒ’È

c



‡¬Ê

y

e

i

yCˆXƒ’È

ê

§

ʀ‡

y‚É

iCÔ

Å

p

yžˆqy

i

ˆ

‡‘i§Ïwcfi

y

…

ƒ

e

ˆ

p

yv

pwcfi

y

Ô

s9yˆ

σ

Ï

y

cX…tc

ˆ

c’ϯcfi

y

i

v

p

y

Ñ¢c cfew…

Q(¯

x)

cê

§

ƒ

Ê

yC

σ

É

‡

ˆ

p

Èِ‰yCy

ʕc



‡‘c’Ïtb

y

i

¯

x

Ô

Å

p

y

#

Þ

î%$

ÜCá



î

Ûc

î

#

Q

r

…

y

e

ƒ’ˆqy

…

[Q]

r

‡di

ˆ

p

y

‡dewi

ˆ

c’e

vCyXƒ

Ê

y‚

σ

i

uwv

p

ˆ

pwc

ˆ

(x

1

, . . . , x

k

) ∈ R

‡uÒ

R(x

1

, . . . , x

k

)

‡‘iXc’e`c

ˆqƒ

Ñ¢‡¬e

Q

Ô9Õ

ƒ˜

cIi

yˆXÌëƒfÈ

ê

§

i

r

[V]

‡di

ˆ

p

y¢u

et‡

ƒ

e

ƒ’ȱˆ

p

y

[Q]



i

Èك˜

c’bdb

Q ∈ V

ÔwÕ

ƒf

ceÑ¢c’×t×w‡¬e



α

Èِ‰ƒ

Ñ

ʒc



‡‘c’Ïwb

y

i

ˆqƒ

ʕc



‡dcfÏtb

y

i§c’ew…

vƒ

ewi

ˆ

c’e

ˆ

i

r

ɱy

…

y

e

ƒ’ˆqy

Ï

Ð

α([Q])

ˆ

p

y

‡dewi

ˆ

cfe

vy ƒ

Ï

ˆ

c’‡de

y

…™Ï

Ð

c’×t×tb

Ð

‡¬e



α

ˆ‰ƒ

cfb¬bƒÊ•c



‡dcfÏtb

y

i±‡¬e

[Q]

Ô

¢

y‚v

c’bdb

ˆ

p¯c

ˆ

c

ˆqu

×wb

y

¯

c

‡di±‡¬e

Q(D)

‡uÒ

ˆ

p

yC‰y—yÓ

‡‘i

ˆ

i±cXp

ƒ

Ñ

ƒ

Ñ

ƒf

×tpt‡‘iqÑ

h

¯

c

Èِ‰ƒ

Ñ

[Q]

ˆqƒ

D

i

uwv

p

ˆ

pwc

ˆ

h

¯

c

(¯

x) = ¯

c

Ôyå‹e

ˆ

pt‡‘i

v

cfi

y«É±y

i‰c

Ð¥ˆ

pwc

ˆ

h

¯

c

ç©à¨ÝnáƒÜ(âjâCÜâ

¯

c ∈ Q(D)

r9ƒf

ˆ

pwc

ˆ

¯

c ∈ Q(D)

ʀ‡‘c

h

¯

c

Ô

s9yˆ›Ì

Ï

y

cºê

§

ʀ‡

y‚É

Èِ‰ƒ

Ñ

I(σ)

ˆ‰ƒ

I(σ

V

)

Ô

sHyˆ

S

Ï

y

cօwc

ˆ

cfÏwcfi

y

‡¬e¯i

ˆ

c’e

vCy

ƒ

Ê

yC

I(σ

V

)

cfew…

C

c›i

yCˆ7ƒ’È©y

b

y

Ñ

y

e

ˆ

i‚Ô

è

y

…

y„

e

yˆ

p

yÌ

ñ

‡desÊ

yC

i

yXƒfÈ

S

qy

bdc

ˆ

‡dÊ

y ˆqƒ

c

…

ƒ

Ñ¢c’‡de

C

r

…

y

e

ƒ’ˆqy

…

V

−1

C

(S)

r

c˜i

ˆ

p

y

‡dewi

ˆ

c’e

vy

D

ƒ

Ê

yC

σ

…

y„

e

y

…Tcfi

Èك

b¬b

ƒ•É

i‚Ô

s9yˆ

V

Ï

y

c

‰y

b‘c

ˆ

‡

ƒ

eX‡¬e

σ

V

r’É

‡

ˆ

p

vCƒf‰qy

i·×

ƒ

e¯…w‡¬e

7ÆsutyC‰Ð

Q

V

(¯

x)

ԒÕ

ƒ˜¥y

Ê

y‚qÐhˆqu

×wb

y

¯

c

Ï

y

b

ƒ

e



‡¬e



ˆqƒ

V

‡de

S

r€É¤y

‡de

v

b

u

…

y

‡¬e

D

ˆ

p

y7ˆ‰u

×tb

y

i

ƒ’È

α

¯

c

([Q

V

])

É

p

yC‰y

α

¯

c

(¯

x) = ¯

c

cfew…

α

¯

c

Ñ¢c’×wi

y

Ê

y‚qÐ

ʕc



‡dcfÏtb

yƒ’È

[Q

V

]

e

ƒ’ˆ

‡de

¯

x

ˆqƒ

i

ƒ

Ñ

y

e

yCÉ

…t‡di

ˆ

‡de

v(ˆ

ʕc’b

uty

e

ƒ’ˆ

‡¬e

dom(S) ∪ C

Ô

Å

p

u

i

r

V

−1

C

(S)

‡‘i

ƒ

Ï

ˆ

cf‡¬e

y

…

cfi›cÎí'&

Y•âÜ

ƒ’È

S

‡¬e

É

pw‡

v

pËc’bdb—Ê•c’b

uty

i¢‡¬e

ˆ‰qƒ

…

uwvCy

…

cfi

É

‡

ˆ

e

y

i‰i

y

i¢c

‰yTƒfuwˆ

i·‡‘…

y

dom(S)

c’ew…

C

Ô

Å

ƒ

i·‡dÑ«×tb¬‡

ÈÙÐfr±É±yTu

i

u

cfb¬b

Ð

cfi‰i

u

Ñ

yTˆ

pwc

ˆ

C

vƒ

e¯i·‡‘i

ˆ

i

ƒ’È—ˆ

p

y¥y

e

ˆ

‡

‰y

…

ƒ

Ñ¢c’‡de

ƒ’Èhˆ

p

y

‡dewi

ˆ

c’e

vyÉ

p

y

e

V

−1

‡di¢cf×t×tbd‡

y

…

r

c’ew…

ƒ

Ñ«‡

ˆ

i·×

y‚v

‡

ÈÙÐ

‡de



‡

ˆ—yCÓ

×wb¬‡

v

‡

ˆ

b

Ð

Ô

Å

p

u

i

r

c’bdb

É

‡

ˆ

e

y

i‰i

y

i§‡de

ˆ‰qƒ

…

u¯vy

…IÏ

Ð

c’eTc’×w×tb¬‡

v

c

ˆ

‡

ƒ

e

ƒ’È

V

−1

c

‰y

e

yCÉ

y

b

y

Ñ

y

e

ˆ

i‚Ô

Å

p

y Èك

bdb

ƒ•É

‡de

pfy‚ТÈ

c

vˆ

iEc

‰yžƒ

Ïwi

yC

Ê

y

…¢‡de



U©'c’ew…

tb¦

Ú

('FID0)

D21

¥78

¥

D

£30465

ÜÝ

Q(¯

x)



Ü%Y87@9

Y•áƒÛ

S = V([Q])

A

5

ÜÝ

Q

V

(¯

x)



ÜÝ

&

ÜB7@9

î

h•ÜCÞ

σ

V

#

î

ÞXç

&

à

í'&

[Q

V

] = S

A©C«Ü

&

Y©h•ÜÝ

&

Ü

#

î

ð¨ð

î

ç©à¨áfeED

F

à

G

Q

V

◦ V

à‘âÜ

`b$

àihIY’ð¬Üá¯Ý±Ý

î

Ý

&

ÜH7@94ç

&wî

âCÜ

#

Þ

î%$

ÜCá



î

Û©c›à‘â

V

−1

(S)

I

F

à¨à

G

Q ⊆ Q

V

◦ V

I

F

à¨à¨à

GQP

#

¯

x ∈ Q(V

−1

(S))

Ý

&

ÜCá

Q = Q

V

◦ V

A Pá«ïGY•Þ(Ý´à

í

$

ðY’Þ'R

V

Q

A

F

àihSGTP

#

Q

&

Y’â%YU7@9VÞqÜCç©Þ(à¨Ýnà¨á¢e›à¨á`ÝqÜCÞ(߁â

î

#

Ì

R@Ý

&

ÜCá

Q

V

à‘âžâ

$

í'&

Y¢Þ‰Üç©Þ(à¨Ý´à¨áfeEA

g

ƒ’ˆ‰yEˆ

p¯c

ˆ

§

qƒ

×

ƒ

i·‡

ˆ

‡

ƒ

e

7cf×t×tbd‡

y

i@Ï

ƒ’ˆ

p

ˆqƒXˆ

p

y—„

ew‡

ˆ‰y

c’ew…

u

e

‰y

i

ˆq

‡

vˆqy

…

v

cfi

y

i‚Ô

è

y

v

c’ee

ƒ•É

i·p

ƒ•É

ˆ

p

yžÈك

b¬b

ƒ•É

‡de



Ô

V6W

3¢D

F©3

$X304

7@9

à‘âXá

î

Ý

íjî

ߗïƒð¬Ü݋Ü

#

î

ÞY7@9@`‹Ý

î

`a7@9

މÜç©Þ(à¨Ý´à¨áfeEA

ø

p

v

m

—‚|‹˜wš¢¡9vw•’gji~k‚‰¤£€™wš¦¥hv¤¥¤fu—‚™’‰

 

Þ

î~î

#

A

è

yeyÓ

pt‡dÏt‡

ˆ

cIi

yCˆ ƒfÈ

ê

§

ʀ‡

yCÉ

i

Ì

cfew…Çc¥ê

§

Q

i

uwv

p

ˆ

p¯c

ˆ

V

Q

Ï

uwˆ

¯

x ∈

Q(V

−1

(S))

rۃ

p

yC‰y

S = V([Q])

Ô)0

Ð

§

‰ƒ

×

ƒ

iq‡

ˆ

‡

ƒ

e

r˜ˆ

pw‡diEiqp

ƒ•É

i

ˆ

pwc

ˆ

Q

p¯cfi¤e

ƒ

ê

§

qy‚ÉE

‡

ˆ

‡de



‡¬e

ˆqy‚

Ñ¢i

ƒfÈ¥Ì

Ô

s9yˆ7ˆ

p

y

…tc

ˆ

c’Ïwc˜i

y

i

v

p

y

Ñ¢c

vCƒ

ewiq‡di

ˆ7ƒfÈ

c™i·‡de



b

y

Ït‡dewc

qАqy

bdc

ˆ

‡

ƒ

e

R

ԃê

ƒ

ewi·‡‘…

y‚—ˆ

p

y

i

yCˆ¤ÌQvƒ

ewiq‡di

ˆ

‡de

ƒfÈHˆ

p

y7Èك

b¬b

ƒ•É

‡de

ˆ

p

‰yCy

Ês‡

yCÉ

i

ã

É

‡

ˆ

p

vCƒf‰qy

i·×

ƒ

ew…t‡¬e

f

c’×tpt‡

v

cfb

‰y

×

ñ

qy

i

y

e

ˆ

c

ˆ

‡

ƒ

ewi

ä

Ú

V

1

(x, y) = ∃α∃β[R(α, x) ∧ R(α, β) ∧ R(β, y)]

x ← α → β → y

V

2

(x, y) = ∃α[R(x, α) ∧ R(α, y)]

x → α → y

V

3

(x, y) = ∃α∃β[R(x, α) ∧ R(α, β) ∧ R(β, y)]

x → α → β → y

s9yˆ

Q(x, y) = ∃a∃b∃c[R(a, x) ∧ R(a, b) ∧ R(b, c) ∧ R(c, y)]

Ô

è

yž„w

i

ˆ

iqp

ƒ•É

ˆ

pwc

ˆ

V

Q

Ô

Å

ƒ

…

ƒ

i

ƒwrwɤy

×

‰ƒ

Ê

yhˆ

pwc

ˆEˆ

p

yžÈك˜

Ñ

u

bdc

ϕ(x, y) : ∃d[V

1

(x, d) ∧ ∀e(V

2

(e, d) → V

3

(e, y)]

‡diec

‰yCÉE

‡

ˆ

‡¬e

Çƒ’È

Q

u

iq‡¬e

`Ì

Ô'å‹e

ƒ’ˆ

p

yCŸÉ±ƒ˜

…wi

ryÈك˜y

c

v

p–…tc

ˆ

c’ϯcfi

y

D

ƒ

Ê

y‚

σ

c’e¯…

u, v ∈ dom(D)

r

u, v ∈ Q(D)

‡uÒ

ϕ(u, v)

p

ƒ

bd…ti

ƒ

e

ˆ

p

y

‡dewi

ˆ

c’e

vCy

V (D)

Ô

x€u

×t×

ƒ

i

y

u, v ∈ Q(D)

Ês‡‘cØcºp

ƒ

Ñ

ƒ

Ñ

ƒf

×tpt‡‘i·Ñ

h

ÔEg

ƒfˆqyֈ

pwc

ˆ¥É±y

c’b‘i

ƒ

pwc’Ê

y

x, c ∈ V

1

([Q])

r

ʀ‡dchcEp

ƒ

Ñ

ƒ

Ñ

ƒ˜

×wpt‡diqÑ

h

Ô~å

ˆ¥Èك

b¬b

ƒ•É

i

ˆ

pwc

ˆ

h◦h

‡di'c—p

ƒ

Ñ

ƒ

Ñ

ƒf

×tpt‡‘i·Ñ

Èِqƒ

Ñ

[V

1

]

ˆqƒ

D

Ñ¢cf×t×t‡de



x, c

ˆ‰ƒ

u, h(c)

Ô

è

y

b

yCˆ

d = h(c)

cfew…

Èِ‰ƒ

Ñ

ˆ

p

y

c’Ï

ƒ

Ê

y@ɤy

pwc’Ê

y

u, d ∈ V

1

(D)

Ôwg

ƒ•É

Ï

y~v

c

u

i

yhˆ

p

y‚qy

‡‘iEc’e

y

…

˜y

c, y

‡¬e

[Q]

ɱy

pwc’Ê

y

cfe

y

…

fy

h(c), v

‡¬e

D

Ô

Å

p

yC‰yÈك˜qy«Èك˜y

Ê

yC‰Ð

e

i

uwv

p

ˆ

p¯c

ˆ

e, d ∈ V

2

(D)

r

e, v ∈ V

3

(D)

Ô

Å

p

u

i

r

ϕ(u, v)

p

ƒ

b‘…ti

ƒ

e

V (D)

Ô¯ê

ƒ

e€Ê

yC

i

y

b

Иr

i

u

×t×

ƒ

i

y

ϕ(u, v)

p

ƒ

bd…ti

ƒ

e

V (D)

Ô

Å

p

y

e

ˆ

p

y‚qy¢yCÓ

‡‘i

ˆ

i

d

i

uwv

p

ˆ

p¯c

ˆ

u, d ∈ V

1

(D)

r

i

ƒ

Ï

Ð

…

y„

ew‡

ˆ

‡

ƒ

e

ƒ’È

V

1

ˆ

p

y‚qy¢yCÓ

‡‘i

ˆ

α, β

i

uwv

p

ˆ

pwc

ˆ

R(α, u) ∧ R(α, β) ∧ R(β, d)

p

ƒ

bd…ti‡¬e

D

Ô(0

uwˆˆ

p

y

e

α, d ∈ V

2

(D)

i

ƒ

Ï

Ð

…

y„

ew‡

ˆ

‡

ƒ

e

ƒfÈ

ϕ

r

α, v ∈ V

3

(D)

Ôå

ˆ¢Èك

b¬b

ƒ•É

i

ˆ

pwc

ˆ¢ˆ

p

y‚qyTyÓ

‡‘i

ˆ

b , c

i

uwv

p

ˆ

pwc

ˆ

R(α, b ) ∧ R(b , c ) ∧ R(c , v)

p

ƒ

bd…wi@‡de

D

Ô

Å

pt‡di

ˆqƒ˜fyˆ

p

yC±É

‡

ˆ

p

ˆ

p

y—È

c

vˆˆ

pwc

ˆ

R(α, u)

p

ƒ

b‘…tih‡¬e

D

r

‡dÑ«×tbd‡

y

i

ˆ

pwc

ˆ

u, v ∈ Q(D)

Ô

Å

p

u

i

r

ϕ(x, y)

‡di c

‰yCÉE

‡

ˆ

‡¬e

›ƒ’È

Q

u

iq‡de



ÌÇr

i

ƒ

V

Q

Ô

å‹e›Ê€‡

y‚É΃’È

§

‰ƒ

×

ƒ

iq‡

ˆ

‡

ƒ

e

r

‡

ˆ§qy

Ñ«cf‡¬e¯i

ˆqƒ

iqp

ƒ•É

ˆ

pwc

ˆ

x, y ∈ Q(V

−1

(S))

rwÉ

p

yC‰y

S = V([Q])

Ôyê±b

y

c



b

Иr

S = V([Q])

‡‘i

ˆ

p

y

‡dewi

ˆ

cfe

vy˜Ú

V

1

x c

b c

c y

V

2

a c

b y

V

3

a y

c’ew…

V

−1

(S)

‡diE…

y

×t‡

v(ˆ‰y

…‡¬e¥Õ'‡

fut‰y

fÔ

å

ˆ

‡‘i

y

cfiq‡¬b

Фv

p

y‚v

˜y

…

ˆ

pwc

ˆ

x, y

…

ƒsy

ie

ƒ’ˆ

Ï

y

b

ƒ

e

ªˆ‰ƒ

Q

cf×t×tbd‡

y

…

ˆ‰ƒªˆ

p

y

cfÏ

ƒ

Ê

y

‡¬ewi

ˆ

cfe

vy

Ô

Å

p

u

i

r

Q

pwc˜i§e

ƒ

ê

§

‰yCÉE

‡

ˆ

‡¬e



‡de

ˆqyC

Ñ¢i

ƒ’ÈWÌ

Ô

2

¡

ÜCßpY’Þ£¢¥¤

A

g

ƒfˆqyeˆ

p¯c

ˆ

Å

p

yCƒ˜qy

Ñ

Ÿp

ƒ

bd…wih‡de

ˆ

p

ye„

et‡

ˆqy

cfi

ɤy

bdb©cfi

ˆ

p

y«u

e

qy

i

ˆ‰

‡

v(ˆ‰y

…

v

cfi

y

Ô

Å

pw‡di@iqp

ƒ•É

i

ˆ

pwc

ˆ

Å

p

yCƒf‰y

Ñ

tÔ

h‡de



rfv

b‘c’‡dÑ«‡¬e

hˆ

pwc

ˆ

ê

§

‡‘i

vƒ

Ñe×wb

yCˆqy§Èكf

ê

§

ñ

ˆqƒ

ñ

ê

§

‰yCÉE

‡

ˆ

‡de



‡¬e

ˆ

p

y—u

e

‰y

i

ˆq

‡

v(ˆqy

…

v

cfi

yfr

‡‘i

y‚q‰ƒ

e

y‚ƒfu

i‚Ô•a—b‘i

ƒ¯r

Å

p

y‚ƒf‰y

Ñ

w𤋮

rfv

b‘c’‡dÑ

ñ

‡¬e



…

y~v

‡‘…tc’Ït‡dbd‡

ˆ{Ð¥ƒfÈ

…

yˆ‰yC

Ñ«‡¬ewc

vÐ

‡de

ˆ

p

yeu

e

qy

i

ˆ‰

‡

v(ˆ‰y

…

v

cfi

y

c˜i c

vƒ˜qƒ

b¬b‘c

‰Ðfr¯qy

Ñ«cf‡¬e¯i

u

et×

‰ƒ

Ê

y

e9Ô

Å

p

y

i

ƒfutjvyžƒfÈ¥ˆ

p

y

×

‰ƒ

Ïtb

y

Ñ

‡di