Sokrates on Oracle

Archive for the ‘fun’ Category

The Fundamental theorem of arithmetic – SQL version

Posted by Matthias Rogel on 26. May 2015

Every positive integer (except the number 1) can be represented in exactly one way apart from rearrangement as a product of one or more primes, see for example Wolfram MathWorld or Wikipedia.

Here is the SQL-Version, we compute this for all integers up to 100

with bound as
(
select 100 as bound from dual
),
n_until_bound as (
select level+1 n
from dual
connect by level <= (select bound.bound from bound)
),
primes_under_bound as
(
select n_until_bound.n as prime
from n_until_bound
minus
select n1.n * n2.n
from n_until_bound n1, n_until_bound n2
where n1.n <= n2.n
and n1.n <= (select sqrt(bound.bound) from bound)
),
primepowers_until_bound as
(
select p.prime, l.exponent
from primes_under_bound p, lateral(select level as exponent from dual connect by level <= log(p.prime, (select bound.bound from bound))) l
),
factors as
(
select n.n, pb.prime, pb.exponent
from n_until_bound n, primepowers_until_bound pb
where mod(n.n, power(pb.prime, pb.exponent)) = 0
),
largestfactors as
(
select
 f.n, f.prime, min(f.exponent) keep(dense_rank first order by f.exponent desc) as exponent
from factors f
group by f.n, f.prime
)
select /*+pallel */ lf.n || ' = ' || listagg(lf.prime || case when lf.exponent > 1 then ' ^ ' || lf.exponent end, ' * ') within group(order by lf.prime asc) as factorization
from largestfactors lf
group by lf.n
order by lf.n
FACTORIZATION
----------------------------------------------------------------------------------------------------
2 = 2
3 = 3
4 = 2 ^ 2
5 = 5
6 = 2 * 3
7 = 7
8 = 2 ^ 3
9 = 3 ^ 2
10 = 2 * 5
11 = 11
12 = 2 ^ 2 * 3
13 = 13
14 = 2 * 7
15 = 3 * 5
16 = 2 ^ 4
17 = 17
18 = 2 * 3 ^ 2
19 = 19
20 = 2 ^ 2 * 5
21 = 3 * 7
22 = 2 * 11
23 = 23
24 = 2 ^ 3 * 3
25 = 5 ^ 2
26 = 2 * 13
27 = 3 ^ 3
28 = 2 ^ 2 * 7
29 = 29
30 = 2 * 3 * 5
31 = 31
32 = 2 ^ 5
33 = 3 * 11
34 = 2 * 17
35 = 5 * 7
36 = 2 ^ 2 * 3 ^ 2
37 = 37
38 = 2 * 19
39 = 3 * 13
40 = 2 ^ 3 * 5
41 = 41
42 = 2 * 3 * 7
43 = 43
44 = 2 ^ 2 * 11
45 = 3 ^ 2 * 5
46 = 2 * 23
47 = 47
48 = 2 ^ 4 * 3
49 = 7 ^ 2
50 = 2 * 5 ^ 2
51 = 3 * 17
52 = 2 ^ 2 * 13
53 = 53
54 = 2 * 3 ^ 3
55 = 5 * 11
56 = 2 ^ 3 * 7
57 = 3 * 19
58 = 2 * 29
59 = 59
60 = 2 ^ 2 * 3 * 5
61 = 61
62 = 2 * 31
63 = 3 ^ 2 * 7
64 = 2 ^ 6
65 = 5 * 13
66 = 2 * 3 * 11
67 = 67
68 = 2 ^ 2 * 17
69 = 3 * 23
70 = 2 * 5 * 7
71 = 71
72 = 2 ^ 3 * 3 ^ 2
73 = 73
74 = 2 * 37
75 = 3 * 5 ^ 2
76 = 2 ^ 2 * 19
77 = 7 * 11
78 = 2 * 3 * 13
79 = 79
80 = 2 ^ 4 * 5
81 = 3 ^ 4
82 = 2 * 41
83 = 83
84 = 2 ^ 2 * 3 * 7
85 = 5 * 17
86 = 2 * 43
87 = 3 * 29
88 = 2 ^ 3 * 11
89 = 89
90 = 2 * 3 ^ 2 * 5
91 = 7 * 13
92 = 2 ^ 2 * 23
93 = 3 * 31
94 = 2 * 47
95 = 5 * 19
96 = 2 ^ 5 * 3
97 = 97
98 = 2 * 7 ^ 2
99 = 3 ^ 2 * 11
100 = 2 ^ 2 * 5 ^ 2

Posted in fun, sql | Tagged: , | 1 Comment »

