liquid_feedback_core: 3031c1973748 update/core-update.v3.0.1-v3.0.2.sql

liquid_feedback_core

view update/core-update.v3.0.1-v3.0.2.sql @ 430:3031c1973748

Update script to v3.0.2 added

author	jbe
date	Thu May 22 05:29:28 2014 +0200 (2014-05-22)
parents	73c2ab2d068f
children	5676b0d33833

line source

1 BEGIN;

3 CREATE OR REPLACE VIEW "liquid_feedback_version" AS

4 SELECT * FROM (VALUES ('3.0.2', 3, 0, 2))

5 AS "subquery"("string", "major", "minor", "revision");

8 CREATE TYPE "defeat_strength" AS ENUM ('simple', 'tuple');

10 COMMENT ON TYPE "defeat_strength" IS 'How pairwise defeats are measured for the Schulze method: ''simple'' = only the number of winning votes, ''tuple'' = primarily the number of winning votes, secondarily the number of losing votes';

13 CREATE TYPE "tie_breaking" AS ENUM ('simple', 'variant1', 'variant2');

15 COMMENT ON TYPE "tie_breaking" IS 'Tie-breaker for the Schulze method: ''simple'' = only initiative ids are used, ''variant1'' = use initiative ids in variant 1 for tie breaking of the links (TBRL) and sequentially forbid shared links, ''variant2'' = use initiative ids in variant 2 for tie breaking of the links (TBRL) and sequentially forbid shared links';

18 ALTER TABLE "policy" ADD COLUMN "defeat_strength" "defeat_strength" NOT NULL DEFAULT 'tuple';

19 ALTER TABLE "policy" ADD COLUMN "tie_breaking" "tie_breaking" NOT NULL DEFAULT 'variant1';

21 ALTER TABLE "policy" ADD

22 CONSTRAINT "no_reverse_beat_path_requires_tuple_defeat_strength" CHECK (

23 ("defeat_strength" = 'tuple'::"defeat_strength" OR "no_reverse_beat_path" = FALSE)

24 );

26 COMMENT ON COLUMN "policy"."defeat_strength" IS 'How pairwise defeats are measured for the Schulze method; see type "defeat_strength"; ''tuple'' is the recommended setting';

27 COMMENT ON COLUMN "policy"."tie_breaking" IS 'Tie-breaker for the Schulze method; see type "tie_breaking"; ''variant1'' or ''variant2'' are recommended';

28 COMMENT ON COLUMN "initiative"."reverse_beat_path" IS 'TRUE, if there is a beat path (may include ties) from this initiative to the status quo; set to NULL if "policy"."defeat_strength" is set to ''simple''';

31 DROP FUNCTION "calculate_ranks"("issue"."id"%TYPE);

32 DROP FUNCTION "defeat_strength"(INT4, INT4);

35 CREATE FUNCTION "defeat_strength"

36 ( "positive_votes_p" INT4,

37 "negative_votes_p" INT4,

38 "defeat_strength_p" "defeat_strength" )

39 RETURNS INT8

40 LANGUAGE 'plpgsql' IMMUTABLE AS $$

41 BEGIN

42 IF "defeat_strength_p" = 'simple'::"defeat_strength" THEN

43 IF "positive_votes_p" > "negative_votes_p" THEN

44 RETURN "positive_votes_p";

45 ELSE

46 RETURN 0;

47 END IF;

48 ELSE

49 IF "positive_votes_p" > "negative_votes_p" THEN

50 RETURN ("positive_votes_p"::INT8 << 31) - "negative_votes_p"::INT8;

51 ELSIF "positive_votes_p" = "negative_votes_p" THEN

52 RETURN 0;

53 ELSE

54 RETURN -1;

55 END IF;

56 END IF;

57 END;

58 $$;

60 COMMENT ON FUNCTION "defeat_strength"(INT4, INT4, "defeat_strength") IS 'Calculates defeat strength (INT8!) according to the "defeat_strength" option (see comment on type "defeat_strength")';

63 CREATE FUNCTION "secondary_link_strength"

64 ( "initiative1_ord_p" INT4,

65 "initiative2_ord_p" INT4,

66 "tie_breaking_p" "tie_breaking" )

67 RETURNS INT8

