联系我们： 手动添加方式: 微信>添加朋友>企业微信联系人>13262280223 或者 QQ: 1483266981

1 INFS3200 Advanced Database Systems Prac 3: Data Linkage (5%) Semester 2, 2021 Due time: 4:00pm, Friday 15 Oct 2021 (Week 11) Submission: Submit your work online (INFS3200 Course Website) Introduction Learning objectives: Learn how to use JDBC/cx_Oracle to interact with Oracle DBMS, including the operations of create table, update table, query table, etc. Learn how to measure the performance of data linkage. Understand various string similarity measures, e.g., edit distance and Jaccard coefficient, for field-level data linkage. Marking Scheme: This Prac carries 5 marks for 5% of this course. 1. 2 marks: Complete two missions in Task 1, each mission is accounted for 1 mark. 2. 1 mark: Complete Task 2, the correct answer for each bullet point is worth 0.5 marks. 3. 1 mark: Complete Task 3. 4. 1 mark: Complete Task 4. Please include your screenshots of the data import and data linkage results (precision, recall, f- measure and time) in a word/pdf document, as well as your answers to the task questions. It is not mandatary to include your student ID in every screenshots as we can check the originality through your code submission. The submission should be a zip/rar file, which includes both the answer document and your source code files. Please format your document and code nicely to help tutor’s marking process. A poorly formatted document may receive a reduced mark. Submit your work to the Blackboard website of the course by 16:00 (i.e., 4pm), Friday Oct 15th 2021. Late Penalties (from ECP): “Where an assessment item is submitted after the deadline, without an approved extension, a late penalty will apply. The late penalty shall be 10% of the maximum possible mark for the assessment item will be deducted per calendar day (or part thereof), up to a maximum of seven (7) days. After seven days, no marks will be awarded for the item. A day is considered to be a 24 hour block from the assessment item due time. Negative marks will not be awarded.” 2 Part 1: Preparation of the Restaurant Data Set In this part, our objective is to prepare data for subsequent tasks. There are two options for data storage: (1) import data into Oracle database, or (2) store data as CSV files. Both solutions are implemented and available in either Java or Python. Although both options are available, we recommend you to try the database option, as you can learn more about how to interact with database using Java/Python code. Option 1: Import data to Oracle database through JDBC/cx_Oracle This option requires the following software: (1) Oracle platform used in Prac1 & Prac2, (2) Java JDK/Python library (Java 8/Python 3.8 recommended), and (3) Java/Python IDE. Here we give an example of Java with Eclipse, but others, like Intellij IDEA for Java or PyCharm for Python, will work the same. You need to go through the following 4 steps. Step 1: Log in and Create Users In this part, we first use “SQL Plus” to create a database user, then we need to connect user to “SQL Developer” and interact with an Oracle database. In SQL Plus Command Line window, login to Oracle with a default username “SYS AS SYSDBA” and password “Password1!”, as shown below. Follow the commands below to create a user: /*Enable user creation*/ ALTER SESSION SET “_ORACLE_SCRIPT”=TRUE; /* Create a user named “S1234567” (student id) with password “w” */ CREATE USER S1234567 IDENTIFIED BY w ACCOUNT UNLOCK DEFAULT TABLESPACE “USERS” TEMPORARY TABLESPACE “TEMP” PROFILE “DEFAULT”; /* Grant DBA privilege to “S1234567” */ 3 GRANT DBA TO S1234567; Same as that of the previous Prac1 & Prac2, please change “S1234567” to your student ID. Step 2: Use Oracle SQL Developer Open SQL Developer and connect the user that we have just created. Click the green “+” button to connect to the database. Fill the connection information in the prompted dialog window shown as above. The “connection name” is specified by the user, and the “username” is the “S1234567” we have just created. “Password” is the password for that user, i.e., “w” in this case. You also need to change SID to “orcl”. Then press “Connect” button to connect to the user “S1234567”. Step 3: Import the Data Linkage Project via Java IDE In this step, we import the Java code template to your Java IDE. Here we use Eclipse as our example. Other IDEs work in a similar way. From the Windows 10 “Start” menu, you can search the “Eclipse”. When you open the “eclipse” software, a dialog window will be prompted asking you to select a workspace, as shown below. Choose a folder where you want your Eclipse project to be stored. Connection name specified by user Change SID to orcl Username just created in the database Password for that user, “w” in this prac 4 Extract the DataLinkage Java project downloaded from Blackboard course website to the workspace. At the eclipse “Project Explorer” panel, mouse right-click and then choose the “import” function. From the prompted dialog window, click “General – Existing Projects into Workspace” and then press the “Next” button. Browse the file folder to find the DataLinkage project in your workspace and press “Finish”, as shown below. Now the project has been successfully imported into your workspace. Step 4: Understand JDBC/cx_Oracle Connection to Oracle DBMS The JDBC API is a Java API that can access any kind of tabular data, especially data stored in a Relational Database (the counterpart in Python is cx_Oracle, open a command prompt and enter “python -m pip install cx_Oracle –upgrade” to install cx_Oracle to Python). JDBC helps you to write Java applications that manage these three programming activities: Connect to a data source, like a database, Send queries and update statements to the database, Retrieve and process the results received from the database in answer to your query. In order to connect a Java application with the Oracle database, typically you need to follow five steps to perform database connectivity. In the following example, we use a database supported by Oracle 12c. Hence, we need to know some related information for the Oracle database management: Driver class: The driver class for the Oracle database is “oracle.jdbc.driver.OracleDriver”. URL: The URL for Oracle 12c database is “jdbc:oracle:thin:@localhost:1521:orcl” where “jdbc” is the API, “oracle” is the database, “thin” is the driver, “localhost” is the server name on which Oracle is running (we may also use IP address), “1521” is the port number, and “orcl” is the Oracle service name. Username: In this Prac, please use the “S1234567” user that you have just created. Password: Password is assigned at the time of creating a user, i.e., “w” in this case. 5 The following simple code fragment gives an example of a five-step process to connect to an Oracle database and perform certain queries. Example 1: In this code fragment, we create a connection con to the database and store the query result of “SELECT * FROM table” to the result set rs and display them. Browse the DataLinkage project in your IDE and find the package “Oracle”. We provide various Java classes for interacting with the Oracle database, including: DBConnection: Basic connection settings and functionalities. CreateTable: Create a table in the database InsertTable: Insert tuples into a table DeleteTable: Delete tuples from a table ReadTable: Select tuples from a table DropTable: Drop a table from the database In order to play with these functionalities, you need to first change the username to the user you just created in DBConnection.java class. import java.sql.*; class OracleCon { public static void main(String args[]) { try { // step1 load the driver class Class.forName(“oracle.jdbc.driver.OracleDriver”); // step2 create the connection object Connection con = DriverManager.getConnection(“jdbc:oracle:thin:@localhost:1521:orcl”, “S1234567”, “w”); // step3 create the statement object Statement stmt = con.createStatement(); // step4 execute query ResultSet rs = stmt.executeQuery(“select * from table”); while (rs.next()) System.out.println(rs.getInt(1) + ” ” + rs.getString(2) + ” ” + rs.getString(3)); // step5 close the connection object con.close(); } catch (Exception e) { System.out.println(e); } } } 6 CREATE TABLE The dataset we are going to use in this Prac is a list of restaurants at various locations. The table contains four attributes: ID, Name, Address, and City. We use the following SQL statement to create this table in the database: CREATE TABLE RESTAURANT (ID NUMBER NOT NULL, NAME VARCHAR2(100 BYTE) NOT NULL, ADDRESS VARCHAR2(255 BYTE) NOT NULL, VARCHAR2(50 BYTE) NOT NULL, RESTAURANT_PK PRIMARY KEY(ID) ENABLE); Run the CreateTable.java class to execute this SQL query using JDBC. Open CreateTable.java, right-click the class, and choose “Run As – Java Application”. When the program terminates, check the table you created in SQL Developer. INSERT INTO TABLE The class InsertTable.java reads all the restaurant records from the excel file we have provided in this Prac, i.e. “datarestaurant.csv”, and insert these records one by one into the RESTAURANT table using JDBC. Run InsertTable.java and then check the result in SQL Developer. 7 SELECT FROM TABLE The class ReadTable.java reads all the restaurant records from table RESTAURANT in the database by executing the SQL query, i.e., “SELECT * FROM RESTAURANT”, using JDBC. It then prints out these records (ID, Name, Address, City) on the Eclipse Console, as shown below. There should be 858 records in total, which can be seen at the end of the printed screen. Option 2: Read data from the CSV File In this option, IDE (integrated development environment) is used, which can be either a Java IDE or Python IDE, determined by the language that you prefer to use. 1. Java IDE: In Java, we provide you with the data loader functionality in CSVLoader.java under Data package. The function restaurantLoader() in CSVLoader.java reads the restaurant information from the CSV file. We call this function in three files, namely NestedLoopByName.java, 8 NestedLoopByNameED.java and NestedLoopByNameJaccard.java. Therefore, you should enter these three files respectively and enable the CSV reader by uncommenting the following line: Restaurant[] restaurants = CSVLoader.restaurantLoader(“data\restaurant.csv”); In the meantime, comment the option 1 part in each file, the result is shown as follows: Be sure to perform the same process to all three files. 2. Python IDE: In Python, we provide you with the data loader functionality in csv_loader.py. Since we also provide two data loading option in Python, we choose the data loading from CSV as default in nested_loop_by_name.py, nested_loop_by_name_ed.py and nested_loop_by_name_jaccard.py. You can switch between two options in the following code snippet. Task 1: Read the code in NestedLoopByName.java/nested_loop_by_name.py and focus on the data loading part. Understand how data are loaded into restaurants array and complete the following data statistics tasks in the given class DataStatistics.java/data_statistics.py: Count the number of restaurant records whose city is “new york” and “new york city”, respectively. Count total number of distinct values in city attribute (Hint: use HashSet in Java or set in Python). There are two ways of completing this task: 9 (1) Load data from Oracle database or CSV file to “Restaurant[] restaurants” object using the method implemented in NestedLoopByName.java/ nested_loop_by_name.py, then obtain corresponding results by processing the “restaurants”, or (2) Write SQL queries that retrieve the task results directly from database, send such query through JDBC/cx_Oracle (like the example shown in Example 1) and print the result to screen. (Note: in Java, if you want to complete this task through SQL query, you may also change the ExecuteQuery(query) in DBConnection.java, as it is initially designed for parsing restaurant records to a Restaurant[] array. Writing a new parser for your new SQL is a better idea than changing ExecuteQuery(query) directly as it is called by other classes as well.) Please screenshot both your code in DataStatistics.java/data_statistics.py and the running results. They should be included within one image. The format of the results is similar as follows (The actual value is not the same as the example): Part 2: Measure the Performance of Data Linkage There are some duplications in the original restaurant dataset, and we will use Data Linkage techniques to detect these duplications, i.e., pairs of records that refer to the same real-world entity. For example, the following two records actually represent the same restaurant: 5, “hotel bel-air”, “701 stone canyon rd.”, “bel air” 6, “bel-air hotel”, “701 stone canyon rd.”, “bel air” 1. Nested-Loop Join for Data Linkage The nested-loop join, a.k.a nested iteration, uses one join input as the outer input table and the other one as the inner input table. The outer loop consumes the outer input table row by row. The inner loop, executed for each outer row, searches for matching rows in the inner input table. The pseudo-code below shows its workflow. In the simplest case, the search scans an entire table or index, which is called a naive nested loop join. In this case, the algorithm runs in O(|R|*|S|) time, where |R| and |S| are the number of tuples contained in tables R and S respectively and can easily be generalized to join any number of relations. Furthermore, the search can exploit an index as well, which is called an index nested loop join. A nested loop join is particularly effective if the outer input is small and the inner input is pre-indexed and large. In many small transactions, such as those affecting only a small set of rows, index nested loop joins are superior to both merge joins and hash joins. In large queries, however, nested loop joins are often not the optimal choice. For each tuple r in R do For each tuple s in S do If r and s satisfy the join condition Then output the tuple 10 In this Prac, we adopt a nested-loop method to self-join the RESTAURANT table for data linkage. We first consider perfect matching on the “Name” attribute. In other words, we link two restaurant records (i.e., they refer to the same entity) only if their names are identical, e.g., 1, “arnie morton’s of chicago”, “435 s. la cienega blv.”, “los angeles” 2, “arnie morton’s of chicago”, “435 s. la cienega blvd.”, “los angeles” Program namely, NestedLoopByName.java/nested_loop_by_name.py is the implementation of this algorithm. It first reads all restaurant records from the Oracle database using JDBC, and then self-joins the table by a nested-loop join. If two records have the same “Name” value, the algorithm outputs this linking pair, i.e., id1_id2 where id1 and id2 are the “ID”s of these records respectively. 2. Precision, Recall, and F-measure We can regard the problem of data linkage as a classification task. Specifically, for each pair of records r and s, we predict a binary class label: “0” or “1”, where “1” means we believe these two records refer to the same entity and hence can be linked. Naturally, a data linkage algorithm is perfect if and only if: (1) Precision: all the linked pairs it predicts are correct, and (2) Recall: all possible linked pairs are discovered. We provide a file “data\restaurant_pair.csv” which stores the gold-standard linking results, i.e., all the restaurant record pairs that refer to the same real-world entity. Suppose that D represents the set of linked pairs obtained by the data linkage algorithm, and D* is the set of gold-standard linking results. The algorithm is regarded as perfect if the two sets are identical, i.e., D=D*. Precision and Recall are well-known performance measures that can capture the above intuitions. For classification tasks, the terms true positives, true negatives, false positives, and false negatives are considered to compare the results of the classifier under test with trusted external judgments (i.e., gold-standard). The terms positive and negative refer to the classifier’s prediction (sometimes known as the expectation), and the terms true and false refer to whether that prediction corresponds to the external judgment (sometimes known as the observation), as shown below. Given a linked pair id1_id2 in this Prac, it is like: True positive, if it belongs to both D and D* False positive, if it only belongs to D False negative, if it only belongs to D* True negative, if it belongs to neither D nor D* Based on these terms, precision and recall are defined as follows, where tp, fp, and fn represent true positive, false positive, and false negative, respectively. = + = + 11 Often, there is an inverse relationship between precision and recall, where it is possible to increase one at the cost of reducing the other. For example, brain surgery can be used as an illustrative example of the trade-off. Consider a brain surgeon tasked with removing a cancerous tumour from a patient’s brain. The surgeon needs to remove all of the tumour cells since any remaining cancer cells will regenerate the tumour. Conversely, the surgeon must not remove healthy brain cells since that would leave the patient with impaired brain function. The surgeon may be more liberal in the area of the brain she removes to ensure she has extracted all the cancer cells. This decision increases recall but reduces precision. On the other hand, the surgeon may be more conservative in the brain she removes to ensure she extracts only cancer cells. This decision increases precision but reduces recall. It can be seen that, greater recall increases the chances of removing healthy cells (negative outcome) and increases the chances of removing all cancer cells (positive outcome). Greater precision decreases the chances of removing healthy cells (positive outcome) but also decreases the chances of removing all cancer cells (negative outcome). Therefore, another performance measure is used to consider the both precision and recall together, namely, F-measure, in which precision and recall are combined by their harmonic mean, as shown below. = 2 + Task 2: Program Measurement.java/measurement.py class implements above performance measures, namely precision, recall, and f-measure. Please read and understand the “CalcuMeasure” function in Measurement.java. Explain the following concepts and explain which variable in the code are they correspond to (count, result.size(), benchmark.size()) in our data linkage problem. Note that some concepts may require additional calculation on the existing variables, and some may not derivable from the variables provided (then only explain its meaning). Include your explanation in the submitted document: What are the true positive, true negative, false positive and false negative What are the meanings of precision and recall in this case An example answer could be as such format (the answer in the example is not correct): “The false positive is the records that appear in both the linkage result and the gold-standard, which is corresponding to count/result.size(). There are 120 false positive pairs.” or “The false positive is the records that appear in both the linkage result and the gold-standard, it is not calculated in the code.” Part 3: Similarity Measures for Field-Level Data Linkage In above Part 2, we link two restaurant records only if their names are identical. However, datasets, in practice, are always informal and noisy, full of abbreviations, spelling mistakes, various entity representations, etc. Therefore, a better solution would be to calculate the similarity between records, which is also the main issue of data linkage. We consider two string similarity measures in Task 3, i.e., Jaccard coefficient and edit distance, to estimate the similarity between restaurant names, so to link corresponding restaurant records. You will see later how these similarity measures affect the performance of data linkage. 12 1. Jaccard Coefficient Jaccard coefficient, also known as Jaccard index or Intersection over Union, is a statistic method used for comparing the similarity and diversity of sample sets. The Jaccard coefficient measures similarity between finite sample sets, and is defined as the size of the intersection divided by the size of the union of the sample sets: (, ) = | ∩ | | ∪ | = | ∩ | || + || | ∩ | Here, A and B are two sample sets, and J(A, B)=1 if A and B are both empty. As you can see, the Jaccard coefficient compares members for two sets to see which members are shared and which are distinct. It measures the similarity between two sets, with a range from 0% to 100%. The higher the percentage, the more similar the two sets. Consider the following simple example, how similar are these two sets Obviously, J(A,B) = |A∩B| / |A∪B| = |{0,2,5}| / |{0,1,2,3,4,5,6,7,9}| = 3/9 = 0.33. A = {0,1,2,5,6} B = {0,2,3,4,5,7,9} In order to measure the similarity between two strings using Jaccard coefficient, the strings need to be converted into sets firstly. In this Prac, we consider q-gram representation of a string. Q- gram is a contiguous sequence of q items from a given string. The items can be phonemes, syllables, characters, or words according to the application. A q-gram of size 1 is referred to as a “unigram”; size 2 is a “bigram”; size 3 is a “trigram” (or 3-gram). Larger sizes are sometimes referred to by the value of q in modern language, e.g., “four-gram”, “five-gram”, and so on. As an example mentioned in Week-8 Lecture Notes and Tutorial 7, consider the string “University_of_Queensland”, we can transform it as a set of 3-grams with each character as the item: “University_of_Queensland”: {“##U”, “#Un”, Uni”, “niv”, “ive”, “ver”, “ers”, “rsi”, “sit”, “ity”, “ty_”, “y_o”, “_of”, “of_”, “f_Q”, “_Qu”, “Que”, “uee”, “een”, “ens”, “nsl”, “sla”, “lan”, “and”, “nd#”, “d##”}, where using character “#” is optional to pad the beginning and ending of the string for the completeness of 3-gram. The Jaccard coefficient similarity measure based on q-grams has been implemented in the class Similarity.java/similarity.py. Task 3: In NestedLoopByNameJaccard.java/nested_loop_by_name_jaccard.py, we link two restaurant records if the Jaccard coefficient of corresponding restaurant names exceeds a predefined threshold. Run NestedLoopByNameJaccard.java/nested_loop_by_name_jaccard.py with different settings of “q” and “threshold” to see how these two parameters affect the output of the similarity measure, and therefore affect the performance of data linkage in terms of the output size and measurement result. Test the influence of each parameter by altering its value to five different settings (up to your choice, but make sure your values are valid) as well as fixing the other parameter. Do such process to both parameters and screenshot all your precision, recall and f-measure results. Explain why the precision/recall increases/decreases based on your understanding. Include both your screenshots and your results in your submitted document. Note that, q=0 means we divide the original string into a bag-of-words. 13 2. Edit Distance Given two strings A and B, their edit distance is the minimum number of edit operations required to transform A into B. Most commonly, the edit operations allowed for this purpose are: Insert a character into a string; Delete a character from a string; Replace a character of a string by another character. For these operations, edit distance is sometimes known as Levenshtein distance. For example, the edit distance between “cat” and “dog” is 3. In fact, edit distance can be generalized to allowing different weights for different kinds of edit operations, for instance a higher weight may be placed on replacing the character “s” by the character “p”, than on replacing it by the character “a” (the latter being closer to “s” on the keyboard). Setting weights in this way depending on the likelihood of letters substituting for each other is very effective in practice. However, to simplify the work in this Prac, we will only focus on the case in which all edit operations have the same weight. It is well-known on time complexity of computing the edit distance between two strings is O(|A|*|B|), where |A| and |B| denote the length of strings A and B respectively. The idea is to use the dynamic programming algorithm, where the characters in A and B are given in array form. The algorithm fills the (integer) entries in a matrix namely ED, whose two dimensions equal to the lengths of the two strings whose edit distances is being computed. The ED[i][j] entry of the matrix will hold (after the algorithm is executed) the edit distance between the strings consisting of the first i characters of A and the first j characters of B. There is a relation between ED[i][j] and ED[i-1][j-1]. Assume that we transform from one string to another. The first string has length i and its last character is “x”, and the second string has length j and its last character is “y”. The following diagram shows the relation. Therefore, by using the dynamic programming algorithm, we can calculate the edit distance between two strings based on the edit distance of their substrings. In particular, If “x” and “y” are identical, then ED[i][j] = ED[i-1][j-1]; If “x” and “y” are different, and we insert “y” for the first string, then 14 ED[i][j] = ED[i][j-1] + 1; If “x” and “y” are different, and we delete “x” for the first string, then ED[i][j] = ED[i-1][j] + 1; If “x” and “y” are different, and we replace “x” with “y” for the first string, then ED[i][j] = ED[i-1][j-1] + 1; When “x” and “y” are different, ED[i][j] is the minimum of the three situations. Above is an example of using the dynamic programming algorithm to calculate the edit distance between strings “fast” and “cats”. Some more examples are available in Week-8 Lecture Notes and in T7 Tutorial. It is worth noting that the edit distance is not a direct hint of the similarity between two strings. Naturally, long strings could have more typing errors than short strings. In other words, we need to normalize the edit distance by string length in order to have a fair comparison of two strings. Since the maximum possible edit distance between any two strings A and B is max(|A|, |B|), we further calculate edit similarity as follows: (, ) = 1 (, ) (||, ||) Task 4: Please complete the implementation of edit distance in Similarity.java/similarity.py, run NestedLoopByNameED.java/nested_loop_by_name_ed.py to see how edit distance affects the performance of data linkage. Same as the above Task 3, you need to report the algorithm’s precision, recall, and f-measure with five different settings of the “threshold” and provide your understanding of the trends. Include both the screenshots of the results under different threshold settings and your explanation in your submitted document. Hint: You can construct an example to test if our edit distance implementation works correctly. In Java, find edit distance and Jaccard coefficient using the code in Similarity.java: 1. Open Similarity.java. 2. Make a public main method to implement following lines as shown in the screenshot below: public static void main(String[] args) { String str1 = “University”; String str2 = “Unvesty”; int out = Similarity.CalcuED(str1, str2); System.out.println(“Edit Distance = “+ out); double out2 = Similarity.CalcuJaccard(str1, str2, 2); System.out.println(“Jaccard Coefficient = “+ out2) }; 15 In Python, do the similar process in similarity.py as follows: str1 = “University” str2 = “Unvesty” out = calc_ed(str1, str2) print(“Edit Distance = “, out) out2 = calc_jaccard(str1, str2, 2) print(“Jaccard Coefficient = “, out2) Based on your understanding of these two measures, you can check if your code returns the expected value. Note that edit distance is different from edit distance similarity. The edit distance similarity is implemented as CalcuEDSim/calc_ed_sim in Java/Python, which is a normalized similarity. —ooo000OOO000ooo— 程序