A Greedy Algorithm using Recursive subquery factoring ( or better – read the comments – using pattern matching)

Posted by Matthias Rogel on 22. May 2015

Today is friday and I like the twitter-hashtag #FibonacciFriday,
so I tweeted

 

Don’t be afraid of having a look at the wikipedia-site, the math is not complicated at all ( you don’t need more than adding natural numbers smaller than hundred ), nevertheless the theorem is nice from a mathematical point of view.

And there is also mentioned

… For any given positive integer, a representation that satisfies the conditions of Zeckendorf’s theorem can be found by using a greedy algorithm, choosing the largest possible Fibonacci number at each stage. …

After thinking a bit about it, I came to the idea to implement it solely in SQL which might show the strength of this language.

Here we go, we compute the Zeckendorf representations of the first 200 natural numbers in SQL.

If you are not familiar with the xmlquery-part of it, see what Tom Kyte learned from me


with
n as
(
 /* the first 200 natural numbers */
 select level as n
 from dual
 connect by level <= 200
),
f(n, a, b) as
(
 /* construct fibonaccis, 30 are surely enough ... */
 select 1 as n, 1 as a, 1 as b
 from dual
 union all
 select n+1, b, a+b
 from f
 where n<=30
)
,
fibonaccis as
(
 select
 f.a as f
 from f
),
decomp(n, s) as
(
 /* here is the magic recursive subquery factoring */
 select
 n.n,
 (select cast(max(fibonaccis.f) as varchar2(100)) from fibonaccis where fibonaccis.f <= n.n)
 from n
 union all
 select
 d.n,
 rtrim
 (
 d.s || ' + ' ||
 (
 select cast(max(fibonaccis.f) as varchar2(10))
 from fibonaccis
 where fibonaccis.f <= d.n - xmlquery(d.s returning content).getNumberVal()
 ),
 ' + '
 )
 from decomp d
 where
 d.s !=
 rtrim
 (
 d.s || ' + ' ||
 (
 select cast(max(fibonaccis.f) as varchar2(10))
 from fibonaccis
 where fibonaccis.f <= d.n - xmlquery(d.s returning content).getNumberVal()
 ),
 ' + '
 )
)
/* we only want "the last" decomp, the one with maximal length */
select
 decomp.n ||
 ' = ' ||
 min(decomp.s) keep(dense_rank first order by length(decomp.s) desc)
 as zeckendorf_representation
from decomp
group by decomp.n
order by decomp.n
/