68 LANGUAGE 'plpgsql' IMMUTABLE AS $$

69 BEGIN

70 IF "initiative1_ord_p" = "initiative2_ord_p" THEN

71 RAISE EXCEPTION 'Identical initiative ids passed to "secondary_link_strength" function (should not happen)';

72 END IF;

73 RETURN (

74 CASE WHEN "tie_breaking_p" = 'simple'::"tie_breaking" THEN

75 0

76 ELSE

77 CASE WHEN "initiative1_ord_p" < "initiative2_ord_p" THEN

78 1::INT8 << 62

79 ELSE 0 END

80 +

81 CASE WHEN "tie_breaking_p" = 'variant2'::"tie_breaking" THEN

82 ("initiative2_ord_p"::INT8 << 31) - "initiative1_ord_p"::INT8

83 ELSE

84 "initiative2_ord_p"::INT8 - ("initiative1_ord_p"::INT8 << 31)

85 END

86 END

87 );

88 END;

89 $$;

91 COMMENT ON FUNCTION "secondary_link_strength"(INT4, INT4, "tie_breaking") IS 'Calculates a secondary criterion for the defeat strength (tie-breaking of the links)';

94 CREATE TYPE "link_strength" AS (

95 "primary" INT8,

96 "secondary" INT8 );

98 COMMENT ON TYPE "link_strength" IS 'Type to store the defeat strength of a link between two candidates plus a secondary criterion to create unique link strengths between the candidates (needed for tie-breaking ''variant1'' and ''variant2'')';

100

101 CREATE FUNCTION "find_best_paths"("matrix_d" "link_strength"[][])

102 RETURNS "link_strength"[][]

103 LANGUAGE 'plpgsql' IMMUTABLE AS $$

104 DECLARE

105 "dimension_v" INT4;

106 "matrix_p" "link_strength"[][];

107 "i" INT4;

108 "j" INT4;

109 "k" INT4;

110 BEGIN

111 "dimension_v" := array_upper("matrix_d", 1);

112 "matrix_p" := "matrix_d";

113 "i" := 1;

114 LOOP

115 "j" := 1;

116 LOOP

117 IF "i" != "j" THEN

118 "k" := 1;

119 LOOP

120 IF "i" != "k" AND "j" != "k" THEN

121 IF "matrix_p"["j"]["i"] < "matrix_p"["i"]["k"] THEN

122 IF "matrix_p"["j"]["i"] > "matrix_p"["j"]["k"] THEN

123 "matrix_p"["j"]["k"] := "matrix_p"["j"]["i"];

124 END IF;

125 ELSE

126 IF "matrix_p"["i"]["k"] > "matrix_p"["j"]["k"] THEN

127 "matrix_p"["j"]["k"] := "matrix_p"["i"]["k"];

128 END IF;

129 END IF;

130 END IF;

131 EXIT WHEN "k" = "dimension_v";

132 "k" := "k" + 1;

133 END LOOP;

134 END IF;

135 EXIT WHEN "j" = "dimension_v";

136 "j" := "j" + 1;

137 END LOOP;

138 EXIT WHEN "i" = "dimension_v";

139 "i" := "i" + 1;

140 END LOOP;

141 RETURN "matrix_p";

142 END;

143 $$;

144

145 COMMENT ON FUNCTION "find_best_paths"("link_strength"[][]) IS 'Computes the strengths of the best beat-paths from a square matrix';

146

147

148 CREATE FUNCTION "calculate_ranks"("issue_id_p" "issue"."id"%TYPE)

149 RETURNS VOID

150 LANGUAGE 'plpgsql' VOLATILE AS $$

151 DECLARE

152 "issue_row" "issue"%ROWTYPE;

153 "policy_row" "policy"%ROWTYPE;

154 "dimension_v" INT4;

155 "matrix_a" INT4[][]; -- absolute votes

156 "matrix_d" "link_strength"[][]; -- defeat strength (direct)

157 "matrix_p" "link_strength"[][]; -- defeat strength (best path)

158 "matrix_t" "link_strength"[][]; -- defeat strength (tie-breaking)

159 "matrix_f" BOOLEAN[][]; -- forbidden link (tie-breaking)

