No Schema SQL Querying Relational Databases Independent of Schema Adam Boot Michael Maur Keith Kelly Jing Yu Maryam Karimzadehgan 6 Dec 2006 CS511 1 Agenda 6 Dec 2006 Motivation Approach Method Challenges Demonstration Conclusion Future Work CS511 2 Motivation Schema Dependence Relational Model achieved certain forms of independence Schema dependence is undesirable 6 Dec 2006 Independent of ordering Independent of indexing Independent of access path Not independent of schema Memorizing schema is a burden on the user When schema changes queries must change CS511 3 Motivation The Problem with SQL SQL is difficult for the causal user Relational schema is double edged Implementation of a full natural language interface is very hard 6 Dec 2006 Schema should exist to help in finding relevant data User should not need to understand structure of underlying schema transparency NaLIX 1 CQL NL 2 CS511 4 Approach What No Schema SQL NS SQL is Relaxed form of SQL s syntactical structure Source to source translator Infers schema from fk pk mappings Qualifies column references Specifies table references and joins FROM clause What NS SQL is not Natural language interface User must still know basic SQL syntax Mind reader ambiguities become possible 6 Dec 2006 Frees users from having to know schema Allows schema specific elements to be omitted Column name ambiguity Join path ambiguity CS511 5 Approach A Simple Example id Employee name salary id title description Job id Facility city state Find the name city and state of all employees whose salary is greater than 70 000 and job title is Database Designer SQL SELECT Employee name Facility city Facility state FROM Employee JOIN Job ON Employee job id Job id JOIN Facility ON Employee facility id Facility id WHERE Employee salary 70000 AND Job title Database Designer NS SQL SELECT name city state WHERE salary 70000 AND title Database Designer 6 Dec 2006 CS511 6 Method System Architecture Get Schema DBMS via JDBC sc sql he m a url DB URL console Schemafy GUI Hub ddl schema Schemafier d ml ambig Parse NS SQL 6 Dec 2006 n ss ql command line script file GUI Statement Parser di sa m bi g NS SQL ambiguity error SQL parse error CS511 7 Method Statement Processing Employee Facility name city Schemafier SELECT name city state WHERE salary 70000 AND title Database Designer SELECT Facility Employee Job state title salary key mapping for join Exployee job id Job id Employee facility id Facility id Legend Column reference name city Structure state Image node WHERE Table reference Expression salary 70000 and title Salary title Database Designer 6 Dec 2006 CS511 8 Method Statement Processing Employee Facility name city SELECT Facility Employee Job state title salary key mapping for join Exployee job id Job id name city state Employee facility id Facility id WHERE Expression salary 70000 and title Salary title Database Designer 6 Dec 2006 CS511 9 Method Statement Processing Employee Facility name city SELECT key mapping for join Employee name name FROM Facility city city Joined Table Exployee job id Job id Facility state state Employee facility id Facility id Facility Joined Table Employee Facility facility id id Job WHERE Expression Employee job id Job id Employee Employee salary salary 70000 and 6 Dec 2006 Facility Employee Job state title salary CS511 Job title title Database Designer 10 Method Statement Processing SELECT Empoyee name Facility city Facility state FROM Employee JOIN Job ON Employee job id Job id JOIN Facility ON Employee facility id Facility id WHERE Employee salary 70000 AND Job title Database Designer SELECT Employee name FROM Facility city Joined Table Facility state Facility Joined Table Employee Facility facility id id Job WHERE Expression Employee job id Job id Employee Employee Job Salary Database Designer salary 70000 and title title 6 Dec 2006 CS511 11 Challenges Parser 6 Dec 2006 Input Requirement Support standard SQL SQL92 inputs and relaxed SQL NS SQL inputs Extensible tolerate dialects AST Requirement Easy to extract column table references Able to modify column reference and FROM clause given feedback from Schemafier Solution Build our own NS SQL parser with JavaCC Design a sufficient internal representation CS511 12 Challenges Schemafier Determine how referenced columns are relatable From among referenced column names determine a unique set of related physical columns Determine a unique join path Types of possible ambiguity Column Join 6 Dec 2006 name ambiguity path ambiguity CS511 13 Challenges Schemafier Column Name Ambiguity Column names might be similar between tables 6 Dec 2006 eg column name such as id or name Assume all referenced columns are related via fk pk no Cartesian products No other assumptions about which physical columns are intended If multiple interpretations of column name physical column notify user of ambiguity Graph tagging algorithm reachability CS511 14 Challenges Schemafier Name Ambiguity Graph Tagging 6 Dec 2006 tag 1 Interpret a schema as a graph Enroll Tables are nodes Key mappings are edges Mark all roots nodes without parents and their children with a common tag A node may have multiple tags Nodes that share a common tag are reachable amongst each other valid solution CS511 Student Course Survey tag 2 two tags 1 Enroll Student Course 2 Survey Student Course 15 Challenges Schemafier Name Ambiguity Example tag 1 grade SELECT name title grade Unambiguous tag 1 SELECT grade rating Unrelatable no common tag SELECT name designator Unambiguous tag 1 and tag 2 SELECT name credithours Ambiguous two physical interpretations of reference credithours and each is a valid solution SELECT rating credithours Unambiguous two versions of credithours but only one valid solution tag 2 6 Dec 2006 CS511 Enroll credithours id name Student email ta Course id designator title credithours Survey rating tag 2 16 Challenges Schemafier Join Path Ambiguity 6 Dec 2006 Set of columns returned from Column Disambiguation algorithm as input physical columns Finds join paths that exist between columns in tables according to mapping between Foreign Primary key If there is more than one path unambiguous solution otherwise ambiguous solution CS511 17 Challenges Schemafier Path Ambiguity Finding Possible Paths Enrollment Get set of common predecessors for all referenced tables Student Course Get set of possible paths common predecessors Enrollment from root to each Professor referenced table Course root Professor paths from Course all