ZECKENDORF_REPRESENTATION
------------------------------------------------------------------------------------------------------------------------------------------------------------
1 = 1
2 = 2
3 = 3
4 = 3 + 1
5 = 5
6 = 5 + 1
7 = 5 + 2
8 = 8
9 = 8 + 1
10 = 8 + 2
11 = 8 + 3
12 = 8 + 3 + 1
13 = 13
14 = 13 + 1
15 = 13 + 2
16 = 13 + 3
17 = 13 + 3 + 1
18 = 13 + 5
19 = 13 + 5 + 1
20 = 13 + 5 + 2
21 = 21
22 = 21 + 1
23 = 21 + 2
24 = 21 + 3
25 = 21 + 3 + 1
26 = 21 + 5
27 = 21 + 5 + 1
28 = 21 + 5 + 2
29 = 21 + 8
30 = 21 + 8 + 1
31 = 21 + 8 + 2
32 = 21 + 8 + 3
33 = 21 + 8 + 3 + 1
34 = 34
35 = 34 + 1
36 = 34 + 2
37 = 34 + 3
38 = 34 + 3 + 1
39 = 34 + 5
40 = 34 + 5 + 1
41 = 34 + 5 + 2
42 = 34 + 8
43 = 34 + 8 + 1
44 = 34 + 8 + 2
45 = 34 + 8 + 3
46 = 34 + 8 + 3 + 1
47 = 34 + 13
48 = 34 + 13 + 1
49 = 34 + 13 + 2
50 = 34 + 13 + 3
51 = 34 + 13 + 3 + 1
52 = 34 + 13 + 5
53 = 34 + 13 + 5 + 1
54 = 34 + 13 + 5 + 2
55 = 55
56 = 55 + 1
57 = 55 + 2
58 = 55 + 3
59 = 55 + 3 + 1
60 = 55 + 5
61 = 55 + 5 + 1
62 = 55 + 5 + 2
63 = 55 + 8
64 = 55 + 8 + 1
65 = 55 + 8 + 2
66 = 55 + 8 + 3
67 = 55 + 8 + 3 + 1
68 = 55 + 13
69 = 55 + 13 + 1
70 = 55 + 13 + 2
71 = 55 + 13 + 3
72 = 55 + 13 + 3 + 1
73 = 55 + 13 + 5
74 = 55 + 13 + 5 + 1
75 = 55 + 13 + 5 + 2
76 = 55 + 21
77 = 55 + 21 + 1
78 = 55 + 21 + 2
79 = 55 + 21 + 3
80 = 55 + 21 + 3 + 1
81 = 55 + 21 + 5
82 = 55 + 21 + 5 + 1
83 = 55 + 21 + 5 + 2
84 = 55 + 21 + 8
85 = 55 + 21 + 8 + 1
86 = 55 + 21 + 8 + 2
87 = 55 + 21 + 8 + 3
88 = 55 + 21 + 8 + 3 + 1
89 = 89
90 = 89 + 1
91 = 89 + 2
92 = 89 + 3
93 = 89 + 3 + 1
94 = 89 + 5
95 = 89 + 5 + 1
96 = 89 + 5 + 2
97 = 89 + 8
98 = 89 + 8 + 1
99 = 89 + 8 + 2
100 = 89 + 8 + 3
101 = 89 + 8 + 3 + 1
102 = 89 + 13
103 = 89 + 13 + 1
104 = 89 + 13 + 2
105 = 89 + 13 + 3
106 = 89 + 13 + 3 + 1
107 = 89 + 13 + 5
108 = 89 + 13 + 5 + 1
109 = 89 + 13 + 5 + 2
110 = 89 + 21
111 = 89 + 21 + 1
112 = 89 + 21 + 2
113 = 89 + 21 + 3
114 = 89 + 21 + 3 + 1
115 = 89 + 21 + 5
116 = 89 + 21 + 5 + 1
117 = 89 + 21 + 5 + 2
118 = 89 + 21 + 8
119 = 89 + 21 + 8 + 1
120 = 89 + 21 + 8 + 2
121 = 89 + 21 + 8 + 3
122 = 89 + 21 + 8 + 3 + 1
123 = 89 + 34
124 = 89 + 34 + 1
125 = 89 + 34 + 2
126 = 89 + 34 + 3
127 = 89 + 34 + 3 + 1
128 = 89 + 34 + 5
129 = 89 + 34 + 5 + 1
130 = 89 + 34 + 5 + 2
131 = 89 + 34 + 8
132 = 89 + 34 + 8 + 1
133 = 89 + 34 + 8 + 2
134 = 89 + 34 + 8 + 3
135 = 89 + 34 + 8 + 3 + 1
136 = 89 + 34 + 13
137 = 89 + 34 + 13 + 1
138 = 89 + 34 + 13 + 2
139 = 89 + 34 + 13 + 3
140 = 89 + 34 + 13 + 3 + 1
141 = 89 + 34 + 13 + 5
142 = 89 + 34 + 13 + 5 + 1
143 = 89 + 34 + 13 + 5 + 2
144 = 144
145 = 144 + 1
146 = 144 + 2
147 = 144 + 3
148 = 144 + 3 + 1
149 = 144 + 5
150 = 144 + 5 + 1
151 = 144 + 5 + 2
152 = 144 + 8
153 = 144 + 8 + 1
154 = 144 + 8 + 2
155 = 144 + 8 + 3
156 = 144 + 8 + 3 + 1
157 = 144 + 13
158 = 144 + 13 + 1
159 = 144 + 13 + 2
160 = 144 + 13 + 3
161 = 144 + 13 + 3 + 1
162 = 144 + 13 + 5
163 = 144 + 13 + 5 + 1
164 = 144 + 13 + 5 + 2
165 = 144 + 21
166 = 144 + 21 + 1
167 = 144 + 21 + 2
168 = 144 + 21 + 3
169 = 144 + 21 + 3 + 1
170 = 144 + 21 + 5
171 = 144 + 21 + 5 + 1
172 = 144 + 21 + 5 + 2
173 = 144 + 21 + 8
174 = 144 + 21 + 8 + 1
175 = 144 + 21 + 8 + 2
176 = 144 + 21 + 8 + 3
177 = 144 + 21 + 8 + 3 + 1
178 = 144 + 34
179 = 144 + 34 + 1
180 = 144 + 34 + 2
181 = 144 + 34 + 3
182 = 144 + 34 + 3 + 1
183 = 144 + 34 + 5
184 = 144 + 34 + 5 + 1
185 = 144 + 34 + 5 + 2
186 = 144 + 34 + 8
187 = 144 + 34 + 8 + 1
188 = 144 + 34 + 8 + 2
189 = 144 + 34 + 8 + 3
190 = 144 + 34 + 8 + 3 + 1
191 = 144 + 34 + 13
192 = 144 + 34 + 13 + 1
193 = 144 + 34 + 13 + 2
194 = 144 + 34 + 13 + 3
195 = 144 + 34 + 13 + 3 + 1
196 = 144 + 34 + 13 + 5
197 = 144 + 34 + 13 + 5 + 1
198 = 144 + 34 + 13 + 5 + 2
199 = 144 + 55
200 = 144 + 55 + 1