160 "matrix_b" BOOLEAN[][]; -- final order (who beats who)

161 "i" INT4;

162 "j" INT4;

163 "m" INT4;

164 "n" INT4;

165 "battle_row" "battle"%ROWTYPE;

166 "rank_ary" INT4[];

167 "rank_v" INT4;

168 "initiative_id_v" "initiative"."id"%TYPE;

169 BEGIN

170 PERFORM "require_transaction_isolation"();

171 SELECT * INTO "issue_row"

172 FROM "issue" WHERE "id" = "issue_id_p";

173 SELECT * INTO "policy_row"

174 FROM "policy" WHERE "id" = "issue_row"."policy_id";

175 SELECT count(1) INTO "dimension_v"

176 FROM "battle_participant" WHERE "issue_id" = "issue_id_p";

177 -- create "matrix_a" with absolute number of votes in pairwise

178 -- comparison:

179 "matrix_a" := array_fill(NULL::INT4, ARRAY["dimension_v", "dimension_v"]);

180 "i" := 1;

181 "j" := 2;

182 FOR "battle_row" IN

183 SELECT * FROM "battle" WHERE "issue_id" = "issue_id_p"

184 ORDER BY

185 "winning_initiative_id" NULLS FIRST,

186 "losing_initiative_id" NULLS FIRST

187 LOOP

188 "matrix_a"["i"]["j"] := "battle_row"."count";

189 IF "j" = "dimension_v" THEN

190 "i" := "i" + 1;

191 "j" := 1;

192 ELSE

193 "j" := "j" + 1;

194 IF "j" = "i" THEN

195 "j" := "j" + 1;

196 END IF;

197 END IF;

198 END LOOP;

199 IF "i" != "dimension_v" OR "j" != "dimension_v" + 1 THEN

200 RAISE EXCEPTION 'Wrong battle count (should not happen)';

201 END IF;

202 -- store direct defeat strengths in "matrix_d" using "defeat_strength"

203 -- and "secondary_link_strength" functions:

204 "matrix_d" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]);

205 "i" := 1;

206 LOOP

207 "j" := 1;

208 LOOP

209 IF "i" != "j" THEN

210 "matrix_d"["i"]["j"] := (

211 "defeat_strength"(

212 "matrix_a"["i"]["j"],

213 "matrix_a"["j"]["i"],

214 "policy_row"."defeat_strength"

215 ),

216 "secondary_link_strength"(

217 "i",

218 "j",

219 "policy_row"."tie_breaking"

220 )

221 )::"link_strength";

222 END IF;

223 EXIT WHEN "j" = "dimension_v";

224 "j" := "j" + 1;

225 END LOOP;

226 EXIT WHEN "i" = "dimension_v";

227 "i" := "i" + 1;

228 END LOOP;

229 -- find best paths:

230 "matrix_p" := "find_best_paths"("matrix_d");

231 -- create partial order:

232 "matrix_b" := array_fill(NULL::BOOLEAN, ARRAY["dimension_v", "dimension_v"]);

233 "i" := 1;

234 LOOP

235 "j" := "i" + 1;

236 LOOP

237 IF "i" != "j" THEN

238 IF "matrix_p"["i"]["j"] > "matrix_p"["j"]["i"] THEN

239 "matrix_b"["i"]["j"] := TRUE;

240 "matrix_b"["j"]["i"] := FALSE;

241 ELSIF "matrix_p"["i"]["j"] < "matrix_p"["j"]["i"] THEN

242 "matrix_b"["i"]["j"] := FALSE;

243 "matrix_b"["j"]["i"] := TRUE;

244 END IF;

245 END IF;

246 EXIT WHEN "j" = "dimension_v";

247 "j" := "j" + 1;

248 END LOOP;

249 EXIT WHEN "i" = "dimension_v" - 1;

250 "i" := "i" + 1;

251 END LOOP;

252 -- tie-breaking by forbidding shared weakest links in beat-paths

253 -- (unless "tie_breaking" is set to 'simple', in which case tie-breaking

254 -- is performed later by initiative id):

255 IF "policy_row"."tie_breaking" != 'simple'::"tie_breaking" THEN

256 "m" := 1;

257 LOOP

258 "n" := "m" + 1;

259 LOOP

