<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Benjamin Campbell on Medium]]></title>
        <description><![CDATA[Stories by Benjamin Campbell on Medium]]></description>
        <link>https://medium.com/@benjaminsky?source=rss-f628cb8c61f5------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*hbds3S_OnPHFPh51j-S8yg.jpeg</url>
            <title>Stories by Benjamin Campbell on Medium</title>
            <link>https://medium.com/@benjaminsky?source=rss-f628cb8c61f5------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 17:51:20 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@benjaminsky/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Complex Survivorship in BigQuery]]></title>
            <link>https://benjaminsky.medium.com/complex-survivorship-in-bigquery-a99c9103d328?source=rss-f628cb8c61f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/a99c9103d328</guid>
            <category><![CDATA[sql]]></category>
            <category><![CDATA[master-data-management]]></category>
            <category><![CDATA[analytics]]></category>
            <category><![CDATA[data-engineering]]></category>
            <category><![CDATA[bigquery]]></category>
            <dc:creator><![CDATA[Benjamin Campbell]]></dc:creator>
            <pubDate>Sat, 17 Apr 2021 19:00:21 GMT</pubDate>
            <atom:updated>2021-07-28T15:03:32.063Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CCrh_mkyneOiC_I6h_yEsQ.png" /></figure><p>This story is a followup to my previous story <a href="https://benjaminsky.medium.com/complex-deduplication-in-bigquery-a3c5e78dec2b">Complex Deduplication in BigQuery</a>.</p><p><a href="https://mdmlist.com/2019/08/22/three-master-data-survivorship-approaches/">Survivorship</a> is the process of choosing canonical values from deduplicated data. The results are often called <a href="https://en.wikipedia.org/wiki/Master_data#Alternative_definition">master data</a> or <a href="https://en.wikipedia.org/wiki/Single_source_of_truth#Master_data_management_(MDM)">golden records</a>.</p><h3>1. Preparation</h3><p>Survivorship requires a dataset with some kind of group_id field. My <a href="https://benjaminsky.medium.com/complex-deduplication-in-bigquery-a3c5e78dec2b">previous story</a> demonstrates how to deduplicate a dataset, so we’ll skip that step for now and start with a pre-grouped source table.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5d1f7305f2bf5ed4eba3e46611bcd88d/href">https://medium.com/media/5d1f7305f2bf5ed4eba3e46611bcd88d/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*W8vIbIpw-ATlBNhpyEyTzg.png" /></figure><h3>2. Grouping candidates into arrays</h3><p>The most efficient method I’ve found for chunking records for survivorship is to roll them up with ARRAY_AGG. For this to work, you must have fewer than 1 million candidate records per group, and ideally, you’d have tens of them. This will be very efficient in BigQuery if the candidate count per group is low.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a5a7043993ad3e588aaabd6d7889fc05/href">https://medium.com/media/a5a7043993ad3e588aaabd6d7889fc05/href</a></iframe><p>You must wrap multiple fields in a struct to group entire records.</p><p>The result of this query will be 2 rows, each containing all survivorship candidate records in a single, queryable field value. A good way to conceptualize this operation is that the ARRAY_AGG outputs a JSON array and STRUCT outputs a JSON struct like this:</p><pre>[<br>  {<br>    &quot;name&quot;: &quot;Albert Einstein&quot;,<br>    &quot;email&quot;: &quot;al@gmail.com&quot;, <br>    ...<br>  }<br>]</pre><h3>3. Survivorship</h3><p>In this step, we will be UNNESTing the candidate arrays in subqueries to handle various complex scenarios. The ARRAY_AGG + UNNEST pattern allows us to design our survivorship queries as if an entire table contains only our candidate rows, making reasoning about complex survivorship scenarios much easier.</p><h4>Most recent non-null</h4><p>Probably the simplest and most common survivorship strategy is to take the most recent non-null value.</p><p>Here’s what that would look like if our table contained only a single group:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8120dda701ad43dc33370fe65197f000/href">https://medium.com/media/8120dda701ad43dc33370fe65197f000/href</a></iframe><p>Here it is in the main survivorship script:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2114dacb1df58c0efdb7622071c056fd/href">https://medium.com/media/2114dacb1df58c0efdb7622071c056fd/href</a></iframe><p>A few things to note:</p><ul><li>Our survivorship query is now a subquery in the SELECT clause</li><li>We use SELECT AS STRUCT and (&lt;query&gt;).*. The .* <a href="https://cloud.google.com/bigquery/docs/reference/standard-sql/query-syntax#select_expression">produces one output column for each column or top-level field of the subquery</a>. This prevents the annoying f0_.name that you’d get without it. If you only query a single field this isn’t necessary.</li><li>UNNEST(candidates) <a href="https://cloud.google.com/bigquery/docs/reference/standard-sql/query-syntax#unnest_operator">takes the candidate array and returns a table</a></li><li>name_recent and name_recent_created are from the same row. If we used the same query for a different field we’d likely get a different date</li></ul><h4>Validation</h4><p>Another common survivorship scenario is <em>most recent valid</em>. This is used for emails and phone numbers quite often. We’ll start with the same query as the previous example and add one more where predicate. The regex I’m using is the absolute minimum validation you’d want to do but gets the point across for this example. If you wanted a more robust validation function, now would be the perfect time to use a JavaScript stored procedure.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bac2eee3e2790c750a381480d7c27fb5/href">https://medium.com/media/bac2eee3e2790c750a381480d7c27fb5/href</a></iframe><p>Here’s the new query with this example appended:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ddf6dcb7a7bb4ed8cc224fb85722fb40/href">https://medium.com/media/ddf6dcb7a7bb4ed8cc224fb85722fb40/href</a></iframe><h4>Source system prioritization</h4><p>In this example, we’ll prioritize certain source systems over others and choose the most recent records from within a priority group. We could also combine this with a <em>within_last_month</em> flag so it only applies to recent values, but I’ll keep it simple for now.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/18ee455bc55eeed6d97e1e7a903f8f49/href">https://medium.com/media/18ee455bc55eeed6d97e1e7a903f8f49/href</a></iframe><p>I’m going to stop adding these to the main query now that you’ve got the idea.</p><h4>Most complete</h4><p>This is very common for names and addresses. For names, it’s often total character length, but for addresses, it’s usually a score for each non-null field. city and state will usually have high scores and address_line2 will have a lower one. Addresses often have validation logic of fields like city and state as well. This is generally the most complex survivorship use-case for firms that don’t use a third-party address validation service. If they do, address survivorship turns into source system prioritization.</p><p>Even though I don’t have address data, here’s an example of what I’m talking about:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ba61db69abd5a1e3ea53d21483ed3d18/href">https://medium.com/media/ba61db69abd5a1e3ea53d21483ed3d18/href</a></iframe><h3>Using DBT</h3><p>You’re probably thinking, “wow, this query is getting gnarly!” and I’d agree. You can DRY it up significantly if you’re using <a href="https://www.getdbt.com/">DBT</a> however.</p><h4>Survivorship macro</h4><p>Here’s what a DBT macro would look like for the <em>most recent valid </em>use-case:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/dc2ae6b6fd94cc909f3e35319c6b4bc9/href">https://medium.com/media/dc2ae6b6fd94cc909f3e35319c6b4bc9/href</a></iframe><p>And here’s what the model query would look like after:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6d7d8b83fa481d6582888af160cc0943/href">https://medium.com/media/6d7d8b83fa481d6582888af160cc0943/href</a></iframe><p>This is so much cleaner and I can reuse my logic! This is one of the many reasons I love <a href="https://www.getdbt.com/">DBT</a>.</p><h3>Next steps</h3><ul><li>While I love BigQuery, my main data warehouse tool is currently <a href="https://www.snowflake.com/">Snowflake</a>. I don’t have access to a personal Snowflake instance to use to write my blogs so BigQuery is an excellent alternative. I’d love to have Snowflake versions of these posts as well.</li><li>Add JavaScript stored procedures to the mix.</li></ul><h3>Disclaimer</h3><p>All code in my blog is meant for instructional purposes only. I make no guarantees of accuracy and if you choose to implement any of this, you do so at your own risk.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a99c9103d328" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Complex Deduplication in BigQuery]]></title>
            <link>https://benjaminsky.medium.com/complex-deduplication-in-bigquery-a3c5e78dec2b?source=rss-f628cb8c61f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/a3c5e78dec2b</guid>
            <category><![CDATA[sql]]></category>
            <category><![CDATA[graph]]></category>
            <category><![CDATA[data-engineering]]></category>
            <category><![CDATA[analytics]]></category>
            <category><![CDATA[bigquery]]></category>
            <dc:creator><![CDATA[Benjamin Campbell]]></dc:creator>
            <pubDate>Fri, 16 Apr 2021 22:35:22 GMT</pubDate>
            <atom:updated>2021-07-28T15:10:18.112Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*a8hzYHTlnWA3DaW87WOluQ.png" /></figure><p>This story covers the first step in the deduplication and survivorship process used in <a href="https://en.wikipedia.org/wiki/Master_data_management">master data management</a>. If you’re interested, check out the followup story <a href="https://benjaminsky.medium.com/complex-survivorship-in-bigquery-a99c9103d328">Complex Survivorship in BigQuery</a>.</p><p>Deduplication is challenging with tabular data. You may have customers signing up for promotions with different email addresses, enrichment data that only joins on phone number, multiple emails or addresses for a given customer, missing values, and a multitude of other challenges. On top of all of that, deduplication is inherently a graph problem — specifically connected component subgraph extraction or <em>union find</em>. In this story I’ll show you how to do this all in BigQuery³.</p><h3>1. Preparation</h3><p>First we need some data. Use the following query to create a customer table. These customers come from various source systems. business_key is the primary key of the record in the source system.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/84dc4f32ba6752539909f20b55570931/href">https://medium.com/media/84dc4f32ba6752539909f20b55570931/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Rqh0zix9JSKFvX2yGEDgkw.png" /></figure><p>We’re going to be deduplicating on any non-key field that could uniquely identify an individual. In this example, those fields are email, phone_number¹, and salesforce_id. Each field will be a <em>node. Edges </em>will be the <a href="https://en.wikipedia.org/wiki/Complete_graph#:~:text=In%20the%20mathematical%20field%20of,(one%20in%20each%20direction).">complete graph</a> connecting them. This just means that all nodes are connected to all other nodes. This will correspond to the number of queries in the <a href="https://medium.com/p/a3c5e78dec2b/#b55f">Create edge table</a> section. It’s best to keep the number of deduplication fields low since the number of edge queries will be field_count(field_count − 1)/2.</p><p>Here’s the complete graph for our example:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vn5D5ctU14scvQoFskF1Ig.png" /></figure><p>Here’s what it would look like with 2 more fields:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zMxk3FUALXZzRb__Q0RMbA.png" /></figure><h3>2. Create node tables</h3><p>The first table we need is a bridge between each data point and the raw_data row it came from. This will be necessary at the end when we want to query the raw_data table with group_id.</p><p>We need one query per field that will be connected by an edge. You’ll notice that we have 2 places for salesforce_id. We want the records that reference a salesforce record to have nodes for both their own data and the data from the salesforce row.</p><h4>Schema</h4><ul><li>node_value and node_type are used to build the edge table</li><li>business_key and source_system are used to join back to raw_data</li><li>node_id⁴ is a hash of node_value and note_type</li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bf6bbc17335b97a2fd3bc993491a19c6/href">https://medium.com/media/bf6bbc17335b97a2fd3bc993491a19c6/href</a></iframe><p>Now we can create our node table from this bridge table:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2dbe4b8e6387369598e2f08726668e72/href">https://medium.com/media/2dbe4b8e6387369598e2f08726668e72/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NZR_VHV4FmQ8A0bYX3zydA.png" /></figure><h3>3 . Create edge table</h3><p>For each combination of deduplication node types we’ll need an edge query. First I’ll show just the email-&gt;phone_number query. Note that we create edges in only one direction. We’ll add the other directions later.</p><h4>Schema</h4><ul><li>edge_id is a hash of the left node + right node</li><li>source_query is for debugging to identify the source of the edge</li><li>group_id is a null int64 that will be populated by a seed, then updated by the final deduplication query in a loop</li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7308f3c6c69d93abcdcc9fef57050610/href">https://medium.com/media/7308f3c6c69d93abcdcc9fef57050610/href</a></iframe><h4>Full Edge Query</h4><p>The salesforce_id nodes require a more complex join since they’re either the business_key when source_system=&#39;salesforce&#39; or the salesforce_id field.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d09313203c21879cf40beb39dd262442/href">https://medium.com/media/d09313203c21879cf40beb39dd262442/href</a></iframe><h3>4. Seed group_id</h3><p>Before we start the deduplication process we need to seed the group_id field with unique int². Seeding must happen prior to converting to an undirected graph since both directions must have the same group seed for deduplication to work correctly. You’ll see why once we get to deduplication. There is some <a href="#f269">complexity</a> to this process I’ve left out for now.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1d9864ce3422a7fad9efb2426f4421b9/href">https://medium.com/media/1d9864ce3422a7fad9efb2426f4421b9/href</a></iframe><h3>5. Convert to undirected graph</h3><p>To turn a directed graph into an undirected graph you only need to insert the opposite edges. You’ll see we simply swap node_id_left and node_id_right and create a swapped edge_id and insert this into the original edge table.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/94956276c95d59ee5877456c82c0bf9f/href">https://medium.com/media/94956276c95d59ee5877456c82c0bf9f/href</a></iframe><h3>6. Deduplication</h3><p>This is where the magic happens. Essentially we’re walking all subgraphs in parallel, squashing group_id to min(group_id), alternating our group by between node_id_left and node_id_right. The following query is a single round trip that we’ll be repeating in a while. If we instead replaced the update with a join_to_left CTE, we could duplicate all the CTEs and do multiple rounds of deduplication in a single long query. We could even create a massive query that does <em>n</em> rounds at once, and wouldn’t even have to loop if we know our largest group/subgraph won’t have a <a href="https://en.wikipedia.org/wiki/Distance_(graph_theory)#:~:text=In%20the%20mathematical%20field%20of,shortest%20path%20between%20two%20vertices.">distance</a> greater than <em>n.</em></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/971bf9e7623179eef61e24841d34c0a2/href">https://medium.com/media/971bf9e7623179eef61e24841d34c0a2/href</a></iframe><p>Note the group_id &lt;&gt; min_group_id in the update statement. That’s how we’ll terminate the loop. The first time we run this and get @@rowcount == 0 we’ll know we are done.</p><p>Here’s a step by step example of how it works…</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*18MO_kYXWhcAnLmYV2VRCw.png" /></figure><p>Notice that Step 3 didn’t update any records so we know we’re done.</p><p>There are 2 groups in this example:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UVnoSNp_RrmBtYYBzCt-cg.png" /></figure><h4>Walk in a loop</h4><p>Using BigQuery’s scripts we can loop the query above. Note that in this example I nested the queries instead of using CTEs. Seeing it both ways may help to understand the recursive nature of this process. I also keep an iteration log to monitor performance.</p><p>You can limit iterations per run by changing the while predicate to (updates &gt; 0 and i &lt; max_iterations) or i = 0. It’ll start where you left off if you end up stopping and restarting it.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0d1177f988a7dc5c579c951c340fae5f/href">https://medium.com/media/0d1177f988a7dc5c579c951c340fae5f/href</a></iframe><p>I’ve run this on ~800 million records⁵ without issue. This method is able to handle some truly massive datasets.</p><h3>Results</h3><p>Use the following query to view the raw data in groups.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/127be039dd5526d8c0e89bdae45b7694/href">https://medium.com/media/127be039dd5526d8c0e89bdae45b7694/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*W8vIbIpw-ATlBNhpyEyTzg.png" /></figure><p>If you’d like to squash the group_id values, use the following query. If you are doing multiple runs and need stable group_id values, you must only squash group_ids &gt; the max from the previous run.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/439314d76ec639dd107bba9c426f4e78/href">https://medium.com/media/439314d76ec639dd107bba9c426f4e78/href</a></iframe><h3>Next Steps</h3><ul><li>Now that we’ve done deduplication, we’re ready to create <em>golden records</em> by squashing these multiple duplicate records into one, in a process called <a href="https://mdmlist.com/2019/08/22/three-master-data-survivorship-approaches/">survivorship</a>. BigQuery has some pretty excellent functionality for doing that too.</li><li>We could perform fuzzy matching via the join criteria in our edge query. We could also add edge weights and in our deduplication process we could sum the weights between 2 nodes to determine if it’s a true match.</li><li>The walk query can be optimized. You only have to update the group_id for a node_id that was updated in the previous round. If you add an iteration_id to the edge table, you can filter using this, or you can recreate a working table each round limited to the records you must consider. It’s more complex and error prone (you must consider <em>all</em> node_ids with changes from the previous iteration), but worth it if you have a huge dataset.</li><li>Build this into a <a href="https://www.getdbt.com/">DBT</a> macro.</li></ul><h3>Appendix</h3><h4>Seeding groups between multiple runs</h4><p>If you want a stable group_id between runs, you’ll just need to start with group_id values from previous run and seed new rows with values above the previous max. This works great if you never break a connection, but in real life you will. If you break groups you’ll need a separate process to handle this. In the past I’ve detected edge removal, then reseeded new group_ids for all nodes/edges in the affected group. If they were all in group 5, they’ll now be in two new groups — maybe 10 and 11, and group 5 will be gone. This is even more challenging if you use weighted edges.</p><h4>Using a graph database</h4><p>The deduplication process would be much simpler in a database like <a href="https://neo4j.com/product/neo4j-graph-database/">Neo4j</a>, but the data pipeline, training, and support would be significantly more complex. That said, if you’re doing a lot of group splitting, using weighted edges, or already have a Neo4j instance, it would make sense to consider this option.</p><h3>Footnotes</h3><p>[1]: Phone number is a bit sketchy. Normally you’d have some time threshold or additional piece of info you’d add to phone numbers to avoid spurious correlations.</p><p>[2]: We could just use the edge_id if we want, but I prefer to use row_number() to avoid massive negative numbers. We can always squash the results with a dense_rank() after we’re done.</p><p>[3]: You could adapt this process to work on any tabular SQL based dbms (like Snowflake). You could also <a href="#6653">use a graph database</a>.</p><p>[4]: farm_fingerprint() is used here for terse output. Hash collision likelihood is an example of the <a href="https://en.wikipedia.org/wiki/Birthday_problem">birthday problem</a>, so you’ll want to use a beefier hash function for large datasets. Check <a href="https://preshing.com/20110504/hash-collision-probabilities/#small-collision-probabilities">this</a> out for examples of hash size and collision likelihoods.</p><p>[5]: For 800 millions records FARM_FINGERPRINT would be insufficient. See [4] above.</p><h3>Disclaimer</h3><p>All code in my blog is meant for instructional purposes only. I make no guarantees of accuracy and if you choose to implement any of this, you do so at your own risk.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a3c5e78dec2b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Making a Python Linter from Scratch]]></title>
            <link>https://python.plainenglish.io/asts-and-making-a-python-linter-from-scratch-79e66e8d99b8?source=rss-f628cb8c61f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/79e66e8d99b8</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[computer-science]]></category>
            <dc:creator><![CDATA[Benjamin Campbell]]></dc:creator>
            <pubDate>Sun, 11 Apr 2021 20:47:11 GMT</pubDate>
            <atom:updated>2022-02-18T18:34:06.332Z</atom:updated>
            <content:encoded><![CDATA[<h4>How to develop a better understanding of ASTs by building our own Python linter from scratch</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lqSj5mNmqtQBzwe3blgVAg.png" /></figure><p>The goal of this story will be to give you a solid understanding of ASTs, a working example of a custom linter in Python, and demystify how code is reasoned about programmatically.</p><h3>ASTs</h3><p>One of the first steps in compiling code is converting it into an AST or <a href="https://en.wikipedia.org/wiki/Abstract_syntax_tree">Abstract Syntax Tree</a>. ASTs turn code into a tree/graph of functions. In the code example below you’ll see how to generate them for Python, in Python.</p><p>The next few sections deal with AST basics. If you have a solid understanding of them and would like to get right to the code, <a href="https://medium.com/p/79e66e8d99b8/#4a57">click here</a>. If you want to play with ASTs for a multitude of different languages, you can generate them online <a href="https://astexplorer.net/">here</a> although they’re quite verbose on that page.</p><h4>Expressions</h4><p>Consider the following expression:</p><pre>a and b and (c or (d and e))</pre><p>The AST would be something like:</p><pre>And(<br>  Variable(&quot;a&quot;),<br>  Variable(&quot;b&quot;),<br>  Or(<br>    Variable(&quot;c&quot;),<br>    And(<br>      Variable(&quot;d&quot;),<br>      Variable(&quot;e&quot;)<br>    )<br>  )<br>)</pre><p>…or as a graph:</p><figure><img alt="Boolean Operator AST" src="https://cdn-images-1.medium.com/max/960/1*hLL19m9SgsT6w-BMIbaeFg.png" /><figcaption>and(a, b, or(c, and(d, e)))</figcaption></figure><p>Notice there is no parenthesis operator since order of operations is obvious. Looking at this, you can probably imagine creating an optimizer. If any child of an and is false or an or is true we can bail. We can evaluate boolean operator inputs in any order, provided there are no dependencies between them. Most SQL query optimizers do this since they keep column statistics and are robust against null values. Most code doesn’t, since you often test for validity in the same boolean expression to avoid runtime errors. Think of testing for an instance of a class, to avoid null reference exceptions.</p><h4>Mathematics</h4><p>Here’s an example from mathematics</p><figure><img alt="\frac{zx²}{h} + 2y=0" src="https://cdn-images-1.medium.com/max/1024/1*l0hvODdRJr-JlPWZmlt8-Q.png" /></figure><pre>Equals(<br>  Sum(<br>    Fraction(<br>      numerator=Mult(<br>        Variable(&quot;z&quot;),<br>        Power(<br>          base=Variable(&quot;x&quot;),<br>          exponent=Constant(2)<br>        )<br>      ),<br>      denominator=Variable(&quot;h&quot;)<br>    ),<br>    Mult(<br>      Constant(2),<br>      Variable(&quot;y&quot;)<br>    )<br>  ),<br>  Constant(0)<br>)</pre><p>Note in the graph that some operators have their inputs labelled. That’s because these operators aren’t <a href="https://en.wikipedia.org/wiki/Commutative_property">commutative</a> while the rest are.</p><figure><img alt="Equation AST" src="https://cdn-images-1.medium.com/max/1024/1*F9ohjd5_a1hTQwFQRdVWbg.png" /></figure><p>You may be starting to realize how an equation solver would work. The root node of the left side of the Equals operator is a Sum operator. That means we need a Sum operator on the right if we’re going to move things over. We can wrap anything in a Sum(&lt;subtree&gt;, Constant(0)) without changing it. We can move any subtree between Sum siblings of an Equals operator parent by wrapping it in a Negate(...).</p><p>There are a ton of other rewrites we can do to this graph:</p><ul><li>A Fraction can be changed to a Mult(numerator, Reciprocal(denominator))</li><li>We can move a subtree between Mult siblings of an Equals by wrapping it in a Reciprocal(...)</li><li>We can remove a Sum operator if only 1 input differs from Constant(0)</li><li>We can remove a Mult operator if only 1 input differs fromConstant(1)</li><li>Sum nodes nested in Sum nodes can be flattened. This is the <a href="https://en.wikipedia.org/wiki/Associative_property">Associative Property</a> and works for Mult as well.</li><li>Sum children of Mult can be transformed to Mult children of Sum via the <a href="https://en.wikipedia.org/wiki/Distributive_property">Distributive Property</a>.</li><li>Graph examples are in the <a href="https://medium.com/p/79e66e8d99b8/#24b1">appendix</a>…</li></ul><p>You can probably see why equation solving can get complex since there are so many ways to transform this graph. <a href="https://en.wikipedia.org/wiki/Graph_rewriting">Graph rewriting</a> is an entire discipline and forms the foundation of <a href="https://writings.stephenwolfram.com/2020/04/finally-we-may-have-a-path-to-the-fundamental-theory-of-physics-and-its-beautiful/">Stephen Wolfram’s proposed fundamental theory of physics.</a></p><h4>Python code</h4><p>Now let’s look at an example of actual executable code:</p><pre>i = 0<br>while i &lt; 5<br>  i += 1</pre><pre>print(&quot;done&quot;)</pre><p>Get the AST as follows (You’ll need Python 3.9 to get the indent param on ast.dump):</p><pre>import ast</pre><pre>tree = ast.parse(&quot;&quot;&quot;<br>i = 0<br>while i &lt; 5:<br>  i += 1</pre><pre>print(&quot;done&quot;)<br>&quot;&quot;&quot;)</pre><pre>print(ast.dump(tree, indent=4))</pre><p>Output (simplified slightly but still a bit gnarly):</p><pre>Module(<br>    body=[<br>        Assign(<br>            target=Name(id=&#39;i&#39;),<br>            value=Constant(value=0)),<br>        While(<br>            test=Compare(<br>                left=Name(id=&#39;i&#39;),<br>                op=Lt(),<br>                right=Constant(value=5)),<br>            body=[<br>                AugAssign(<br>                    target=Name(id=&#39;i&#39;),<br>                    op=Add(),<br>                    value=Constant(value=1))),<br>        Call(<br>            func=Name(id=&#39;print&#39;),<br>                args=[<br>                Constant(value=&#39;done&#39;)])])</pre><p>…or as a graph:</p><figure><img alt="Simple Python Code AST" src="https://cdn-images-1.medium.com/max/1024/1*Gw-BA24_2Hccj9S-9w2EBw.png" /></figure><p>The first thing to note is how much more complex the AST is than the code and that’s a simplified version. Code can be thought of as shorthand.</p><h4>Let’s break it down</h4><p>The root node is a Module which has 1 parameter body, a list, containing 3 nodes which will be executed in sequence.</p><pre>Module(<br>    body=[<br>        Assign(),<br>        While(),<br>        Call()<br>    ]<br>)</pre><p>First, we assign a variable, then we run a while loop, then we call a function.</p><h4>Assign</h4><pre>Assign(<br>  target=Name(id=&#39;i&#39;, ctx=Store()),<br>  value=Constant(value=0)<br>)</pre><p>Assign takes 2 parameters, target — which is the variable i in this case, and value — which is the constant 0. Name is a variable in Python. You’ll notice that Name has a new parameter I left off the full AST. ctx means “context” and Name&#39;s are used in either a Load, Store, or Del context based on whether we’re storing a value, retrieving a value, or deleting from the names table.</p><h4>While</h4><pre>While(<br>  test=Compare(<br>    left=Name(id=&#39;i&#39;, ctx=Load()),<br>    ops=[Lt()],<br>    comparators=[Constant(value=5)]<br>  ),<br>  body=[<br>    AugAssign(<br>      target=Name(id=&#39;i&#39;, ctx=Store()),<br>      op=Add(),<br>      value=Constant(value=1)<br>    )<br>  ],<br>  or_else=[]<br>)</pre><p>Note that we now have a Load context example for our Name, and Compare has different parameters that in the full AST earlier. This is because Python allows comparisons like 1 &lt; x ≤ 6 unlike most languages where Compare works as before.</p><p>AugAssign stands for “Augmented Assign” — the += and -= operator class.</p><p>You’ll also see the or_else parameter for the While statement. If you’re not aware, while can have an else that will run if test is False but won’t run after a break statement.</p><h4>Call</h4><pre>Expr(<br>  Call(<br>    func=Name(id=&#39;print&#39;, ctx=Load()),<br>    args=[Constant(value=&#39;done&#39;)],<br>    keywords=[]<br>  )<br>)</pre><p>Call is actually wrapped in an Expr node. Per the docs, <a href="https://docs.python.org/3/library/ast.html#ast.Expr">when an expression, such as a function call, appears as a statement by itself with its return value not used or stored, it is wrapped in this container.</a></p><p>The only other difference is that you can see a Call takes akeywords list for args passed in the format something=&quot;value&quot;.</p><p>Additionally note that Call’s func argument takes a Name just like Assign. That’s a part of what is meant by “functions are first class objects”.</p><h3>Linter</h3><p>Now that we’re experts on ASTs we can start using them. To start interacting with an AST we will “visit” the tree recursively and accumulate information along the way. Thankfully, Python’s ast module makes this easy with the ast.NodeVisitor class.</p><p>The simplest NodeVisitor looks like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6aed74920a3d43d6ef16428e5711391c/href">https://medium.com/media/6aed74920a3d43d6ef16428e5711391c/href</a></iframe><p>a NodeVisitor will call visit_&lt;Type&gt;() for each node and will fall back to generic_visit if no such method exists. If you want to do something special for Name nodes, for instance, you would create a visit_Name(self, node) method in your visitor class. Just make sure to call self.generic_visit(node) if necessary at the end of custom visit methods to avoid unintended pruning.</p><p>First, let’s try out this generic visitor:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5adab610bfed4bbe3b5183f0e46cae8b/href">https://medium.com/media/5adab610bfed4bbe3b5183f0e46cae8b/href</a></iframe><p>The output is surprisingly noisy:</p><pre>Module<br>Assign<br>Name<br>Store<br>Constant<br>While<br>Compare<br>Name<br>Load<br>Lt<br>Constant<br>AugAssign<br>Name<br>Store<br>Add<br>Constant<br>Expr<br>Call<br>Name<br>Load<br>Constant</pre><p>For detecting globals, we only care about assignments outside a function or class scope. We can’t just loop through the Module.body though or we’ll miss global assignments in for, while, if, try, etc. One option is to short-circuit our visit to nodes that would create a non-global scope. That’s what I’ll do for this example.</p><p>We’ll also add an instance variable self.globals to accumulate globals as we find them.</p><pre>class globalsVisitor(ast.NodeVisitor):<br>  def __init__(self):<br>    self.globals = set()</pre><pre>  def visit_FunctionDef(self, node): pass<br>  def visit_AsyncFunctionDef(self, node): pass<br>  def visit_Lambda(self, node): pass<br>  def visit_ClassDef(self, node): pass<br>  def visit_comprehension(self, node): pass</pre><p>The last missing piece is retrieving the globals from assignment operators. This is slightly more complex than it would seem since i[0][1] = 5 is actually Assign(Subscript(Subscript(Name()))). Given the potential complexity of an assign target, we need to search its entire subtree for Name nodes.</p><p>The ast module makes this easy with ast.walk(node). walk gives us a flattened iterator containing all nodes in the subtree starting from node. Since Python has 3 assignment operators, we’ll create this helper method:</p><pre>def add_globals_from_subtree(self, node):<br>  for n in ast.walk(node):<br>    if type(n) is ast.Name:<br>      self.globals.add(n.id)</pre><p>Now all we need are the visit methods for the assignment operators:</p><pre>def visit_Assign(self, node):<br>  for t in node.targets:<br>    self.add_globals_from_subtree(t)</pre><pre>def visit_AugAssign(self, node):<br>  self.add_globals_from_subtree(node.target)</pre><pre>def visit_AnnAssign(self, node): #annotated assign - `i: int = 0`<br>  self.add_globals_from_subtree(node.target)</pre><p>Note we’re only adding globals from the targets of the assignment, not the value. If our use-case required visiting the descendants of the assign, we’d need to add self.generic_visit(node) to the end of each of these methods. The current implementation short-circuits our main visit just like the pass methods, but that’s fine for this use-case. In a fully featured linter we’d push scopes and use those to detect globals instead.</p><h4>Putting it all together</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d376708747e8fdbf879315e6f1de3ab4/href">https://medium.com/media/d376708747e8fdbf879315e6f1de3ab4/href</a></iframe><h4>Next steps</h4><p>If you enjoyed this and would like to dig deeper, check out the <a href="http://pylint.pycqa.org/en/latest/how_tos/custom_checkers.html#write-a-checker">pylint extension how-to</a>.</p><p>A more in-depth breakdown of Python’s ast.NodeVisitor is <a href="https://stackoverflow.com/questions/1515357/simple-example-of-how-to-use-ast-nodevisitor">here</a> and inspired a lot of my example.</p><p>pylint is powered by <a href="https://github.com/PyCQA/astroid">astroid</a> which adds scope framing, node traversal methods like node.parent and node.last_child, and many other features to the core ast objects. It’s definitely worth checking out and contributing to. I was especially intrigued by the <a href="https://github.com/PyCQA/astroid/blob/f2b197a4f8af0ceeddf435747a5c937c8632872a/astroid/as_string.py#L35-L610">AsStringVisitor</a> that turns an AST back into executable Python.</p><p>If you want to know more about how programming languages work, check out the absolutely excellent, free course <a href="https://www.nand2tetris.org/course">From Nand 2 Tetris</a>. Chapter 10 is the closest to what I’ve discussed here.</p><h3>Appendix</h3><h4>Generating graphviz diagrams from ASTs</h4><p>Assuming Mac, run this in a shell in a virtual environment:</p><pre>brew install gprof2dot<br>pip install graphviz<br>pip install astmokey</pre><p>Then run this Python script:</p><pre>import ast<br>from astmonkey import visitors, transformers</pre><pre>node = ast.parse(&quot;&quot;&quot;<br>i = 0<br>while i &lt; 5:<br>  i += 1<br>print(&quot;done&quot;)<br>&quot;&quot;&quot;)</pre><pre>node = transformers.ParentChildNodeTransformer().visit(node)<br>visitor = visitors.GraphNodeVisitor()<br>visitor.visit(node)</pre><pre>visitor.graph.write_png(&#39;graph.png&#39;)</pre><h4>Mathematical Identities as Graphs</h4><figure><img alt="Associative Property AST" src="https://cdn-images-1.medium.com/max/1024/1*z1cRjhTx9hge5o9BzCDlEg.png" /><figcaption>Sum(x, Sum(y, z)) == Sum(x, y, z)</figcaption></figure><figure><img alt="Distributive Property AST" src="https://cdn-images-1.medium.com/max/1024/1*yzN2dtu0_qXjoNijFvG-6w.png" /><figcaption>Mult(x, Sum(y, z)) == Sum(Mult(x, y), Mult(x, z))</figcaption></figure><figure><img alt="Sin Angle-Sum Identity AST" src="https://cdn-images-1.medium.com/max/1024/1*_RnYUM7D8Zg0lam_UDyXIw.png" /><figcaption>Sin(Sum(α, β)) == Sum(Mult(Sin(α), Cos(β)), Mult(Cos(α), Sin(β)))</figcaption></figure><h3>Disclaimer</h3><p>All code in my blog is meant for instructional purposes only. I make no guarantees of accuracy and if you choose to implement any of this, you do so at your own risk.</p><p><em>More content at </em><a href="https://plainenglish.io/"><strong><em>plainenglish.io</em></strong></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=79e66e8d99b8" width="1" height="1" alt=""><hr><p><a href="https://python.plainenglish.io/asts-and-making-a-python-linter-from-scratch-79e66e8d99b8">Making a Python Linter from Scratch</a> was originally published in <a href="https://python.plainenglish.io/">Python in Plain English</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Blockchain by Example in SQL Server]]></title>
            <link>https://benjaminsky.medium.com/blockchain-by-example-in-sql-server-8376b410128?source=rss-f628cb8c61f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/8376b410128</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[bitcoin]]></category>
            <category><![CDATA[sql-server]]></category>
            <dc:creator><![CDATA[Benjamin Campbell]]></dc:creator>
            <pubDate>Fri, 08 Dec 2017 01:20:48 GMT</pubDate>
            <atom:updated>2018-01-14T17:55:34.684Z</atom:updated>
            <content:encoded><![CDATA[<h4>A self-contained, private blockchain implemented within a basic messaging app in SQL Server.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*CcORimpRMYLAZGPkv-GcmQ.jpeg" /></figure><h4>Intro</h4><p>In this post I’m going to demonstrate how a blockchain works using nothing but SQL Server. I’m not suggesting this as an ideal implementation. I decided to make this demo self-contained since I’m focusing mostly on the schema and data, my target audience is database professionals, and SQL Server has all the required <a href="https://docs.microsoft.com/en-us/sql/t-sql/functions/cryptographic-functions-transact-sql">cryptographic functions</a>.</p><p>Probably the most well known use of a blockchain is Bitcoin and there are <a href="http://learnmeabitcoin.com/">tons</a> of <a href="http://blockchainsql.io/">resources</a> for learning how bitcoin works and for learning how <a href="https://bitcoin.stackexchange.com/questions/12427/can-someone-explain-how-the-bitcoin-blockchain-works">blockchains work</a>. In this example I’ll be starting with the basics and adding features incrementally.</p><h4>Definitions</h4><p>When people use the term <em>blockchain </em>they are generally talking about the Bitcoin blockchain. At its most basic, a blockchain is just rows of data that reference previous rows (a linked list) with a hash that contains the previous row’s hash. Bitcoin has additional features allowing it to be updated publicly, making it “trustless”. I’m going to start with the most simple implementation and build (almost) up to that.</p><p>First there are a few cryptography concepts you’ll want to be familiar with.</p><ul><li><a href="https://simple.wikipedia.org/wiki/Cryptographic_hash_function"><strong>Cryptographic Hash</strong></a> (specifically SHA256): A function that for a given input of any size outputs a deterministic, fixed length “signature”. It must be very sensitive to changes in the input, outputting a totally different, random looking signature for even a single bit change (the <a href="https://simple.wikipedia.org/wiki/Avalanche_effect">avalanche effect</a><strong>)</strong>. It also must be fast to compute, free of collisions (2 different inputs giving the same output), and non-reversible (can’t determine the input form the output). Try it out <a href="http://www.xorbin.com/tools/sha256-hash-calculator">here</a>.</li></ul><p>SHA256(&quot;Hello&quot;) = 0x185f8db32271…</p><p>SHA256(&quot;Hello!&quot;) = 0x334d016f755c…</p><ul><li><a href="https://en.wikipedia.org/wiki/Public-key_cryptography"><strong>Public or Asymmetric Key Cryptography</strong></a><strong>: </strong>An encryption method using 2 keys where the key used to encrypt a message (the public key) is different from the key used to decrypt it (the private key). Think of the public key as a lock and the private key as a key to that lock. I can put a huge pile of these locks out in the middle of a public place and you grab one, write me a private message, put it in a box, and lock it with my lock. Now you can leave the locked box out in public or have anyone deliver it to me, even someone you don’t trust. No one can open it but me, not even you. These key pairs can also be used to sign messages. I sign it with my private key and you can confirm that I signed it using my public key but are unable to forge my signature since you lack my private key. Bitcoin uses public key crypto to secure the coins so only the person with the right private key can spend them. I’ll use asymmetric key encryption in my example as an alternative to mining and distributed trust by signing blocks instead of hashing them.</li><li><a href="https://en.wikipedia.org/wiki/Cryptographic_nonce"><strong>Nonce</strong></a><strong>: </strong>A meaningless piece of information for one-time use. In the case of a blockchain the nonce is used to mine blocks. The nonce gives the miner control over part of the data being hashed allowing them to change the hash in an attempt to create one with special properties, in this case a value below a certain threshold. Mining is really just randomly picking integer values for the nonce and rehashing everything until you “win the lottery” getting a hash low enough (starts with a bunch of zeroes). Check it out below. In the first example I computed the hash of my data without the nonce and then after trying 2,081,747 values I won the hash lottery and got a low enough hash value.</li></ul><p>SHA256(&quot;Hello!&quot;) = 0x334d016f755c…</p><p>SHA256(&quot;Hello!|Nonce=2081747&quot;) = 0x0000048817E2…</p><ul><li><a href="https://en.wikipedia.org/wiki/Merkle_tree"><strong>Merkle Tree</strong></a><strong>: </strong>A binary tree of hashes, the leaves being data blocks, allowing you to check quickly if a certain leaf is valid even if there are many leaf nodes. This is very similar to an index seek but for validation rather than retrieval. Another good explanation <a href="https://seebitcoin.com/2016/09/what-on-earth-is-a-merkle-tree-part-2-i-get-more-technical-but-hopefully-all-becomes-clearer/">here</a>.</li><li><strong>Block/Blockchain</strong>: This isn’t technically a cryptography concept but it may help to explicitly define what a block and a blockchain actually is. A block in a blockchain is a row of data that contains a hash of some underlying data (like a group of ledger transactions), a reference to the prior block and its hash(except for the first or “genesis” block), and a hash of all the data in the row. In any implementation the block has more features but at its core these fields give a block its ability to guarantee the trustworthiness of the content and order of some underlying data. In my example and in Bitcoin the <em>MerkleRoot</em> field is the <em>UnderlyingDataHash</em> and we also have a <em>TransactionCount, Version, </em>and <em>CreatedDateTime</em>. In a public blockchain you’ll need <em>Nonce </em>and<em> Difficulty </em>fields to do the mining (and the <em>BlockHash</em> will start with zeroes). In a private blockchain <em>BlockHash</em> can be replaced with a <em>BlockSignature</em> using public key encryption instead of a mined SHA256 hash since there is only one party writing to the table. For what in my opinion is the best diagram check out “Merkle Proofs in Bitcoin” <a href="https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/">here</a>.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nU6NNSfX1XCAjsosvYGoow.png" /></figure><h4>Getting Started</h4><p>Blockchains can be used to protect the order and integrity of any type of transaction. While the obvious use-case is cryptocurrencies I’ve decided to create a demo using a messaging app. With each iteration of the code a demo.sql file will change allowing you to try out certain scenarios.</p><h4>Existing App (<a href="https://github.com/benjaminsky/BlockchainMessenger/tree/ExistingApp">Code Here</a>)</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xto4_GlkRzLNQ2YmYjp94Q.png" /></figure><p>This is the most basic messaging app I could think up. We have users that can send messages with a subject and a body to one another. We also track when the message was read. <em>MessageID</em> is sequential.</p><h4>Upgrade 1 — The Most Basic Blockchain (<a href="https://github.com/benjaminsky/BlockchainMessenger/tree/Upgrade1">Code Here</a>)</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ByuaTiCtRsx3ngFAnIYftg.png" /></figure><p>All we did is add 4 columns to the <em>Message</em> table. Each message is also a block.</p><ul><li><strong>MessageHash</strong>: A SHA256 hash of all the fields in the table with the exception of <em>ReadDateTime</em> since it can be updated.</li><li><strong>HashVersion</strong>: An INT telling us the version of the logic used to concatenate field values into a delimited string. If this field wasn’t there, we could never add fields to this table or fix bugs in the hash logic. This allows backward compatibility when verifying old rows.</li><li><strong>PrevMessageID</strong>: References the message prior to this one. Note that I’m assuming the MessageID is sequential. There is a unique index on this field so there can only be one NULL (the first block, also called the genesis block) and one child per parent. This creates the “chain” with messages as blocks.</li><li><strong>PrevMessageHash</strong>: This is the <em>MessageHash</em> from the row referenced by <em>PrevMessageID</em>. This value is included in the current message’s hash. This means that all prior data is rolled up into this single hash. If someone were to alter anything in the past they’d have to redo all hashes from that message forward.</li></ul><p><strong>So what did that get us? </strong>When a user creates a message in our system we can return the <em>MessageHash </em>as a receipt. The user can use this to ensure that all message data and the order of messages in the system haven’t been tampered with up to this point. They’d need a trusted third party to verify this like an auditor. A third party could rehash all the messages and ensure all hashes match all receipts if needed. If any data corruption or manipulation occurs they’d be able to catch it.</p><p>The big win here is that we have a single BINARY(32) value that is a fingerprint of all the data in our system including its order. The hash will change if anything it protects is changed.</p><p><strong>What are we lacking? </strong>We can’t protect the <em>ReadDateTime</em> or any other future updateable field since you can’t change the hash once a new message is written without changing all the subsequent hashes.</p><p>Also, users need to keep those hash receipts or there’s no way to verify anything. A hacker or a bad admin at our firm could update all the hashes and it’d be your word against ours. For this to be robust we’d need some trusted third party to hold all our message hashes and verify messages if needed which would get tedious.</p><h4>Upgrade 2 — Transaction Table (<a href="https://github.com/benjaminsky/BlockchainMessenger/tree/Upgrade2">Code Here</a>)</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/958/1*pYK2EmFpoQHgeghwroG06g.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*A7K6yMFjaIVJ0PpBK-NWFg.png" /><figcaption>TransactionType lookup table</figcaption></figure><p>The <em>Message </em>table is back to its original schema, we’ve moved the chaining and hashing fields (<em>TransactionHash</em>, <em>HashVersion</em>, <em>PrevTransactionID</em>, <em>PrevTransactionHash</em>) to the <em>Transaction</em> table, and added a <em>TransactionType</em>. Finally <em>MessageID</em> references the message we’re protecting whether it’s the entire message, a mark read, or mark unread event. <em>TransactionHash </em>for message sends is still computed from data in the <em>Message</em> table (in addition to necessary <em>Transaction</em> fields) but read and unread transactions are just hashes of the <em>MessageID, </em>the <em>TransactionDateTime</em>, and the<em> PrevTransactionHash</em>.</p><p><strong>Now what do we have?</strong></p><p>We can now protect any updates and can even protect things other than messages if we add another table and FK field in <em>Transaction</em>.</p><p><strong>What are we lacking?</strong></p><p>We still have the same problems requiring third party verification. If we wanted to eliminate the need for third party verification we’ll need to either mine the blocks or sign them. We also have a tight 1:1 coupling between blocks and transactions. This will cause major scaling problems once we introduce signatures and/or mining.</p><h4>Upgrade 3 — Block Table (<a href="https://github.com/benjaminsky/BlockchainMessenger/tree/Upgrade3">Code Here</a>)</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*g4nZqta1Ab0zpotquUy7Hg.png" /></figure><p>Chaining is moved to the <em>Block </em>table but <em>Transactions</em> still store their own hashes. <em>BlockID</em> has been added to <em>Transaction</em> allowing many transactions to be rolled into the same block. <em>BlockID</em> and <em>PrevBlockID</em> now form our chain. <em>TransactionCount</em> is just an aggregate from the <em>Transaction</em> table. While this may look like bad normalization, we want to protect the count in the hash so we explicitly store this to speed up verification. Instead of hashes we use signatures on the blocks (<em>BlockSignature</em>, <em>PrevBlockSignature</em>, and <em>SignatureVersion </em>replace<em> Hash</em>,<em> PrevHash</em>, and <em>HashVersion </em>fields). There are a few new concepts added to this table.</p><ul><li>Signatures on blocks instead of hashes</li><li><em>Nonce</em> — for mining even though we technically don’t need to mine when using signatures</li><li><em>MerkleRoot</em> — the root of the merkle tree of transaction hashes defined above</li></ul><p><strong>Signatures</strong>: Using signatures is a departure from Bitcoin. In the Bitcoin block table they still use hashes. Earlier, in my definition of public key crypto, I talked about how I’d use signatures as an alternative to mining. This is where that becomes important. That signature is created using the private key portion of an X.509 certificate. Trustworthiness of the block comes from your ability to protect your private key instead of the proof of work from the hash value itself. Verification is simple. Either you could register your cert with a certificate authority or just distribute the public key yourself. Anyone can safely be granted access to the signatures and public key. This allows confirmation that you signed a given block. As long as you keep the key safe (and out of SQL Server) you’re protected against hackers and rouge admins. In this example the entire cert (public and private keys) lives in SQL Server for simplicity. In real life you’d use a key vault and do the signing with whatever client is writing the block. Neither devs nor DBAs would have access to the private key or the vault. However, you’d still want to have the public key in SQL Server to allow you to quickly verify blocks at rest.</p><p><strong>Nonce</strong>: The nonce is just an int that we can change in an attempt to get a special signature value. Changing this field and redoing the hash (or for our example, the signature) is what mining is. This is also referred to as a “proof of work” since the only way to discover this special value is through brute force. You’ll see in my example that I chose random values for the Nonce but in real life you’d just want to increment it. This is because incrementing is faster, dupe free, and no two miners will get the same hash since they include a transaction paying themselves the reward. In Bitcoin the target time between additions of blocks is 10 minutes. If miners regularly beat that time (using a 2 week moving average) the difficulty goes up (the number of zeroes required at the start of the hash/signature goes up) and if they lag behind the difficulty is reduced. When you add the next block you get a reward which decreases over time but is currently around 13 bitcoins in addition to a small transaction fee added to each transaction to entice miners to add it to their current block. At $10,000 per Bitcoin that’s some good money! There’s a reason Bitcoin mining <a href="https://futurism.com/mining-bitcoin-costs-more-energy-159-countries-consume-year/">uses more electricity</a> than many small countries. If someone wanted to update data they’d need to mine all their own blocks in order to get them accepted. Anything altered in the past would require re-mining all blocks that followed. That’s why old block are more trustworthy. There is a ton of proven work following them that increases with each new block.</p><p>Here’s some super basic mining code:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a2c0583779206661fd7be68e4ddf156b/href">https://medium.com/media/a2c0583779206661fd7be68e4ddf156b/href</a></iframe><p><strong>MerkleRoot</strong>: This is the root of a binary tree of all the underlying <em>TransactionHash</em>es from the <em>Transaction</em> table. The reason we don’t just hash all the individual transaction hashes in a straight line is to allow us to verify a single transaction quickly (log(N) hash computations, N being the transaction count). In this version of the code, intermediate merkle nodes are added as additional transactions with a special <em>TransactionType </em>and their order is very important since they actually form a tree. This is how Bitcoin works but in the next upgrade, I’ll split the intermediate nodes and add a <em>Depth</em> field out to speed up verification and better demonstrate their function.</p><p><strong>Branching</strong>: I left this concept out of my block table but it’s worth discussing. Bitcoin has a <em>BranchID</em> field which allows for cases where 2 people mine the next block at the same time. This is rare but does happen. When that happens, 2 blocks with the same parent are created. If there’s ever a branch all clients are instructed to follow the path with the most work (the lowest hash value). Note that the hashes will never be the same since miners also add a transaction paying themselves the mining reward before they mine. The chances that the next block after a branch will be mined simultaneously is even more rare and once it is added, more and more people will start mining against that branch and the loser will be abandoned. Anyway, with a private blockchain, mining is an optional security enhancement and you don’t need branching.</p><h4>Upgrade 4 — Intermediate Merkle Node Table and Verification Proc (<a href="https://github.com/benjaminsky/BlockchainMessenger/tree/Upgrade4">Code Here</a>)</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FEGpmGqqtnoBYx8X-Z1FaQ.png" /></figure><p>Here I’ve added a table to store the merkle nodes. These are no longer added to the <em>Transaction</em> table. I’ve also added a proc to verify a given transaction by climbing down the merkle tree. Each <em>NodeHash</em> is eitherSHA256(TransactionID1 + TransactionID2) for Depth == 1 or SHA256(MerkleTreeIntermediateNodeID1 + MerkleTreeIntermediateNodeID2). <em>Depth</em> tells you how many hops you are from a a leaf with leaves being Depth == 0. This doesn’t add any features we didn’t have before but it’s perhaps better normalization and it makes verification much easier. Check out demo.sql and the inner workings of [dbo].[TransactionVerify].</p><h4>Conclusion</h4><p>That’s it, a self-contained, private blockchain implemented on a basic messaging app. You could use it on a ledger, state machine, contract, on-boarding process, or anything else where you want to provide independent verifyablility of data integrity and order.</p><p>Let me know if there’s anything else you’d like to see in this example and feel free to ask any questions you may have.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8376b410128" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Populating Lookup Tables in SQL Server DataTools (SSDT)]]></title>
            <link>https://benjaminsky.medium.com/populating-lookup-tables-in-ssdt-a5e09efbd02?source=rss-f628cb8c61f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/a5e09efbd02</guid>
            <category><![CDATA[lookup-table]]></category>
            <category><![CDATA[sql-server]]></category>
            <category><![CDATA[visual-studio]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[ssdt]]></category>
            <dc:creator><![CDATA[Benjamin Campbell]]></dc:creator>
            <pubDate>Mon, 20 Nov 2017 23:06:21 GMT</pubDate>
            <atom:updated>2017-12-15T16:51:53.143Z</atom:updated>
            <content:encoded><![CDATA[<h4>Lookup data never really felt like data to me</h4><h4>Definitions</h4><p><strong>Lookup Table:</strong> A table with 2 fields at a minimum, a <a href="https://www.techrepublic.com/article/the-great-primary-key-debate/">meaningless primary key</a> and a text value used in normalization to avoid repeating textual values and referenced by foreign keys in other tables. I’ve also heard them called <em>Reference Tables</em>, and <em>Domain Tables. </em>These tables are not changed during the normal course of business (unlike something like ProductCategory which looks the same but I’d argue isn’t a lookup table). This is my definition so don’t take this as gospel.</p><p>Examples</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IydoT9KNSI3OhphKh0czqw.png" /><figcaption>State table could go either way. That could be maintained by your application.</figcaption></figure><p><a href="https://msdn.microsoft.com/en-us/library/hh272686(v=vs.103).aspx"><strong>SQL Server Data Tools</strong></a><strong> (SSDT):</strong> Functionality for developing, testing, deploying, and refactoring SQL Server databases in Visual Studio that doesn’t require change script creation. Development is done simply by defining the desired final state of the database and deployment is done by comparing the schema in the project with the schema in the deployment target.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*d7DTEIBnlXdcxiPOyrcbiw.png" /><figcaption>SQL Server Data Tools — Table Editor UI</figcaption></figure><h4>Is Lookup Table Data Really Data?</h4><p>Think of the corresponding code. It’s usually an enum, right? Sometimes you’ll implement this as class and load lookup data from the database to avoid hard coding this twice but you’re looking for enum-like functionality. Here are a few more tests…</p><ul><li>Would your app function if these tables were empty? I doubt it unless you aren’t using foreign keys (which warrants a whole other post).</li><li>Would a “blank” copy of the database be complete without this data?</li><li>Do they change without a corresponding code push?</li></ul><p>Ok, I’m feeling pretty comfortable that we’re dealing with a really special type of data that sure feels a lot like schema. Now what? We have to get it source controlled and deployed.</p><h4>Source controlling lookup table data in SSDT</h4><p>The beauty of SSDT is that we create a declarative model of what a target database should become after a deployment regardless of its current state. We want lookup table data to be treated the same way both in source control and during deployment.</p><h4>Example</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/91f04b38bb386c3d8b9218663d24e8bb/href">https://medium.com/media/91f04b38bb386c3d8b9218663d24e8bb/href</a></iframe><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fb5bacdbc9caecbf695728408fcf2e55/href">https://medium.com/media/fb5bacdbc9caecbf695728408fcf2e55/href</a></iframe><h4>A couple things you may notice…</h4><p>Lines 5–10 represent the data that is the desired final state of the lookup table</p><p>Lines 13–15 are ensuring that we only do an update when something really changed. Lines 13–14 demonstrate the predicate for NOT NULL fields and line 15 demonstrates the predicate for a NULL field. If you’ve used entity framework you may be familiar with this logic. It allows NULL == NULL == true tests. While this section isn’t technically necessary, it’s nice to have so you can see (0 row(s) affected) when you run this script against a target table that matches it.</p><p>This script is verbose. To create it by hand would be error-prone. I use a script that auto-generates it from metadata and data already in the table. Initially, on large existing DBs I’m migrating to SSDT, I use a PowerShell script that leverages extended properties to identify the lookup tables, creates all of these scripts in the correct order by doing a depth first search of the FK dependency graph, and assumes you’re always creating data rather than deleting it (since deletes have to happen in the opposite order. Think Category and SubCategory.) I may publish these scripts at a future time but they’re not really ready for dissemination yet. What I’d really love to see is lookup tables, including imports of existing ones, as a first-class feature of SSDT!</p><h4>Deployment</h4><p>We want to deploy these using a post deployment script. Since you can only have one, I use the following setup:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/924/1*ieI6AxHKfB-voo6LzbZJkA.png" /><figcaption>Script.PostDeployment.sql</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/308/1*QwbKSDNiB7Gm6GXmZakJqA.png" /><figcaption>Solution Explorer</figcaption></figure><p>Create Script.PostDeployment.sql as Post-Deployment Script. All lookup table scripts, add as Script (Not in Build) to avoid compile time debugging and ensure they all end in GO.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/642/1*u3aI4iJ9x2W1aHrqM5sR0w.png" /><figcaption>Types of Scripts</figcaption></figure><p>If you accidentally create the wrong type of script and you’re getting errors, you can change Build Action to None in properties:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/492/1*D3lHghAvXlK0wYnu-EyHXg.png" /></figure><p>You can also create stored procedures to populate the lookup tables to keep your publish.sql scripts nice and tidy.</p><h4>Caveats</h4><ul><li>This will fail in cases where you end up deleting lookup table rows that are referenced by a foreign key in another table. This may happen during a rollback scenario and will require you to disable foreign keys or manually intervene prior to running the scripts unless you have cascading deletes turned on (which I wouldn’t do).</li><li>You’ll also have failures when two teams are using the same DB in dev and deploying from their branches without merging them first.</li></ul><p>Both of the above caveats can be avoided with the right processes in place.</p><h4>Thoughts?</h4><p>How do you do it? Does anyone out there have a better way?</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a5e09efbd02" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>