200 rows selected.

Elapsed: 00:01:28.71

Posted in fun, sql | Tagged: , | 5 Comments »

Best Practice in 12c

Posted by Matthias Rogel on 4. December 2013

Since PL/SQL now is closely integrated into SQL, we hence can happily state

sokrates@12.1 > with function bestpractice return varchar2
  2  is
  3  begin
  4     return 'Do not use PL/SQL when it can be done with SQL alone !';
  5  end bestpractice;
  6  select bestpractice() from dual
  7  /

BESTPRACTICE()
--------------------------------------------------------------------------------
Do not use PL/SQL when it can be done with SQL alone !

Posted in 12c, Allgemein, fun, sql | Tagged: | 2 Comments »

A Hint without +

Posted by Matthias Rogel on 4. June 2011

I always though, every hint would start with /*+ or –+, SQL reference   http://download.oracle.com/docs/cd/E11882_01/server.112/e17118/sql_elements006.htm#SQLRF00219 also says that.

But I learnt something new on

http://www.dba-oracle.com/t_11g_adaptive_cursor_sharing.htm

about the

adaptive cursor sharing hint (acs_1)

:

The same on

http://www.dba-oracle.com/t_cursor_sharing_similar.htm :

an “11g adaptive cursor sharing tip

Interesting, isn’t it ?

Couldn’t find something about this hint without a + in the docs nor on support.

But didn’t optimizermagic himself write about it on http://optimizermagic.blogspot.com/2007/12/why-are-there-more-cursors-in-11g-for.html :

Plenty of

/*ACS_1*/

‘s there ! ( as on http://optimizermagic.blogspot.com/2009/04/update-on-adaptive-cursor-sharing.html )

Well, they only use /*ACS_1 */ as a marker comment to find the sql later on in v$sql, so they can demonstrate the new 11g adaptive cursor sharing feature.

I arrived to a conclusion how this “tip”  originated and had a great laugh !

Should everyone who read this come to his own conclusions

By the way, on http://optimizermagic.blogspot.com/2007/12/why-are-there-more-cursors-in-11g-for.html , they indeed announce a hint to mark a statement as bind aware:

Q: Are you planning a hint to mark statements as bind-aware ?
A: Yes, we plan to add this in the future. This will allow users to bypass the startup cost of automatically determining that a query is a good candidate for bind-aware cursor sharing.

Seems to me that it is the BIND_AWARE hint mentioned in Bug 9532657 :

For cursors where one knows it wants to be bind aware then add a 
/*+ BIND_AWARE */ hint. 
This makes the cursor aware of bind values rather than automatically 
trying to work out if it should change from non-aware to aware 
based on execution statistics.
...
"

Can’t check it now because I have no access to an 11g at the moment, will check it later on and update this not.

Update:

seems to be correct, BIND_AWARE ( which does occur in V$SQL_HINT ) suffices to mark an sql bind aware, as long as statistics do exist:

sokrates@11.2 > create table t ( i int );

Table created.

sokrates@11.2 > exec dbms_stats.gather_table_stats(user, 'T', cascade => true)

PL/SQL procedure successfully completed.

sokrates@11.2 > variable n number
sokrates@11.2 > exec :n := 1

PL/SQL procedure successfully completed.

sokrates@11.2 > select /*+BIND_AWARE */ * from t where i=:n;

no rows selected

sokrates@11.2 > select /*ACS_1 */ * from t where i=:n;

no rows selected

sokrates@11.2 > select /*placebo */ * from t where i=:n;

no rows selected

sokrates@11.2 > select is_bind_sensitive, is_bind_aware, sql_text from v$sql
where sql_text like 'select /*ACS_1%' or sql_text like 'select /*+BIND%' or sql_text like 'select /*placebo%';

IS_ IS_
--- ---
SQL_TEXT
---------------------------------
Y N
select /*placebo */ * from t where i=:n

Y N
select /*ACS_1 */ * from t where i=:n

Y Y
select /*+BIND_AWARE */ * from t where i=:n

sokrates@11.2 > REM stats on t suffice to become bind aware with hint "BIND_AWARE", ACS_1 behaves like placebo

Posted in 11g, fun | Tagged: | 2 Comments »