260 -- only process those candidates m and n, which are tied:

261 IF "matrix_b"["m"]["n"] ISNULL THEN

262 -- start with beat-paths prior tie-breaking:

263 "matrix_t" := "matrix_p";

264 -- start with all links allowed:

265 "matrix_f" := array_fill(FALSE, ARRAY["dimension_v", "dimension_v"]);

266 LOOP

267 -- determine (and forbid) that link that is the weakest link

268 -- in both the best path from candidate m to candidate n and

269 -- from candidate n to candidate m:

270 "i" := 1;

271 <<forbid_one_link>>

272 LOOP

273 "j" := 1;

274 LOOP

275 IF "i" != "j" THEN

276 IF "matrix_d"["i"]["j"] = "matrix_t"["m"]["n"] THEN

277 "matrix_f"["i"]["j"] := TRUE;

278 -- exit for performance reasons,

279 -- as exactly one link will be found:

280 EXIT forbid_one_link;

281 END IF;

282 END IF;

283 EXIT WHEN "j" = "dimension_v";

284 "j" := "j" + 1;

285 END LOOP;

286 IF "i" = "dimension_v" THEN

287 RAISE EXCEPTION 'Did not find shared weakest link for tie-breaking (should not happen)';

288 END IF;

289 "i" := "i" + 1;

290 END LOOP;

291 -- calculate best beat-paths while ignoring forbidden links:

292 "i" := 1;

293 LOOP

294 "j" := 1;

295 LOOP

296 IF "i" != "j" THEN

297 "matrix_t"["i"]["j"] := CASE

298 WHEN "matrix_f"["i"]["j"]

299 THEN (-1::INT8) << 63 -- worst possible value

300 ELSE "matrix_d"["i"]["j"] END;

301 END IF;

302 EXIT WHEN "j" = "dimension_v";

303 "j" := "j" + 1;

304 END LOOP;

305 EXIT WHEN "i" = "dimension_v";

306 "i" := "i" + 1;

307 END LOOP;

308 "matrix_t" := "find_best_paths"("matrix_t");

309 -- extend partial order, if tie-breaking was successful:

310 IF "matrix_t"["m"]["n"] > "matrix_t"["n"]["m"] THEN

311 "matrix_b"["m"]["n"] := TRUE;

312 "matrix_b"["n"]["m"] := FALSE;

313 EXIT;

314 ELSIF "matrix_t"["m"]["n"] < "matrix_t"["n"]["m"] THEN

315 "matrix_b"["m"]["n"] := FALSE;

316 "matrix_b"["n"]["m"] := TRUE;

317 EXIT;

318 END IF;

319 END LOOP;

320 END IF;

321 EXIT WHEN "n" = "dimension_v";

322 "n" := "n" + 1;

323 END LOOP;

324 EXIT WHEN "m" = "dimension_v" - 1;

325 "m" := "m" + 1;

326 END LOOP;

327 END IF;

328 -- store a unique ranking in "rank_ary":

329 "rank_ary" := array_fill(NULL::INT4, ARRAY["dimension_v"]);

330 "rank_v" := 1;

331 LOOP

332 "i" := 1;

333 <<assign_next_rank>>

334 LOOP

335 IF "rank_ary"["i"] ISNULL THEN

336 "j" := 1;

337 LOOP

338 IF

339 "i" != "j" AND

340 "rank_ary"["j"] ISNULL AND

341 ( "matrix_b"["j"]["i"] OR

342 -- tie-breaking by "id"

343 ( "matrix_b"["j"]["i"] ISNULL AND

344 "j" < "i" ) )

345 THEN

346 -- someone else is better

347 EXIT;

348 END IF;

349 IF "j" = "dimension_v" THEN

350 -- noone is better

351 "rank_ary"["i"] := "rank_v";

352 EXIT assign_next_rank;

353 END IF;

354 "j" := "j" + 1;

355 END LOOP;

356 END IF;

357 "i" := "i" + 1;

358 IF "i" > "dimension_v" THEN

359 RAISE EXCEPTION 'Schulze ranking does not compute (should not happen)';

360 END IF;

361 END LOOP;

362 EXIT WHEN "rank_v" = "dimension_v";

363 "rank_v" := "rank_v" + 1;

