Governments have initiated national programs to make government data publicly available with the purpose of improving transparency and making it easier for general public to access information of interest about many aspects of their countries. Thousands of datasets are being continuously published in Open Government Data Portals (OGDP) for public use, which makes them an attractive data repository for researchers to study data integration problem. One common application of data integration is join operation to expand a table with additional columns, for which many studies have been proposed in the literature. However, usefulness of end result after joining of potential table pairs is under-explored, especially considering heterogeneous nature of OGDPs. To this end, we analyze joinability of tables based on high value overlap in several, English-speaking OGDPs; Canada, Singapore, UK, and US. Our analysis reveals that mainly due to high value repetition and nonexistence of key columns, vast majority of the joinable table pairs are accidental, resulting in uninterpretable tables.
The launch of OGDPs, such as data.gov, open.canada.ca, or data.gov.in, has popularized the open data movement of the last decade. The overarching vision of OGDPs is to make governments transparent so that journalists, policy analysts, researchers, and the general public can easily monitor how their societies are functioning. Achieving this vision requires developing additional tools and applications over these datasets to discover, understand, link, and integrate them. Excitingly, these are some of the core research problems that interest the database and information retrieval communities, and as such OGDPs have become some of the most popular data repositories (aka data lakes) to study [1, 2, 3, 4, 5, 6, 7, 8, 9].
around open datasets is to understand the properties of these datasets. Previous empirical studies have focused on analyzing either the metadata on the webpages that publish these datasets [10, 11], or detailed technical aspects of the files that store these datasets, such as the Singapore(SG) [14], UK(UK) [15], and USA(US) [16]. In our large scale analysis, our main findings are as follows: • Tables exhibit high-degree of denormalization regarding the perspective of data design; high value repetition, plethora of functional dependencies (FD), absence of key and more importantly identifying columns, and prevalence of multi-attribute composite keys. • We found out that the denormalized nature of tables has significant implications on data integration operations such as join. Overwhelming majority of joinable pairs, even with a conservative, value-overlappingbased approach, are accidental, i.e., useless. The joins happen mostly between non-key columns, resulting in significantly bigger tables in rows which is contrary to most common join case exercised in relational databases, that is to expand a table with a column.
1https://ckan.org/ bles with additional columns. For those tables that do not have a key column, we searched for all possible 2-size and 3-size candidate keys. The distribution of the minimum candidate key columns of the tables are depicted in Figure 2.
A very large number of tables, 58%, 53%, 50%, and 33% in SG, CA, UK, and US, respectively, do not have any single key columns. Therefore data systems, such as search engines that index records, may need to find composite keys to identify majority of the records in some portals. Furthermore, 10% of the tables across all portals do not have a candidate key of size 1, 2, or 3, which indicates the extent of denormalization and value repetitions in these portals.
OGDPs. Recall that an FD [17] in a table is an expression → where ⊆ ( ) and ∈ ( ) , which informally indicates that a specific set of values imply the same values in . Formally, → holds if Figure 2: Distribution of candidate key sizes. for any pairs of tuples , ∈ if [ ] = [ ] , then column are mostly accidental due to either columns [] = [] . → is trivial if ⊆ or if forms having the same domain from tables with irrelevant candidate key. It is well known that existence of noncontext or key but non-identifying columns. trivial FDs indicates poor relation design and leads to value repetitions that can be avoided by decomposing the relation into Boyce Codd normal form (BCNF). In 2. Analysis the rest of this section, LHS and RHS stand for the leftand right-hand side of an FD, respectively. While all our 2.1. Normalization Analysis previous analyses used all datasets in each OGDP, our next analyses on composite keys and FDs require super2.1.1. Uniqueness and Key Column Analysis linear computations and for these we used tables with For a column , let ’s uniqueness score be |() | , which 10 ≤ ≤ 10000 tuples and 5 ≤ ≤ 20 columns. The final | | number of tables along with some other statistics from is the ratio of the number of unique values vs number the sample are provided in Table 1. of values in (the latter is equivalent to the number of To find FDs in tables, we implemented the FUN algorows in the table belongs to). Distributions of number rithm for finding FDs [ 18] and limited the algorithm to of unique value counts and uniqueness scores of columns ifnd FDs whose LHS contain at most 4 attributes. Table 1 are depicted in Figure 1. We also recorded the median shows the percentages of the tables for which we found unique value counts for all portals, which are 10, 23, 10, at least 1 FD across all portals. and 30 for SG, CA, UK, and US, respectively. Majority of tables in each portal, and overwhelming majorThere is a very high degree of value repetition across all ity in UK (84.05%) and US (79.86%), have non-trivial FDs. portals. Almost half of the columns for all the portals have These percentages indicate that most of the table published equal to or less than 20 unique value, which consequently by OGDPs are not in Boyce Codd normal form, so up to leads into non-descriptive columns with significantly low the common normalization standards of relational tables uniqueness scores. For instance, 51% and 41% of the columns in practice. in US and CA, respectively, have smaller than 0.1 unique- Finally, we note that in most of the tables, the FDs have ness score, i.e., each value in these columns are on average a simple structure where a single attribute on the LHS repeated more than 10 times. implies columns on the RHS. Such FDs indicate a direct
We next analyze the distributions of key columns. A dependency between two columns in a table. A classic column with uniqueness score of 1.0 is a key column. example of such FD is → , which is prevaKey columns are desirable as they help identify a table’s lent in the Canadian portal. As shown in Table 1 (“tables records. Furthermore, in data integration, joins of two with a non-trivial FD s.t |LHS|=1” lines), the majority of tables on two key columns lead to non-growing joins, the tables that have a non-trivial FD has a non-trivial FD which are desirable as they efectively extend these ta- in this simple form. 2.2. Joinability Analysis columns ( , on two criteria: , ,
Throughout our analyses, we define joinable pairs as quadruplets ( , , , ), where ( , ) are found to be join able tables through the pair of joinable columns ( Similar to many prior studies [1, 19, 20, 4, 21, 22], we consider an equi-join operation. We use Jaccard similarity as a metric of joinability, since in terms of precision it is regarded as highly efective [ 21, 22]. We used all available tables from each portal and picked all joinable pairs within the same portal, i.e., pairs of tables and joinable , ).
) and filtered out joinable pairs based • High Jaccard similarity: Since our overall goal is to analyze useful joinable pairs, we wanted the resulting joins to not filter many tuples from the tables and picked pairs only if their join columns had very high, at least 0.9, Jaccard similarity value. • High unique values: We selected pairs only if their columns had at least 10 unique values. Very small domains tend to have high value repetitions and lead to very large join outputs, which we assumed are not useful in data integration operations.
11.9% (UK) to 17.8% (US) of the columns have another column they are joinable with, of which only 17.9% (US) to 24.3% (UK) were key columns. We manually analyzed some tables and columns with high-degree joinability and observed three patterns: • Tables with the same schema: There are large sets of tables that have the same or almost the same schema, e.g., because these are periodically published tables, which refers to publication style prevalent in OGDPs to store information weekly, monthly, annually. These tables tend to have many columns that have exactly the same domain and tend to be all pairwise joinable. • Tables in the same dataset: Another common publication style in OGDPs is to have multiple tables storing information about diferent aspects about an entity, which we refer to as semi-normalized tables. The schemas of these tables tend to be diferent but still have common columns with significant value overlaps. These tables can be seen as normalized versions of a larger table yet can still exhibit FDs. • Common non-descriptive columns: Some columns, such as state or year, exist in many tables and lead to high joinability degrees.
i.e., expansion ratio of the joins, which we define as: output size of the join / the size of the larger table.
picted as letter-value plots in Figure 3. The biggest box in each distribution represents values between the 1st and 3rd quartiles. Vertical line in the biggest box represents median expansion ratios, which we
Table 3 shows the overall frequencies of the labels we found as 1 for CA and UK, 2 for SG and 24 for US. As gave across portals. As we hypothesized, overwhelming shown in the plot, except in SG, very large fractions majority of the joinable pairs we sampled, whose columns of joinable pairs grow significantly, often beyond 10. had close-to-perfect value overlaps are accidental, i.e., For example in the US, the majority grows beyond 24 false positives. The frequency ranges between 80.8% and and there are at least 25% of the pairs that have an 86.7% across portals (and 100% in SG). Our results indicate expansion ratio of above 100. that value overlap alone can be a weak signal of useful Although it is not possible to infer whether a particu- joins and applications ofering join feature need to be lar join is useful only by inspecting its expansion ratio, more selective in the tables they suggest to users. perhaps the most common motivating case for joins In what follows, we list possible remediation strategies is to extend one table with a new column, without for avoiding U-Acc and R-Acc pairs, respectively: growing the table at all, e.g., to add a new property of an entity in a table as a new column. If the expansion rate of a join is very high it is safe to assume that the joins are accidental. • In order to avoid U-Acc pairs, tools must take the context of the tables forming the join into account as well instead of solely relying on column similarity, for which some metadata properties of datasets such as description or subject can be utilized, if available.
Another alternative is to limit candidate joinable tables to be within the same dataset given the query table to ensure the same context, as exercised in a recent work [9]. • We argue that avoiding R-Acc pairs is what makes the problem of finding useful joinable pairs more challenging, which can be a future research direction to explore. Besides, uniqueness score of the columns and expansion ratio of a prospective join can be leveraged as heuristics. However, such heuristics standalone may not accurately predict usefulness for certain cases, since they do not address the problem of ifnding joins through identifying columns, which is yet another research direction that can be delved into.
SG due to common publication practice skewing the sample) from all of the pairs, and manually labeled them as accidental vs useful 2. For the sample, we omit pairs with the same schema (i.e., list of column names), since these dominate the joinable space and are better candidates for union operation. We categorized the tables into 3 as follows: • Unrelated Tables and Accidental (U-Acc): These are the clear false positive pairs of tables that come from completely diferent domains (e.g., crime vs health) and happen to have columns with high value overlaps. • Related Tables and Accidental (R-Acc): These are pairs that originate from the tables storing same or similar information in a same context (e.g., health), but the join is accidental because the join’s output does not have a clear interpretation. Often, this happens because the join is on columns that do not represent the main entities but some other property of
searchers and developers that develop data systems over OGDPs about normalization properties of the tabular datasets and their impact in join operation in these portals. Our analysis reveals that tabular datasets published 2For reference, the final pairs we used along with their by OGDPs have unique characteristics that play role leadannotated labels can be found at https://github.com/ ing into false positive joins, which should be remedied arifusta/ogdpAnalysis by embracing more selective join candidates. Web Conference, WWW ’19, Association for Computing Machinery, New York, NY, USA, 2019, p. [1] E. Zhu, F. Nargesian, K. Q. Pu, R. J. Miller, Lsh 1365–1375. URL: https://doi.org/10.1145/3308558. ensemble: Internet-scale domain search, arXiv 3313685. doi:1 0 . 1 1 4 5 / 3 3 0 8 5 5 8 . 3 3 1 3 6 8 5 . preprint arXiv:1603.07410 (2016). [11] S. Neumaier, J. Umbrich, A. Polleres, Automated [2] F. Nargesian, E. Zhu, K. Q. Pu, R. J. Miller, Table quality assessment of metadata across open data union search on open data, Proceedings of the portals, J. Data and Information Quality 8 (2016).
VLDB Endowment 11 (2018) 813–825. URL: https://doi.org/10.1145/2964909. doi:1 0 . 1 1 4 5 / [3] E. Zhu, D. Deng, F. Nargesian, R. J. Miller, Josie: 2 9 6 4 9 0 9 .
Overlap set similarity search for finding joinable [12] J. Mitlöhner, S. Neumaier, J. Umbrich, A. Polleres, tables in data lakes, in: Proceedings of the 2019 Characteristics of Open Data CSV Files, in: 2016 International Conference on Management of Data, 2nd International Conference on Open and Big Data 2019, pp. 847–864. (OBD), IEEE, 2016, pp. 72–79. [4] A. Bogatu, A. A. Fernandes, N. W. Paton, N. Kon- [13] Canada’s open government data portal, https:// stantinou, Dataset discovery in data lakes, in: 2020 open.canada.ca/en/open-data, 2023. IEEE 36th International Conference on Data Engi- [14] Singapore’s open government data portal, https: neering (ICDE), IEEE, 2020, pp. 709–720. //data.gov.sg/, 2023. [5] O. Benjelloun, S. Chen, N. Noy, Google dataset [15] Uk’s open government data portal, https://www. search by the numbers, in: The Semantic data.gov.uk/, 2023.
Web – ISWC 2020: 19th International Seman- [16] Usa’s open government data portal, https://data. tic Web Conference, Athens, Greece, Novem- gov/, 2023. ber 2–6, 2020, Proceedings, Part II, Springer- [17] H. Garcia-Molina, J. Widom, J. D. Ullman, Database Verlag, Berlin, Heidelberg, 2020, p. 667–682. System Implementation, Prentice-Hall, Inc., USA, URL: https://doi.org/10.1007/978-3-030-62466-8_41. 1999.
doi:1 0 . 1 0 0 7 / 9 7 8 - 3 - 0 3 0 - 6 2 4 6 6 - 8 _ 4 1 . [18] N. Novelli, R. Cicchetti, Fun: An eficient algorithm [6] S. Castelo, R. Rampin, A. Santos, A. Bessa, F. Chiri- for mining functional and embedded dependencies, gati, J. Freire, Auctus: A dataset search en- in: International Conference on Database Theory, gine for data discovery and augmentation, Proc. Springer, 2001, pp. 189–203.
VLDB Endow. 14 (2021) 2791–2794. URL: https: [19] D. Deng, A. Kim, S. Madden, M. Stonebraker, Silk//doi.org/10.14778/3476311.3476346. doi:1 0 . 1 4 7 7 8 / moth: An eficient method for finding related sets 3 4 7 6 3 1 1 . 3 4 7 6 3 4 6 . with maximum matching constraints, Proc. VLDB [7] A. Khatiwada, G. Fan, R. Shraga, Z. Chen, W. Gat- Endow. 10 (2017) 1082–1093. doi:1 0 . 1 4 7 7 8 / 3 1 1 5 4 0 4 . terbauer, R. J. Miller, M. Riedewald, Santos: 3 1 1 5 4 1 3 .
Relationship-based semantic table union search, [20] R. C. Fernandez, Z. Abedjan, F. Koko, G. Yuan, Proc. ACM Manag. Data 1 (2023). URL: https://doi. S. Madden, M. Stonebraker, Aurum: A data disorg/10.1145/3588689. doi:1 0 . 1 1 4 5 / 3 5 8 8 6 8 9 . covery system, in: 2018 IEEE 34th International [8] A. Khatiwada, R. Shraga, W. Gatterbauer, R. J. Miller, Conference on Data Engineering (ICDE), IEEE, 2018, Integrating data lake tables, Proc. VLDB Endow. pp. 1001–1012. 16 (2022) 932–945. URL: https://doi.org/10.14778/ [21] Y. Dong, K. Takeoka, C. Xiao, M. Oyamada, Ef3574245.3574274. doi:1 0 . 1 4 7 7 8 / 3 5 7 4 2 4 5 . 3 5 7 4 2 7 4 . ifcient joinable table discovery in data lakes: A [9] C. Liu, A. Usta, J. Zhao, S. Salihoglu, Governor: high-dimensional similarity-based approach, in: Turning open government data portals into inter- 2021 IEEE 37th International Conference on Data active databases, in: Proceedings of the 2023 CHI Engineering (ICDE), IEEE, 2021, pp. 456–467. Conference on Human Factors in Computing Sys- [22] C. Koutras, G. Siachamis, A. Ionescu, K. Psarakis, tems, Association for Computing Machinery, New J. Brons, M. Fragkoulis, C. Lofi, A. Bonifati, A. KatYork, NY, USA, 2023, pp. 468–479. sifodimos, Valentine: Evaluating matching tech[10] D. Brickley, M. Burgess, N. Noy, Google dataset niques for dataset discovery, in: 2021 IEEE search: Building a search engine for datasets in 37th International Conference on Data Engineering an open web ecosystem, in: The World Wide (ICDE), IEEE, 2021, pp. 468–479.