# Untitled

By: a guest on Jun 9th, 2012  |  syntax: None  |  size: 8.58 KB  |  hits: 25  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. -- Given a relation R1, with three attributes X, Y and Z, each with a
2. -- 'number'-domain. R1 represents different points in the 3-dimensional
3. -- Euclidean space. Express in SQL a query that gives the Convex Hull of
4. -- the points of R1. Each point of the Convex Hull must be
5. -- non-redundant.
6. SELECT *
7. FROM R1 E1
8. WHERE
9. ---------------------
10. -- Case of 1 point --
11. --v10----------------
12. (
13. ( SELECT COUNT(*)
14. FROM R1
15. )
16. = 1
17. )
18. --^10--
19. OR
20. --------------------
21. -- Case of 1 line --
22. --v20---------------
23. (
24. --v21-- Not one point
25. (
26. ( SELECT COUNT(*)
27. FROM R1
28. )
29. <> 1
30. )
31. --^21--
32. AND
33. --v22-- All points on one line
34. (
35. NOT EXISTS
36. ( SELECT *
37. FROM R1 E2, R1 E3
38. WHERE
39. ------- E1,E2,E3 are not on one line
40. (
41. (
42. ------- Projection on X,Y not on one line
43. (((E1.X-E3.X)*(E2.Y-E3.Y))-((E2.X-E3.X)*(E1.Y-E3.Y))) <> 0
44. )
45. OR
46. (
47. ------- Projection on X,Z not on one line
48. (((E1.X-E3.X)*(E2.Z-E3.Z))-((E2.X-E3.X)*(E1.Z-E3.Z))) <> 0
49. )
50. OR
51. (
52. ------- Projection on Y,Z not on one line
53. (((E1.Y-E3.Y)*(E2.Z-E3.Z))-((E2.Y-E3.Y)*(E1.Z-E3.Z))) <> 0
54. )
55. )
56. )
57. )
58. --^22--
59. AND
60. --v23-- All points on the same side of E1
61. (
62. NOT EXISTS
63. ( SELECT *
64. FROM R1 E2, R1 E3
65. WHERE
66. ------- E2 and E3 are on a different side of E1
67. ((E1.X-E2.X)*(E1.X-E3.X) < 0)
68. OR
69. ((E1.Y-E2.Y)*(E1.Y-E3.Y) < 0)
70. OR
71. ((E1.Z-E2.Z)*(E1.Z-E3.Z) < 0)
72. )
73. )
74. --^23--
75. )
76. --^20--
77. OR
78. ---------------------
79. -- Case of 1 plane --
80. --v30----------------
81. (
82. --v31-- Not one point
83. (
84. ( SELECT COUNT(*)
85. FROM R1
86. )
87. <> 1
88. )
89. --^31--
90. AND
91. --v32-- Not all points on one line
92. (
93. EXISTS
94. ( SELECT *
95. FROM R1 E2, R1 E3
96. WHERE
97. ------- E1,E2,E3 are not on one line
98. (
99. (
100. ------- Projection on X,Y not on one line
101. (((E1.X-E3.X)*(E2.Y-E3.Y))-((E2.X-E3.X)*(E1.Y-E3.Y))) <> 0
102. )
103. OR
104. (
105. ------- Projection on X,Z not on one line
106. (((E1.X-E3.X)*(E2.Z-E3.Z))-((E2.X-E3.X)*(E1.Z-E3.Z))) <> 0
107. )
108. OR
109. (
110. ------- Projection on Y,Z not on one line
111. (((E1.Y-E3.Y)*(E2.Z-E3.Z))-((E2.Y-E3.Y)*(E1.Z-E3.Z))) <> 0
112. )
113. )
114. )
115. )
116. --^32--
117. AND
118. --v33-- All points in one plane
119. (
120. NOT EXISTS
121. ( SELECT *
122. FROM R1 E2, R1 E3, R1 E4
123. WHERE
124. ------- E1,E2,E3,E4 are not in one plane
125. (
126. (E2.X-E1.X)*((E3.Y-E1.Y)*(E4.Z-E1.Z)-
127. (E4.Y-E1.Y)*(E3.Z-E1.Z))
128. -
129. (E2.Y-E1.Y)*((E3.X-E1.X)*(E4.Z-E1.Z)-
130. (E3.Z-E1.Z)*(E4.X-E1.X))
131. +
132. (E2.Z-E1.Z)*((E3.X-E1.X)*(E4.Y-E1.Y)-
133. (E3.Y-E1.Y)*(E4.X-E1.X)) <> 0
134. )
135. )
136. )
137. --^33--
138. AND
139. --v34--
140. (
141. ------- there exist two points P1,P2 with:
142. ------- E1,P1,P2 are pairwise different
143. ------- all points lie on the same side of the line E1,P1
144. ------- all points lie on the same side of the line E1,P2
145. ------- E1,P1,P2 are not on one line
146. EXISTS
147. (
148. SELECT *
149. FROM R1 P1,R1 P2
150. WHERE
151. ------- P1,P2 different
152. ((P1.X<>P2.X) OR (P1.Y<>P2.Y) OR (P1.Z<>P2.Z))
153. AND
154. ------- E1,P1 different
155. ((E1.X<>P1.X) OR (E1.Y<>P1.Y) OR (E1.Z<>P1.Z))
156. AND
157. ------- E1,P2 different
158. ((E1.X<>P2.X) OR (E1.Y<>P2.Y) OR (E1.Z<>P2.Z))
159. AND
160. NOT EXISTS
161. (
162. SELECT *
163. FROM R1 Q1,R1 Q2
164. WHERE
165. ------- Q1,Q2 on a different side of the line E1,P1
166. ( ((E1.X-Q1.X)*(P1.Y-Q1.Y)-(P1.X-Q1.X)*(E1.Y-Q1.Y))*
167. ((E1.X-Q2.X)*(P1.Y-Q2.Y)-(P1.X-Q2.X)*(E1.Y-Q2.Y)) < 0
168. OR
169. ((E1.X-Q1.X)*(P1.Z-Q1.Z)-(P1.X-Q1.X)*(E1.Z-Q1.Z))*
170. ((E1.X-Q2.X)*(P1.Z-Q2.Z)-(P1.X-Q2.X)*(E1.Z-Q2.Z)) < 0
171. OR
172. ((E1.Y-Q1.Y)*(P1.Z-Q1.Z)-(P1.Y-Q1.Y)*(E1.Z-Q1.Z))*
173. ((E1.Y-Q2.Y)*(P1.Z-Q2.Z)-(P1.Y-Q2.Y)*(E1.Z-Q2.Z)) < 0
174. )
175. )
176. AND
177. NOT EXISTS
178. (
179. SELECT *
180. FROM R1 Q1,R1 Q2
181. WHERE
182. ------- Q1,Q2 on a different side of the line E1,P2
183. ( ((E1.X-Q1.X)*(P2.Y-Q1.Y)-(P2.X-Q1.X)*(E1.Y-Q1.Y))*
184. ((E1.X-Q2.X)*(P2.Y-Q2.Y)-(P2.X-Q2.X)*(E1.Y-Q2.Y)) < 0
185. OR
186. ((E1.X-Q1.X)*(P2.Z-Q1.Z)-(P2.X-Q1.X)*(E1.Z-Q1.Z))*
187. ((E1.X-Q2.X)*(P2.Z-Q2.Z)-(P2.X-Q2.X)*(E1.Z-Q2.Z)) < 0
188. OR
189. ((E1.Y-Q1.Y)*(P2.Z-Q1.Z)-(P2.Y-Q1.Y)*(E1.Z-Q1.Z))*
190. ((E1.Y-Q2.Y)*(P2.Z-Q2.Z)-(P2.Y-Q2.Y)*(E1.Z-Q2.Z)) < 0
191. )
192. )
193. AND
194. --v35-- E1,P1,P2 not on a line
195. (
196. (
197. (((E1.X-P2.X)*(P1.Y-P2.Y))-((P1.X-P2.X)*(E1.Y-P2.Y))) <> 0
198. )
199. OR
200. (
201. (((E1.X-P2.X)*(P1.Z-P2.Z))-((P1.X-P2.X)*(E1.Z-P2.Z))) <> 0
202. )
203. OR
204. (
205. (((E1.Y-P2.Y)*(P1.Z-P2.Z))-((P1.Y-P2.Y)*(E1.Z-P2.Z))) <> 0
206. )
207. )
208. --^35--
209. )
210. )
211. --^34--
212. )
213. --^30--
214. OR
215. ------------------
216. -- General case --
217. --v40-------------
218. (
219. --v41-- Not one point
220. (
221. ( SELECT COUNT(*)
222. FROM R1
223. )
224. <> 1
225. )
226. --^41--
227. AND
228. --v42-- Not all points on one line
229. (
230. EXISTS
231. ( SELECT *
232. FROM R1 E2, R1 E3
233. WHERE
234. ------- E1,E2,E3 are not on one line
235. (
236. (
237. ------- Projection on X,Y not on one line
238. (((E1.X-E3.X)*(E2.Y-E3.Y))-((E2.X-E3.X)*(E1.Y-E3.Y))) <> 0
239. )
240. OR
241. (
242. ------- Projection on X,Z not on one line
243. (((E1.X-E3.X)*(E2.Z-E3.Z))-((E2.X-E3.X)*(E1.Z-E3.Z))) <> 0
244. )
245. OR
246. (
247. ------- Projection on Y,Z not on one line
248. (((E1.Y-E3.Y)*(E2.Z-E3.Z))-((E2.Y-E3.Y)*(E1.Z-E3.Z))) <> 0
249. )
250. )
251. )
252. )
253. --^42--
254. AND
255. --v43-- Not all points in one plane
256. (
257. EXISTS
258. ( SELECT *
259. FROM R1 E2, R1 E3, R1 E4
260. WHERE
261. (
262. (E2.X-E1.X)*((E3.Y-E1.Y)*(E4.Z-E1.Z)-
263. (E4.Y-E1.Y)*(E3.Z-E1.Z))
264. -
265. (E2.Y-E1.Y)*((E3.X-E1.X)*(E4.Z-E1.Z)-
266. (E3.Z-E1.Z)*(E4.X-E1.X))
267. +
268. (E2.Z-E1.Z)*((E3.X-E1.X)*(E4.Y-E1.Y)-
269. (E3.Y-E1.Y)*(E4.X-E1.X)) <> 0
270. )
271. )
272. )
273. --^43--
274. AND
275. ( EXISTS
276. ( SELECT *
277. ------- select a point E2 different from E1 such that no point P is
278. --v44-- on 1 line with E1 and E2 and outside [E1,E2]
279. FROM R1 E2
280. WHERE
281. ------- E2 different from E1
282. ( (E1.X<>E2.X) OR (E1.Y<>E2.Y) OR (E1.Z<>E2.Z) )
283. AND
284. --v45-- no point P that is on 1 line with E1 and E2 is outside [E1,E2]
285. ( NOT EXISTS
286. ( SELECT *
287. FROM R1 P
288. WHERE
289. (
290. (
291. ------- E1,E2,P that is on 1 line
292. (
293. ------- Projection on X,Y on one line
294. (((E1.X-P.X)*(E2.Y-P.Y))-
295. ((E2.X-P.X)*(E1.Y-P.Y))) = 0
296. )
297. AND
298. (
299. ------- Projection on X,Z on one line
300. (((E1.X-P.X)*(E2.Z-P.Z))-
301. ((E2.X-P.X)*(E1.Z-P.Z))) = 0
302. )
303. AND
304. (
305. ------- Projection on Y,Z on one line
306. (((E1.Y-P.Y)*(E2.Z-P.Z))-
307. ((E2.Y-P.Y)*(E1.Z-P.Z))) = 0
308. )
309. )
310. AND
311. ------- P is outside [E1,E2]
312. (
313. ((P.X-E1.X)*(P.X-E2.X) > 0)
314. OR
315. ((P.Y-E1.Y)*(P.Y-E2.Y) > 0)
316. OR
317. ((P.Z-E1.Z)*(P.Z-E2.Z) > 0)
318. )
319. )
320. )
321. )
322. --^45--
323. AND
324. ------- there exist two points P1, P2 with:
325. ------- E1,E2,P1 are not on 1 line
326. ------- all points lie on the same side of the plane E1,E2,P1
327. ------- E1,E2,P2 are not on one line
328. ------- all points lie on the same side of the plane E1,E2,P2
329. --v46-- E1,E2,P1,P2 are not in one plane
330. ( EXISTS
331. (
332. ------- there exist two points P1, P2 with:
333. SELECT *
334. FROM R1 P1, R1 P2
335. WHERE
336. --v47-- E1,E2,P1 are not on 1 line
337. (
338. (
339. ------- Projection on X,Y on one line
340. (((E1.X-P1.X)*(E2.Y-P1.Y))-
341. ((E2.X-P1.X)*(E1.Y-P1.Y))) <> 0
342. )
343. OR
344. (
345. ------- Projection on X,Z on one line
346. (((E1.X-P1.X)*(E2.Z-P1.Z))-
347. ((E2.X-P1.X)*(E1.Z-P1.Z))) <> 0
348. )
349. OR
350. (
351. ------- Projection on Y,Z on one line
352. (((E1.Y-P1.Y)*(E2.Z-P1.Z))-
353. ((E2.Y-P1.Y)*(E1.Z-P1.Z))) <> 0
354. )
355. )
356. --^47--
357. AND
358. --v48-- all points lie on the same side of the plane E1,E2,P1
359. (
360. NOT EXISTS
361. --v49--
362. (
363. SELECT *
364. FROM R1 Q1, R1 Q2
365. WHERE
366. --v50-- Q1 and Q2 lie on different sides of the plane E1,E2,P1
367. (
368. --v51--
369. (
370. (E1.X-Q1.X)*
371. ((E2.Y-Q1.Y)*(P1.Z-Q1.Z)-
372. (P1.Y-Q1.Y)*(E2.Z-Q1.Z))
373. -
374. (E1.Y-Q1.Y)*
375. ((E2.X-Q1.X)*(P1.Z-Q1.Z)-
376. (E2.Z-Q1.Z)*(P1.X-Q1.X))
377. +
378. (E1.Z-Q1.Z)*
379. ((E2.X-Q1.X)*(P1.Y-Q1.Y)-
380. (E2.Y-Q1.Y)*(P1.X-Q1.X))
381. ) *
382. --^51--
383. --v52--
384. (
385. (E1.X-Q2.X)*
386. ((E2.Y-Q2.Y)*(P1.Z-Q2.Z)-
387. (P1.Y-Q2.Y)*(E2.Z-Q2.Z))
388. -
389. (E1.Y-Q2.Y)*
390. ((E2.X-Q2.X)*(P1.Z-Q2.Z)-
391. (E2.Z-Q2.Z)*(P1.X-Q2.X))
392. +
393. (E1.Z-Q2.Z)*
394. ((E2.X-Q2.X)*(P1.Y-Q2.Y)-
395. (E2.Y-Q2.Y)*(P1.X-Q2.X))
396. )
397. --^52--
398. < 0
399. )
400. --^50--
401. )
402. --^49--
403. )
404. --^48--
405. AND
406. --v53-- E1,E2,P2 are not on 1 line
407. (
408. (
409. ------- Projection on X,Y on one line
410. (((E1.X-P2.X)*(E2.Y-P2.Y))-
411. ((E2.X-P2.X)*(E1.Y-P2.Y))) <> 0
412. )
413. OR
414. (
415. ------- Projection on X,Z on one line
416. (((E1.X-P2.X)*(E2.Z-P2.Z))-
417. ((E2.X-P2.X)*(E1.Z-P2.Z))) <> 0
418. )
419. OR
420. (
421. ------- Projection on Y,Z on one line
422. (((E1.Y-P2.Y)*(E2.Z-P2.Z))-
423. ((E2.Y-P2.Y)*(E1.Z-P2.Z))) <> 0
424. )
425. )
426. --^53--
427. AND
428. --v54-- all points lie on the same side of the plane E1,E2,P2
429. (
430. NOT EXISTS
431. --v55--
432. (
433. SELECT *
434. FROM R1 Q1, R1 Q2
435. WHERE
436. --v56-- Q1 and Q2 lie on different sides of the plane E1,E2,P2
437. (
438. --v57--
439. (
440. (E1.X-Q1.X)*
441. ((E2.Y-Q1.Y)*(P2.Z-Q1.Z)-
442. (P2.Y-Q1.Y)*(E2.Z-Q1.Z))
443. -
444. (E1.Y-Q1.Y)*
445. ((E2.X-Q1.X)*(P2.Z-Q1.Z)-
446. (E2.Z-Q1.Z)*(P2.X-Q1.X))
447. +
448. (E1.Z-Q1.Z)*
449. ((E2.X-Q1.X)*(P2.Y-Q1.Y)-
450. (E2.Y-Q1.Y)*(P2.X-Q1.X))
451. ) *
452. --^57--
453. --v58--
454. (
455. (E1.X-Q2.X)*
456. ((E2.Y-Q2.Y)*(P2.Z-Q2.Z)-
457. (P2.Y-Q2.Y)*(E2.Z-Q2.Z))
458. -
459. (E1.Y-Q2.Y)*
460. ((E2.X-Q2.X)*(P2.Z-Q2.Z)-
461. (E2.Z-Q2.Z)*(P2.X-Q2.X))
462. +
463. (E1.Z-Q2.Z)*
464. ((E2.X-Q2.X)*(P2.Y-Q2.Y)-
465. (E2.Y-Q2.Y)*(P2.X-Q2.X))
466. )
467. --^58--
468. < 0
469. )
470. --^56--
471. )
472. --^55--
473. )
474. --^54--
475. AND
476. --v59-- E1,E2,P1,P2 are not in one plane
477. (
478. (
479. (E2.X-E1.X)*
480. ((P1.Y-E1.Y)*(P2.Z-E1.Z)-
481. (P2.Y-E1.Y)*(P1.Z-E1.Z))
482. -
483. (E2.Y-E1.Y)*
484. ((P1.X-E1.X)*(P2.Z-E1.Z)-
485. (P1.Z-E1.Z)*(P2.X-E1.X))
486. +
487. (E2.Z-E1.Z)*
488. ((P1.X-E1.X)*(P2.Y-E1.Y)-
489. (P1.Y-E1.Y)*(P2.X-E1.X))
490. )
491. <> 0
492. )
493. --^59--
494. )
495. )
496. --^46--
497. )
498. )
499. --^44--
500. )
501. --^40--
502. ;