364 END LOOP;

365 -- write preliminary results:

366 "i" := 2; -- omit status quo with "i" = 1

367 FOR "initiative_id_v" IN

368 SELECT "id" FROM "initiative"

369 WHERE "issue_id" = "issue_id_p" AND "admitted"

370 ORDER BY "id"

371 LOOP

372 UPDATE "initiative" SET

373 "direct_majority" =

374 CASE WHEN "policy_row"."direct_majority_strict" THEN

375 "positive_votes" * "policy_row"."direct_majority_den" >

376 "policy_row"."direct_majority_num" * ("positive_votes"+"negative_votes")

377 ELSE

378 "positive_votes" * "policy_row"."direct_majority_den" >=

379 "policy_row"."direct_majority_num" * ("positive_votes"+"negative_votes")

380 END

381 AND "positive_votes" >= "policy_row"."direct_majority_positive"

382 AND "issue_row"."voter_count"-"negative_votes" >=

383 "policy_row"."direct_majority_non_negative",

384 "indirect_majority" =

385 CASE WHEN "policy_row"."indirect_majority_strict" THEN

386 "positive_votes" * "policy_row"."indirect_majority_den" >

387 "policy_row"."indirect_majority_num" * ("positive_votes"+"negative_votes")

388 ELSE

389 "positive_votes" * "policy_row"."indirect_majority_den" >=

390 "policy_row"."indirect_majority_num" * ("positive_votes"+"negative_votes")

391 END

392 AND "positive_votes" >= "policy_row"."indirect_majority_positive"

393 AND "issue_row"."voter_count"-"negative_votes" >=

394 "policy_row"."indirect_majority_non_negative",

395 "schulze_rank" = "rank_ary"["i"],

396 "better_than_status_quo" = "rank_ary"["i"] < "rank_ary"[1],

397 "worse_than_status_quo" = "rank_ary"["i"] > "rank_ary"[1],

398 "multistage_majority" = "rank_ary"["i"] >= "rank_ary"[1],

399 "reverse_beat_path" = CASE WHEN "policy_row"."defeat_strength" = 'simple'::"defeat_strength"

400 THEN NULL

401 ELSE "matrix_p"[1]["i"]."primary" >= 0 END,

402 "eligible" = FALSE,

403 "winner" = FALSE,

404 "rank" = NULL -- NOTE: in cases of manual reset of issue state

405 WHERE "id" = "initiative_id_v";

406 "i" := "i" + 1;

407 END LOOP;

408 IF "i" != "dimension_v" + 1 THEN

409 RAISE EXCEPTION 'Wrong winner count (should not happen)';

410 END IF;

411 -- take indirect majorities into account:

412 LOOP

413 UPDATE "initiative" SET "indirect_majority" = TRUE

414 FROM (

415 SELECT "new_initiative"."id" AS "initiative_id"

416 FROM "initiative" "old_initiative"

417 JOIN "initiative" "new_initiative"

418 ON "new_initiative"."issue_id" = "issue_id_p"

419 AND "new_initiative"."indirect_majority" = FALSE

420 JOIN "battle" "battle_win"

421 ON "battle_win"."issue_id" = "issue_id_p"

422 AND "battle_win"."winning_initiative_id" = "new_initiative"."id"

423 AND "battle_win"."losing_initiative_id" = "old_initiative"."id"

424 JOIN "battle" "battle_lose"

425 ON "battle_lose"."issue_id" = "issue_id_p"

426 AND "battle_lose"."losing_initiative_id" = "new_initiative"."id"

427 AND "battle_lose"."winning_initiative_id" = "old_initiative"."id"

428 WHERE "old_initiative"."issue_id" = "issue_id_p"

429 AND "old_initiative"."indirect_majority" = TRUE

430 AND CASE WHEN "policy_row"."indirect_majority_strict" THEN

431 "battle_win"."count" * "policy_row"."indirect_majority_den" >

432 "policy_row"."indirect_majority_num" *

433 ("battle_win"."count"+"battle_lose"."count")

434 ELSE

435 "battle_win"."count" * "policy_row"."indirect_majority_den" >=

436 "policy_row"."indirect_majority_num" *

437 ("battle_win"."count"+"battle_lose"."count")

438 END

439 AND "battle_win"."count" >= "policy_row"."indirect_majority_positive"

440 AND "issue_row"."voter_count"-"battle_lose"."count" >=

441 "policy_row"."indirect_majority_non_negative"

442 ) AS "subquery"

443 WHERE "id" = "subquery"."initiative_id";

444 EXIT WHEN NOT FOUND;

445 END LOOP;

446 -- set "multistage_majority" for remaining matching initiatives:

447 UPDATE "initiative" SET "multistage_majority" = TRUE

448 FROM (

449 SELECT "losing_initiative"."id" AS "initiative_id"

450 FROM "initiative" "losing_initiative"

451 JOIN "initiative" "winning_initiative"

452 ON "winning_initiative"."issue_id" = "issue_id_p"

453 AND "winning_initiative"."admitted"

454 JOIN "battle" "battle_win"

455 ON "battle_win"."issue_id" = "issue_id_p"

456 AND "battle_win"."winning_initiative_id" = "winning_initiative"."id"

457 AND "battle_win"."losing_initiative_id" = "losing_initiative"."id"

458 JOIN "battle" "battle_lose"

459 ON "battle_lose"."issue_id" = "issue_id_p"

460 AND "battle_lose"."losing_initiative_id" = "winning_initiative"."id"

461 AND "battle_lose"."winning_initiative_id" = "losing_initiative"."id"

462 WHERE "losing_initiative"."issue_id" = "issue_id_p"

463 AND "losing_initiative"."admitted"

464 AND "winning_initiative"."schulze_rank" <

465 "losing_initiative"."schulze_rank"

466 AND "battle_win"."count" > "battle_lose"."count"

467 AND (

468 "battle_win"."count" > "winning_initiative"."positive_votes" OR

469 "battle_lose"."count" < "losing_initiative"."negative_votes" )

470 ) AS "subquery"

471 WHERE "id" = "subquery"."initiative_id";

472 -- mark eligible initiatives:

473 UPDATE "initiative" SET "eligible" = TRUE

474 WHERE "issue_id" = "issue_id_p"

475 AND "initiative"."direct_majority"

476 AND "initiative"."indirect_majority"

477 AND "initiative"."better_than_status_quo"

478 AND (

479 "policy_row"."no_multistage_majority" = FALSE OR

480 "initiative"."multistage_majority" = FALSE )

481 AND (

482 "policy_row"."no_reverse_beat_path" = FALSE OR

483 coalesce("initiative"."reverse_beat_path", FALSE) = FALSE );

484 -- mark final winner:

485 UPDATE "initiative" SET "winner" = TRUE

486 FROM (

487 SELECT "id" AS "initiative_id"

488 FROM "initiative"

489 WHERE "issue_id" = "issue_id_p" AND "eligible"

490 ORDER BY

491 "schulze_rank",

492 "id"

493 LIMIT 1

494 ) AS "subquery"

495 WHERE "id" = "subquery"."initiative_id";

496 -- write (final) ranks:

497 "rank_v" := 1;

498 FOR "initiative_id_v" IN

499 SELECT "id"

500 FROM "initiative"

501 WHERE "issue_id" = "issue_id_p" AND "admitted"

502 ORDER BY

503 "winner" DESC,

504 "eligible" DESC,

505 "schulze_rank",

506 "id"

507 LOOP

508 UPDATE "initiative" SET "rank" = "rank_v"

509 WHERE "id" = "initiative_id_v";

510 "rank_v" := "rank_v" + 1;

511 END LOOP;

512 -- set schulze rank of status quo and mark issue as finished:

513 UPDATE "issue" SET

514 "status_quo_schulze_rank" = "rank_ary"[1],

515 "state" =

516 CASE WHEN EXISTS (

517 SELECT NULL FROM "initiative"

518 WHERE "issue_id" = "issue_id_p" AND "winner"

519 ) THEN

520 'finished_with_winner'::"issue_state"

521 ELSE

522 'finished_without_winner'::"issue_state"

523 END,

524 "closed" = "phase_finished",

525 "phase_finished" = NULL

526 WHERE "id" = "issue_id_p";

527 RETURN;

528 END;

529 $$;

530

531

532 COMMIT;