\documentclass[12pt]{report}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Standard AMS packages
\usepackage{amssymb, amsmath, amsthm, url, cite, subfigure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  For mathematical diagrams
\usepackage{xypic}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% For inserting graphic files
\usepackage{graphicx, csquotes} %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Hyper-references
%\usepackage[pdftex, plainpages=false]{hyperref}   %To be use with PDF-TEX

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Graduate college required margins
\usepackage[left=1.5in, top=1.3in, right=1.3in, bottom=1.2in]{geometry}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% line spacing
\usepackage{setspace}
    %\singlespacing
    %\onehalfspacing
    \doublespacing


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Personal Environments and Commands
\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}{Example}
\numberwithin{equation}{chapter}
\numberwithin{figure}{chapter}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% My commands
\newcommand{\reals}{\mathbb{R}}   %Real numbers' symbol
\newcommand{\hyperbolic}{\mathbb{H}}  %Hyperbolic symbol
\newcommand{\complex}{\mathbb{C}} %Complex numbers' symbol
\newcommand{\integers}{\mathbb{Z}}   %Integer numbers' symbol
\newcommand{\presentation}[2]{\langle \, #1  \, | \, #2 \,  \rangle}
\newcommand{\GammaH}{Cayley (G, X\cup \widetilde{\mathcal{H}}) }
\newcommand{\Hs}{\{ H_i \}_{i=1}^m}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% THESIS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}

\title{A FLEXIBLE SCHEMA-AWARE MAPPING OF XML DATA INTO RELATIONAL MODELS}
\author{Vamshi Krishna Sunchu}
\date{July 2016}



{%% PAGE NUMBERING ROMAN

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TITLE PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\singlespacing

\newpage
\thispagestyle{empty}
\begin{center}
{ %\large
UNIVERSITY OF OKLAHOMA
\par
\vspace{0.16in}
GRADUATE COLLEGE
\par
\vspace{1.2in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
A FLEXIBLE SCHEMA-AWARE MAPPING OF 
\par
\vspace{0.17in}
XML DATA INTO RELATIONAL MODELS
\par
\vspace{1.2in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
A THESIS
\par
\vspace{0.17in}
SUBMITTED TO THE GRADUATE FACULTY
\par
\vspace{0.17in}
in partial fulfillment of the requirements for the
\par
\vspace{0.17in}
Degree of
\par
\vspace{0.17in}
MASTER OF SCIENCE
\par
\vfill
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
By
\par
\vspace{0.17in}
VAMSHI KRISHNA SUNCHU
\par
%\vspace{0.05in}
Norman, Oklahoma
\par
%\vspace{0.05in}
2016
}
\end{center}

\pagenumbering{roman}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% SIGNATURE PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\thispagestyle{empty}
\begin{center}
{%\large
A FLEXIBLE SCHEMA-AWARE MAPPING OF 
\par
%\vspace{0.17in}
XML DATA INTO RELATIONAL MODELS
\par
\vspace{0.9in}
A THESIS APPROVED FOR THE
\par
%\vspace{0.17in}
SCHOOL OF COMPUTER SCIENCE
\par
\vspace{0.9in}
BY
\par
\vfill
\begin{flushright}
\begin{tabular}{cr}
\hline
\  \  \  \  \  \  \  & Dr. Chris Weaver, Chair\\
 \\ &  \\
  \\ &  \\
\hline
  & Dr. Christan Grant \\
\\ & \\
 \\ &  \\
\hline
  & Dr. K. Thulasiraman \\
\end{tabular}
\end{flushright}
}
\end{center}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% COPYRIGHT PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\thispagestyle{empty}
\   \
\par
\vfill
\begin{center}
\copyright \    Copyright by VAMSHI KRISHNA SUNCHU \   2016

All Rights Reserved.
\end{center}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% DEDICATION PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newpage

\thispagestyle{empty}
{\singlespacing
\begin{center}
{
\par
\vspace{1.2in}
%\large
DEDICATION
\par
\vspace{0.17in}
to
\par
\vspace{1.2in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
My parents
\par
\vspace{0.17in}
Sunchu. Narahari, and
\par
\vspace{0.17in}
Sunchu. Renuka
\par
\vspace{1.2in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
For
\par
\vspace{0.17in}
Encouraging me to follow my dreams
\par
\vfill
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
}
\end{center}
}

\pagenumbering{roman}
\setcounter {page} {3}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ACKNOWLEDGEMENTS PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter*{Acknowledgements}

First of all, I would like to express my sincere gratitude to my advisor, Professor Chris Weaver, whose constant guidance helped me in completing this study, from the thesis proposal up to the final thesis manuscript. Without his guidance, endless advice, and persistent help, this study would not have been possible.  

A special thanks to Dr. Samuel J. Huskey, Dr. Abbas June and all the team members of Digital Latin Library for all the advice and encouragement throughout the project.

I would like to express my deep appreciation to Dr. Christan Grant and Dr. K. Thulasiraman for serving on my committee and taking time to talk with me on many occasions. 

I would also like to extend my thanks to my close friends and my roomies in the university for all the memories and inside jokes that we shared together and making the last two years more memorable.

No acknowledgement would be complete without thanking my beloved father and mother, they are my inspiration and motivation for everything. I would like to thank them for letting me be the person I am today, without their endless support, enduring love, constant guidance, and encouragement, I could not have made it.  Furthermore, I would like to thank my sisters and cousins for their unconditional love and support.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TABLE OF CONTENTS PAGE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\singlespacing
\tableofcontents
\listoffigures
\listoftables
}
\newpage

} %% END PAGE NUMBERING ROMAN


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ABSTRACT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter*{Abstract}

In the last several years, substantial contributions have been made in the development of techniques to transform and store eXtensible Markup Language (XML) \cite{xmlSpecs} data into relational database models. Although there exists a rich literature in this field, none of the existing procedures provides a complete solution in a single framework. Many of the existing solutions describe ways to automate parts of the conversion. However, a purely automated approach has limitations. Due to the heterogeneous and hierarchical nature of XML for a given input, there can be numerous reasonable relational schemas and automated systems may not be able to reach all such possible schemas.\textit{ Our hypothesis is that a human-guided tool can help to identify appropriate relational schemas in complex XML documents for use in highly structured data applications.}

We propose an integrated system that provides an end-to-end solution for the user-guided mapping of XML into relational data. Our system accomplishes the translation in three stages: (1) Parse an XML Schema Definition (XSD) \cite{XSDurl} file to suggest relational schemas; (2) allow users to alter the schema using a user interface to determine appropriate schemas; and (3) populate relational tables using an input XML document. The system extracts key information from the XSD input file and introduces new constraints, wherever required, as keys are crucial for querying the resulting relations. The user interface is an essential component of our system. It enables users to perform additional, meaning-driven operations on the suggested schema to achieve application-specific relational schemas.

The Digital Latin Library (DLL) \cite{DLLurl} is a large, collaborative project to build an open collaborative environment for exploring critical editions of Latin texts and facilitating scholarly conversations. In particular, new and existing visualizations of relational data are being developed to support these goals. The Text Encoding Initiative (TEI) \cite{TEIurl} is often used for the representation of critical editions. TEI is a markup language to create digital versions of texts as highly structured XML documents. To help achieve the DLL objectives, we are applying our system to read TEI structure into a relational data model in the Improvise visualization environment \cite{ Improvise, Improviseurl }. This data model, in turn, supports the development of a variety of visualization queries in the DLL software tools.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% INTRODUCTION %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Introduction}

\pagenumbering{arabic}
Critical editions are attempts by scholars to reconstruct texts from fragmentary sources with the most appropriate original meaning. In general, scholars choose an authoritative manuscript and \enquote{correct} it using variations from other manuscripts.  Critical editions encourage readers to think about the work, deeply, beyond the particular manuscript presentation. They also provide details about the work's sources, historical context, form, and style. The Text Encoding Initiative (TEI) \cite{TEIurl} defines guidelines to provide methods for encoding critical editions. 

Scholars are interested in the hidden patterns of information in the reconstruction choices and reconstructed text of critical editions, but querying these patterns directly against a TEI document can be complicated and slow. Transforming this XML-based information in these documents into more structured form, such as a relational data model is highly desirable to help as scholars query more deeply to look for meaningful insights in critical editions. Storing the TEI-encoded critical editions in a highly structured form allows scholars to query and analyze the data by performing operations like sorting, grouping, filtering. These capabilities promise to help scholars greatly in reducing the time and effort needed to identify anomalies and interesting regions in a text. Since TEI is a formal markup language that relies on XML standards, our work concentrates on storing and querying XML data.

The conventional procedures to store and query XML data involve file systems, relational databases, and object-oriented databases. Storing XML data in a file system is convenient and portable but often does not support efficient data queries. Object-oriented databases are generally not structured for processing complex relational queries on large databases. There is considerable interest in using relational database systems, as they support complex queries and can be built on top of powerful and reliable data management services \cite{stored1999, storingQuerying1999, efficientStorage2000, Shanmugasundaram:1999, cpi2001, mani2003, costBased2002,ordered2002, Inlining2003,kappel2004}. Moreover, due to the wide popularity of the XML format, a very large volumes of formatted XML data is available online. Correspondingly, there is a growing need for relational access and processing of XML data.

In the Digital Latin Library project, data visualization techniques will play a central role in a collaborative system enabling scholars to analyze, interact, and comment on Latin texts. Visualization is the graphical representation of data to help users obtain understanding and draw conclusions about data. Improvise, a visualization environment that enables users to build sophisticated interactive visualizations \cite{ Improvise, Improviseurl }, is the basis for developing visualizations. Improvise accepts primarily relational data as its input. So, to develop data visualizations for critical editions, it is highly desirable to first transform Text Encoding Initiative (TEI) formatted documents into relational datasets. 

Towards this aim, our thesis work contributes a system that provides a semi-automated, flexible, schema-aware mapping technique to transform XML data into its equivalent relational data model and allows users to choose and customize the most appropriate relational model for their data analysis and visualization purposes.

One of the significant challenges for developers is to exchange data among various incompatible systems over the Internet. XML, (eXtensible Markup Language) is a common choice for data exchange and integration over the Internet because diverse applications can read documents in this format. XML is self-descriptive and a simple text-based format to specify structures in a document. The roots of XML evolved from an older standard format, called Standard Generalized Markup Language (SGML), in order to be more suitable for web use.  XML is the standard choice for data exchange between different organizations for several reasons. XML tags form the foundation of XML; by using tags, one can describe the meaning of the content. New tags and attributes can be defined, document structures can be nested to any level of complexity, and documents can be validated against a schema specification.

As applications manipulate an increasing volume of XML data, there is a growing need for secure systems to store and query XML documents. A major hurdle of this approach is the need to overcome conflicts between XML and relational data models. Whereas XML data is hierarchical and ordered in nature, relational data models are flat, unordered, and potentially spread across multiple tables. Schema mapping, data mapping, and query mapping assist in overcoming these differences. 

\begin{itemize}
    \item Schema Mapping: This process can involve two different approaches, schema-oblivious and schema-aware. In schema-oblivious XML storage, the final relational schema is independent of the input XML document and employs a fixed, generic, relational database schema. Schema-aware techniques utilize input schema specification documents to help determine relational schemas. To translate the ordered nature of the XML data model into a relational database, one can map any of the XML order encoding schemes by appending additional columns to handle ordinals of XML elements.  
    \item Data Mapping: Data mapping shreds an input XML document to populate the tables of a relational database generated during the schema mapping phase. This phase is also known as XML document shredding. Various reliable XML parsers are available that shred input XML documents.
    \item Query Mapping: To query XML data stored in a relational database, one should map the XML queries into equivalent relational queries (SQL statements). This mapping is known as query mapping. Numerous researchers propose the use relational databases for storing and querying XML documents in order to receive the benefits from sophisticated technologies such as query optimization, transaction management, concurrency control, data security and many more available in database management systems.
\end{itemize}

In summary, to transform an XML document into relational tables takes three steps. The first step is to map the tree structure of the XML document to an equivalent, flat relational schema, using a suitable schema mapping approach. Then, the relational tables are populated by shredding the input XML document. Finally, at runtime, XML queries are translated into SQL and submitted to the RDMBS to fetch the desired result set.

There exists a rich literature of techniques to manage XML documents in relational databases. Many commercial database management systems support XML storage. Nevertheless, none of the mapping techniques or platforms are able to address all the translation ambiguities. Many approaches oppose the philosophy of accepting technical inputs from users \cite{DTDIndependent2009}. The rationale is that XML and relational data are too complex and diverse for most users to make appropriate decisions about schema structure.  However, TEI document encode extremely complicated hierarchical and associative relationships. Fully automatic translation produces nearly unreadable collections of tables with many meaningless key identifiers. 

To overcome this limitation, we propose an XML to relational transformation system that allows users to manually customize an automatically suggested schema. The suggested schema incorporates several mapping strategies from the existing literature and appends certain new strategies related to identity constraints. The system parses an input schema document and suggests a relational schema on which users can perform certain operations to specify an appropriate, meaningful schema for their application. The operations include split tables, merge tables, delete a table, delete columns, rename table, and reset schema. These operations are simple to perform and do not require users to have advanced knowledge of either XML or relational models. The system employs the a form-based user interface to help users perform the operations. 

Once a user finalizes a schema, the system prompts them for a corresponding XML document. It then extracts values from the input document to populate tables of the schema. The system uses XML tag paths in the schema document as XPath strings to extract tag and attribute values for storage in tables.  

The remaining chapters of the thesis are organized as follows:
\begin{itemize}
\item Chapter 2 provides a glimpse of several technologies employed in our system implementation. These technologies include TEI, XML, XML structure constraints, XML Schema Definition Language (XSD), and Relational Database Model Systems (RDBMS).  

\item Chapter 3 describes some of the more substantial contributions described in the literature about XML-to-relational mapping techniques, and strategies our system inherits from them. It also lists their drawbacks and how our current system advances the existing systems.

\item Chapter 4 describes the design specifications, system implementation, user interface and schema operations of our system, with supporting examples.

\item Chapter 5 describes the shredding of TEI documents using our mapping technique, along with a system analysis.

\item Chapter 6 concludes by reviewing the contributions of thesis and outlining several future directions of our work.
\end {itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Background  Information%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Background Information}

It is a well-known fact that digital computers can only store and process binary system information i.e., bits. Hence, it is essential to transform data present in the form of letters, numbers, pictures and others into an equivalent binary system to make it suitable for computer processing. The transformation of data from other systems into bits is known as encoding and if this transformation is from text to binary then it is known as character encoding. Character encoding fails to convey information regarding meta-data like semantics or structure of a text. Text encoding provides meta information through the means of markup language.

\section {Text Encoding Initiative} 
The Text Encoding Initiative (TEI) is a standard for the representation of texts in digital form. A community of scholars, mainly from humanities, social sciences, and linguistics, are organized into a consortium that develops and maintains this standard. Earlier versions of TEI offered a choice of using Standard Generalized Markup Language (SGML) or eXtensible Markup Language (XML). In the latest version, TEI can be expressed only in  XML. TEI is widely accepted by libraries, museums, publishers, and individual scholars to present texts for online research, teaching, and preservation.

Scholarly editions of texts often record some or all of the known variations among different witnesses to the text. Witnesses to a text may include authorial or other manuscripts, printed editions of the work. The TEI provides methods for encoding these critical editions. 

\section {Extensible Markup Language}
Extensible Markup Language (XML) can be used to represent the structure of text documents. Its origin is from Standard Generalized Markup Language (SGML) and is defined by World Wide Web Consortium (W3C) XML 1.0 Specification. Both markup languages are  machine-readable and human-readable, as they include tags that are distinguishable from the text. Tags are regular words, much like the keywords used in programming languages, making markup languages readily human-readable. 

There are three main general categories of markup languages, presentational markup, procedural markup and descriptive markup. 
XML falls under the category of descriptive markup system, as it represents text components of documents rather than presentation or procedural information. Unlike other markup languages, XML places no limitations on the set of permissible tags and imposes limited rules on their usage, which makes the design of the language quite simple. As the name suggests, XML is extensible; a given set of tags can always have new tags added. The logical structure of an XML document includes a root element, parent elements, child elements, attributes within elements and comments. The order in which elements occur in an XML document can be significant.

\noindent
XML documents are legal if they are well-formed and valid. A well-formed XML document has the following characteristics:
\begin{itemize}
\item only one root element, which contains all other elements;
\item all Elements must be properly nested; and
\item each opening tag must have a closing tag.
\end{itemize}

\noindent
A valid XML document must satisfy following criteria:

\begin{itemize}
\item it is well-formed, and
\item it is consistent with the grammatical rules specified in a schema definition document (which may be XSD, DTD, or other schema description format).
\end{itemize}
\noindent
 An XML document must be well-formed but being valid is optional.

\section {Constraints on XML Structure}
As mentioned earlier, XML is flexible and easy to compose, but these benefits of XML come with certain tradeoffs. For example, two documents containing the same information may be created with distinct XML tag names, as there is no restriction on the set of legitimate tags. This results in different XML documents representing the same data, making processing of these documents a more difficult task. To overcome such complications, we need supporting documents that specify the constraints on the legal structure and contents of XML documents. Schema language documents, like Document Type Definition (DTDs), Regular Language for XML Next Generation (Relax-NG), and W3C XML Schema Definition (XSD) accomplish this objective. In addition, schema documents serve the purpose of validating XML documents. 

\section {XML Schema Definition}
Of all the available schema specification formats, XSDs are quite popular because of their prominent features. They define building blocks of XML documents, elements, and attributes that can appear in an XML document; the default and fixed values of elements and attributes; and the number and order of child elements. Unlike other schema documents, XSDs are verbose and define the data types of attributes and elements. The syntax of XSD is similar to that of XML, which makes parsing XSD files accessible simple to implement and apply.

Though DTDs are one of the preferred schema specification formats they are slowly fading out as they suffer from certain drawbacks such as not allowing definition of the types of elements or attributes. They also have no way to specify constraints between elements, which us needed to determine relational key semantics. Considering these shortcomings, we chose XSD as the XML schema document for our schema-aware system. The following section expands on some of the vital components of XSD.

\subsection{XSD Constructs}

XML Schema Definition files allow a variety of valid components and component relationships. In this section, we introduce the constructs and tags of XSD files that are important for our purposes.

\begin {itemize}

\item Attribute: The attribute tag defines the name and type of attributes that may occur in an XML documents. Figure~\ref{figAttribute} depicts attributes in an XSD file. They are optional by default and may have a default or fixed value specified. An attribute is always declared as a simple type.

\begin{figure}[!t]
  \centering
  \includegraphics[width=1.1\linewidth]{Figures/attribute.png}
   \caption{XML Schema code, defining attribute tags.}
  \label{figAttribute}
  \end{figure}
  
\item Element: Like attribute, the element tag in an XSD file also provides information about the name, type, and occurrence of elements in the corresponding XML document. The tag also defines constraints including like minimum and maximum occurrences, default and fixed values. Figure~\ref{figElement} shows an example of elements in an XSD file. An element is of simple type if it contains just text and is of complex type if it holds other elements or has attributes.

\begin{figure}[!b]
  \centering
  \includegraphics[width=1.05\linewidth]{Figures/element.png}
   \caption{XML Schema code, defining element tags.}
  \label{figElement}
  \end{figure}
  
\item Complex Type: A complex type element is a type definition for XML elements that may contain elements and attributes. The following figure~\ref{figComplexType} illustrates a sample complex type element. It defines the structure, content, and attributes of an element. The content can includes special, reserved tag elements like \textless group\textgreater, \textless sequence\textgreater,  \textless choice\textgreater, and \textless all\textgreater. Similarly, attributes of complex type can be defined using tags \textless attribute\textgreater, \textless attributeGroup\textgreater , and \textless anyAttribute\textgreater.

\begin{figure}[!t]
  \centering
  \includegraphics[width=1.05\linewidth]{Figures/complexType.png}
   \caption{XML schema code, defining complex type element. }
  \label{figComplexType}
  \end{figure}
 

\item Key:  The \textless key\textgreater\  element is reserves as a means to define a primary key relationship, in the same manner as a primary key in the relational database model unique and appear explicitly in the XML document. A key element contains \textless name\textgreater, \textless selector\textgreater\ and \textless field\textgreater\  child elements. The \textless field\textgreater\ element specifies the element or attribute names that must be unique. The \textless selector\textgreater\  tag contains the XML path of the values that occur in a sibling \textless field\textgreater.   
  \newpage
  
     \begin{figure}[!t]
  \centering
  \includegraphics[width=1.15\linewidth]{Figures/keyandref.png}
   \caption{ Occurrences of \textless key\textgreater\ and \textless keyref\textgreater\ elements in an XSD. }
  \label{figkey}
  \end{figure} 

     
 \item Key Reference: Complementary to \textless key\textgreater\, the \textless keyref\textgreater\ element contains \textless name\textgreater, \textless selector\textgreater, \textless field\textgreater,  and \textless refer\textgreater\ elements and is similar to a foreign key in the relational model. The tag \textless refer\textgreater\ holds a \textless key\textgreater\ element which is a referred element of  \textless keyref\textgreater. Both \textless key\textgreater\ and \textless keyref\textgreater\ elements define identity constraints of XML documents. An example is shown in figure~\ref{figkey}.  

   
\end{itemize}

\section {Relational Database Management Systems}

Database often contain large amounts of data. The primary goals of a Database Management System (DBMS) are to provide convenient and efficient means to store and retrieve structured collections of information. Data management also facilitates the integrity of the information stored. 

\newpage
A data model provides a way to describe the design of a database. There are various data models available in widespread use. The relational data model is the most widely used data model. It uses a collection of tables to represent data and the relationships among those data. Relational Database Management Systems (RDBMS) often play a pivotal role in the growth of an organization as the amount and complexity of their data increases over time.

A relational schema defines the structure of a database, which including tables, columns/attributes, primary and foreign keys and type information. A relational database consists of a collection of tables, each of which is assigned a unique name. Each table can have multiple columns, and each column has a unique name and data type. Tables hold tuples or rows. Candidate keys specify alternative ways of uniquely identifying rows. One of the candidate keys of a relation can be chosen as the table's primary key. A foreign key is a set of one or more columns in which the values refer to a primary key of another table, such that each value of a foreign key is the same as a value  of a primary key in the referred table.


To demonstrate our system functionality, we use the XML Schema Definition (XSD) shown in figure ~\ref{figExample}. The document defines the structure of an XML file that includes customers, orders, and shipping information. In the next chapter, we use this XSD file to illustrate how the system suggests a schema then supports operations for modifying that schema.

   \begin{figure}[!t]
  \centering
  \includegraphics[width=1.1\linewidth]{Figures/example3.png}
  
  \end{figure}

\makeatletter
    \setlength\@fptop{0\p@}
\makeatother

  \begin{figure}[htbp]
  \centering
  \includegraphics[width=1.1\linewidth]{Figures/example4.png}
   \caption{ Example XML Schema Definition, for XML files containing customer order information. }
  \label{figExample}
  \end{figure} 
\null
\vfill

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% RELATED WORK %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Overview of Mapping Techniques
}

XML to relational mapping techniques can be categorized into schema-aware and schema-oblivious based on the inputs used for this transformation. In the schema-aware approach, mapping techniques make use of XML schema specifications to determine the relational schema whereas the schema-oblivious techniques do not consider XML schema instead directly use XML document. Document Type Descriptors (DTD), XML Schema Definition Language (XSD), Relax NG are the various XML schema languages.  This section reviews some of the mapping techniques and relates them with our system. 

\section{Schema Oblivious Techniques}

\subsection{Edge Mapping}
Edge Mapping \cite{storingQuerying1999} is one of the earliest works done in the field of converting XML data into Relational data. The primary goal of this work is to build a system that supports storing and querying of simple XML schemes. This system does not prompt for any inputs from its users and does not require any of the supporting XML schema specification documents.
\begin{figure}[!t]
  \centering
  \includegraphics[width=1.00\linewidth]{Figures/Customer.png}
   \caption{Sample XML code, defining a Customer data.}
  \label{figEdge}
  \end{figure}
  
This system assigns an object id to each element present in the XML document. It adds an edge between the element and corresponding sub element or its data types. Each edge is labeled with the name of its sub element. The resulting relational schema stores all the edge information in a single table titled as the Edge table. The table columns include the source object id and target of an edge, the edge label, flag that signifies whether the edge is a reference or a data type and an ordinal number as the edges are numbered.  Table ~\ref{EdgeTable} represents the resulting schema  obtained by applying Edge mapping technique on the customer  XML data shown in figure~\ref{figEdge}.

As mentioned earlier, this system only handles simple XML documents. Independent of the input XML document the output relational schema remains the same. As only one table holds all the information, querying on the table becomes cumbersome if there is a high degree of nesting in the original XML document. This method is not a good way to store a large, deeply nested XML documents.

\begin{table}[!t]
  \centering
  \includegraphics[width=1.00\linewidth]{Figures/EdgeTable.png}
   \caption{Edge Schema representation of the Customer Data in figure~\ref{figEdge}.}
  \label{EdgeTable}
  \end{table}

\subsection {DTD- Independent Schema Mapping}
The paper by Zin Mar Kyu et al. \cite{DTDIndependent2009} suggests a schema oblivious mapping technique and explains the development of a relational schema from an input XML document. This process includes two different mappings DTD-independent schema mapping which extract table names and attributes to create a document schema and data mapping extracts XML and stores it into relational tables.

In DTD-independent schema mapping, the system parses through an input XML document and retrieves elements, attributes, and their values into element list and attribute list. The columns of these lists include name, value, and id or start id, end id, and parent id. It parses the element list to generate a new list comprising of no repeated elements. From the latest element list the system extracts the table name list, all the elements with more than one child elements makes entry into this list. Elements in the table name list, attribute list and element list are mapped to create a relational schema. As mentioned earlier, each table name element has an associated start id, which acts as primary key. Data mapping makes use of element values from the initial element list to populate the tuples of relational schema tables. 

This approach is reliable if the XML document does not have a supporting schema document, users are interested in regression mapping i.e., Relational to XML mapping. Though the paper provides one of the efficient schema-oblivious mapping techniques it fails in certain aspects. The resulting schema tables only hold customized primary keys, introduced by the system and each table has the end id column, which can be an overhead. The final relational schema might involve certain trivial tables. For example tables with their only columns as start id and end id and this paper does not outline a way to discard these tables.

\section{Schema Aware  Techniques}

\subsection {Shared Inlining}
The mapping strategies proposed by Shanmugasundaram et al. \cite{Shanmugasundaram:1999} are the primary ones to illustrate that it is indeed possible to use commercial relational database systems to evaluate powerful queries over XML documents. It has overcome some of the problems of storing all the XML data in a single relational table. This strategy used Document Type Descriptors (DTDs)  \cite {dtd2004} as their schema language to generate a relational schema. Then it parses the XML document conforming input DTD and loads them into tuples of relational tables.The figure~\ref{figDTDOPTable} shows the equivalent Shared Inlining Mapping of a DTD Customer data in the figure~\ref{figDTDIPTable}.
  
  \begin{figure}[!t]
  \centering
  \includegraphics[width=1\linewidth]{Figures/SharedDTDIP.png}
   \caption{DTD document, defining Customer data.}
  \label{figDTDIPTable}
  \end{figure}
  
Our system incorporates one of these mapping approaches known as shared inlining, elements with multiple occurrences transforms into tables whereas elements with a single occurrence are columns of the table corresponding to its parent element. Generating the relational schema for this mapping strategy is more complicated than the simple edge schema but anything of this nature is essential for large, deeply nested XML documents. 

  \begin{figure}[!b]
  \centering
  \includegraphics[width=0.85\linewidth]{Figures/SharedDTDOP.png}
   \caption{Shared Inlining Mapping of Sample Data.}
  \label{figDTDOPTable}
  \end{figure}

 
 \subsection {Constraints-Preserving Inlining } 
The algorithm suggested by Dongwon Lee et al. \cite{cpi} known as Constraints-Preserving Inlining Algorithm (CPI) converts an XML schema specification to a relational schema while preserving semantic constraints of the original XML schema. Here the XML schema specification denotes the document type definition (DTD) document. Many of the XML-to-Relational transformation algorithms suggested till then was mainly focusing on the structural conversion \cite{storingQuerying1999, Shanmugasundaram:1999, XPERANTO2000, stored1999  } ignoring the semantic constraints hidden in the original DTD. This algorithm identifies various semantics constraints in the original DTD and preserves them by rewriting the same in the final relational schema.
  
In a DTD declaration, there exist four possible cardinality relations between an element and its sub-elements. 
\begin{enumerate}
    \item(0,1): An element can have either zero or one sub-element.
    \item(1,1): An element must have one and only one sub-element.
    \item(0,N): An element can have zero or more sub-elements.
    \item(1,N): An element can have one or more sub-elements.
\end{enumerate}
    
  
 From the above relations, three constraints can be inferred. The first constraint is if a sub-element can be null or not. This can be implemented in a relational database by using the \enquote{NULL} or \enquote{NOT NULL} clause. The second constraint restricts an element to have at most one sub-element and is known as singleton constraint \cite{wood1999}. This constraint is one kind of Equality-Generating Dependency (EGDs) and can be enforced by \enquote{UNIQUE} construct.  Final constraint is for a given an element, whether its sub-element should occur or not. This is one of the categories of tuple-generating dependencies. TGDs in a relational model require that some tuples of a certain form be present in the table. Child and Parent constraints  are two useful forms of TGDs.

CPI algorithm extends the structural mapping of DTD to relational schema by introducing semantic constraints. In addition to CPI, Dongwon Lee et al. \cite{cpi, nesting2001, cpi2001} suggest two more algorithms Nesting-based Translation (NeT) and Constraints-based Translation (CoT) for translating Relational schema to XML schema. This paper makes significant contribution to the mapping techniques but the XML schema used in these techniques is DTD, which is not the latest version of XML schemas. Parsing DTD document is cumbersome when compared to that of parsing XSD, latest XML schema version. DTD documents does not provide information corresponding to the data types of the elements, which is a major drawback as this information is very vital for determining relational schema.

\begin{table}[!t]
  \centering
  \includegraphics[width=0.8\linewidth]{Figures/tableCPI.png}
   \caption{Cardinality relationships and the Semantic Constraints.}
  \label{figPCITable}
  \end{table}
 
\subsection{ShreX}
ShreX \cite{shreX2004, shrexurl} is an XML to Relational mapping framework, provided the first end-to-end solution to the relational storage of XML data problem. It makes use of XML schema to establish mappings from XML to relational schema. It contributed several new mapping strategies to the existing ones \cite{stored1999, costBased2002, storingQuerying1999, efficientStorage2000} and provides an API to access the mapping information. A user can specify the mappings by including annotations in an XML schema. As there exist multiple methods to associate annotations, ShreX is capable of expressing a wide range of mappings.  

The system allows users to annotate either manually or by using the interface provided. The annotation processor parses an annotated XML schema to check the mapping validity and creates the corresponding relational schema. Then the system accepts an XML document as input and loads the tuples into the relational database. 

Annotations specify how to represent elements of an XML schema definition language in the corresponding relational schema. The annotations supported by the system are modifying an attribute or an element into a new table, altering a table name or a column name or a column type and mapping an element or an attribute to a CLOB column.

Though ShreX design overlaps with the design of our system, there exist considerable differences between both the systems. Unlike ShreX, our system extracts the identity constraints from an input XSD, appends the same in the relational schema. It utilizes counters as keys when the input XML schema definition document fails to provide key constraint information. But, ShreX uses only counters as the primary and foreign keys in the relational schema irrespective of the information provided in the input document. Our system supports operations like Split a Table, Merge Tables, Delete a Table, Delete Columns and Reset Schema. Users can perform all these operations using the user interface. This makes performing these actions quite modest even for an amateur user.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Design %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Design and Implementation}
In this chapter, we present the design, implementation, and analysis of our system in following steps: 

\begin{enumerate}
\item Using XML Schema Object Model (XSOM) \cite{XSOMurl}, the system parses XML Schema Definition file and generates equivalent Relational Database Model.
\item Various schema operations our system supports enabling users to alter the relational schema.
\item Once the user finalizes schema, the next step is to fill the rows of the schema tables. For this step, the system uses DOM parser \cite{DOMurl} and accepts an XML document as input.
\item The key segments of the user interface.
\end{enumerate}

\section{Suggest Schema}

In this step, the System parses through the input XSD and extracts various data components. These components include obtaining table names, columns, keys, and XML paths. Besides, it also handles a variety of elements by introducing new keys and tables wherever necessary. This step involves following segments:

\begin{enumerate}
    \item Excerpt Table Names and Columns
    \item Extract Keys
    \item Introduce Keys
    \item Handling Recurring Elements
    \item Generate XML Paths    
\end{enumerate}

\subsection{Excerpt Table Names and Columns}
Initially, the system excerpts elements, attributes, and their data types. Elements can be either complex type or simple type. All elements with their types as complex are table names in the resulting suggested schema. The simple type child elements and the attributes of the complex type elements are columns of the respective tables. The Suggested schema in the  Figure~\ref{figSS} shows the complex type element \enquote{FullAddress} and its child elements of the XSD file in figure~\ref{figExample} are mapped into a table name and corresponding columns in the suggested relational schema.

\subsection{Extract Keys}
                 Here, the system fetches the identity keys and associated element information from the schema document. Identity keys indicate either primary keys or foreign keys and or unique keys. The associated element information involves the table names to which each of these keys belongs. In the case of foreign keys, the system extracts additional information about the referring table. The system appends this key data to the existing schema information. The suggested schema in figure~\ref{figSS} demonstrates this instance, the key with name \enquote{CustomerIDKey} in the example XML schema document is the primary key of the table \enquote{Customer}.

\subsection{Introduce Keys}

The system loops through all the tables in the schema and checks if each of them has any keys associated with them because relational schema makes no sense without keys. If they do not possess either a primary key or a foreign key, the system checks parent table for the keys. 

                If the parent table holds a primary key, then the system adds this column as the new foreign key of the table with parent table as the reference and adds the same to the child table column list. The \enquote{CustomerID} key of the table \enquote{FullAddress} in the suggested schema is an example of this occurrence.

                If the parent table includes a foreign key but not a primary key,  then the system introduces a new primary key to the parent table. The name of this primary key includes the table name and the string \enquote{PKID} separated by a hyphen (-). The same key acts as the foreign key for the table with reference table being the parent table. Here, the columns are unique if their labels, data types and XML paths are same. The primary key \enquote{Order-PKID} of the table \enquote{Order} in the suggested schema illustrates this instance.

                
\subsection{Handling Recurring Elements}

                Elements in the schema document can occur more than once. If elements with complex type are recurring then no problem persists as they form a separate table and each of its occurrence in the XML document will be a separate row in the table.  Whereas, a recurring simple element is not fair as a single table cannot support multiple occurrences of the same column.

                If any of the simple type elements are recurring, the system introduces a new table. This recurring simple element and the primary key of the parent table are the new table columns. Here parent table indicates the parent of the simple element. The new table key is the foreign key and refers to the primary key of the parent table. The table \enquote{Phone-Home} of the suggested schema falls into this category
  
                
\subsection{Generate XML Paths}

                While extracting elements and columns from the XML schema definition document. The system constructs XML paths \cite{XPathurl} for all the parent elements or table names. These XML paths are useful for populating the table values.

                If the parent element of a table is also a table in the schema, the table will inherit the XML path from its parent. The system implements this inheritance as most of the child and parent tables share the primary keys. For retrieving the table values from an XML document, the system considers the XML path of the parent instead of the actual XML path, as the primary key values are present in the path of the parent table. XML paths of all the tables generated by the system are shown in the suggested schema.
                
   \begin{figure}[!t]
  \centering
  \includegraphics[width=1\linewidth]{Figures/SuggSchema.png}
   \caption{Suggested Relational Schema for the example XSD in figure \ref{figExample}.}
  \label{figSS}
  \end{figure}
  
  \newpage
   Our system is examined against various XML Schema documents whose structure resembles the one shown in the figure ~\ref{figExample} and it works flawlessly generating relational schemas with the above features. The structure accommodates nested complex type elements with a varying number of occurrences, all kinds of identity keys and child elements of complex types with zero or multiple occurrences. 
  
  \newpage
  Figure ~\ref{figSS} describes the suggested schema for the example XSD in figure \ref{figExample}. The schema information presented in the ~\ref{figSS} is organized in the following order:
 \begin{enumerate}
\item Name of the table.
\item List of attribute information separated by  \enquote{;} and attribute information includes column name and its type.
\item Primary key (PK) with its data type separated by  \enquote{:}.
\item Foreign key (FK), data type and referred table partitioned by \enquote{:}.
\item XML path that should used for populating tables.
  \end{enumerate}
\section{Alter Schema}
 
 The suggested relational schema may not convince the user. So, our system allows users to perform a set of operations on the suggested schema using an inbuilt user interface. The set of operations to alter suggested schema include:
 
 \begin{enumerate}
    \item Split Tables
    \item Merge Tables
    \item Delete Table Columns
    \item Delete a Table
    \item Rename Tables
    \item Reset Schema
\end{enumerate}
    
\subsection{Split Tables}

                     The number of columns in tables suggested by the tool might be large or some columns in a table are vital and they need to be a part of a separate table. To address scenarios like these, this tool allows the user to perform Split operation on Tables.

   \begin{figure}[!t]
  \centering
  \includegraphics[width=0.85\linewidth]{Figures/Split1.png}
  \caption{Split tables operation on the \enquote{Customer} table.}
  \label{figSplit1}
  \end{figure}

                The user interface allows users to select multiple columns, which need to be part of the new table. Then, the system creates a new table, whose column list includes selected columns   and a foreign key referring to the parent table. The parent table name appended with \enquote{-1} is the name of the new table. Here, the parent table is the one on which split action occurred. XML path of the new table is similar to that of its parent table. The primary key of the parent table will be the foreign key of the new table. 

 
                The figure~\ref{figSplit1} illustrates creating a new table with \enquote{Fax} as column by choosing Split table operation on the \enquote{Customer} table and the figure~\ref{figSplit2} shows the newly formed table \enquote{Customer-1} and altered table \enquote{Customer}.

   \begin{figure}[!h]
  \centering
  \includegraphics[width=1.0\linewidth]{Figures/Split2.png}
  \caption{ \enquote{Customer} and \enquote{Customer-1} tables after Split Tables action.}
  \label{figSplit2}
  \end{figure}

\subsection{Merge Tables}
                    In some instances, suggested schema is more effective if tables with similar properties merge to form a new table.
 
   \begin{figure}[!b]
  \centering
  \includegraphics[width=1.0\linewidth]{Figures/merge3.png}
  \caption{ Merge tables operation on tables \enquote{FullAddress} and \enquote{Phone-Home}.}
  \label{figMerge1}
  \end{figure}

                The user can perform this merge action by choosing two different tables with similar properties in the user interface. This forms the new table with its columns being an augmentation of all non-key columns from the selected tables and a primary or foreign key column. After this operation, the resulting schema includes the new merged table and excludes two tables used for the merge operation. 

                   The label for the new table is the combination of two merged table names separated by a hyphen('-'). The similar properties correspond to tables with same primary keys or a foreign key of one table referring to the other table chosen for the merge operation.

   \begin{figure}[!t]
  \centering
  \includegraphics[width=0.85\linewidth]{Figures/merge4.png}
  \caption{ Updated table list and new table attributes after Merge Tables operation.}
  \label{figMerge2}
  \end{figure}
  
   In the figure~\ref{figMerge1}, two tables \enquote{Customer} and \enquote{Phone} are chosen for merge operation and the resulting table list and new table \enquote{Customer-Phone} columns are shown in figure~\ref{figMerge2}.

\subsection{Delete Table Columns}
  
    \begin{figure}[!h]
  \centering
  \includegraphics[width=0.85\linewidth]{Figures/delCol1.png}
   \caption{The columns of the ShipInfo table selected for deletion.}
  \label{figdel1}
  \end{figure}
  
                    The system gives a provision to delete some columns from tables. The user can choose a table of his interest from the user interface and then corresponding column list gets updated accordingly, the user can choose one or more columns to delete. The system updates the table with the new column list. This operation does not acknowledge deletion of primary and foreign keys.
   
                This task is helpful if any of the column lists in the suggested schema include keys with minimal importance. Figure ~\ref{figdel1} illustrates a user selecting columns of \enquote{ShipInfo} table to perform delete operation and the figure~\ref{figdel2} shows the resulting columns of \enquote{ShipInfo} table. 

    \begin{figure}[!h]
  \centering
  \includegraphics[width=0.8\linewidth]{Figures/delCol2.png}
   \caption{The \enquote{ShipInfo} table after Deleting columns.}
  \label{figdel2}
  \end{figure}
   

\subsection{Delete a Table}

   \begin{figure}[!t]
  \centering
  \includegraphics[width=0.73\linewidth]{Figures/delTab1.png}
   \caption{The \enquote{Customer-1} table selected for deletion.}
  \label{figdel3}
  \end{figure}
      
   Users can delete tables from the schema if no other table refers to them and if they are not a part of suggested schema. To perform this action users can select a table from table list using the user interface and the system deletes the table from resulting schema accordingly. 
 
  \begin{figure}[!h]
  \centering
  \includegraphics[width=0.7\linewidth]{Figures/delTable2.png}
   \caption{The \enquote{Customer-1} table removed from the new schema table list. }
  \label{figdel4}
  \end{figure} 
     
   The figure~\ref{figdel3} depicts deletion of the table \enquote{Customer-1} and the table list of the resulting schema is shown in the figure~\ref{figdel4}. 
   
 

\subsection{Rename Tables}

                    In some of the previous schema operations, the system has generated some new tables and labeled them using some predefined conventions. These predefined conventions might not be the appropriate labels for the tables. To address these circumstances, this system provides flexibility to re-label the newly constructed tables with the choice of the user.

 \begin{figure}[!b]
  \centering
  \includegraphics[width=0.8\linewidth]{Figures/rename1.png}
   \caption{The \enquote{FullAddress-Phone-Home} table is being renamed as \enquote{CustomerAddress}.}
  \label{rename1}
  \end{figure}
  
                To perform this action, the user needs to select the \enquote{Rename} operations followed by the table to rename in the user interface and then provide a new label for the elected table in the text editor. Figures~\ref{rename1} and~\ref{rename2} shows the name of the table is changed from \enquote{FullAddress-Phone-Home} to \enquote{CustomerAddress}. A sample final schema after a series of operations is shown in the figure~\ref{figFS}. 

   \begin{figure}[!h]
  \centering
  \includegraphics[width=0.9\linewidth]{Figures/rename2.png}
   \caption{The new \enquote{CustomerInfo} table attributes after rename operation.}
  \label{rename2}
  \end{figure}
                      
\subsection{Reset Schema}
  
 This allows the user to regain the suggested schema after performing a set of operations on them. This helps the user to correct his actions by restoring the schema to the original one. The user can perform this action just by selecting \enquote{Reset} operation from the operations list from the user interface. 
 
 The figure~\ref{reset} presents the resulting table list after performing the reset operation and the schema resembles same as the suggested schema shown in the figure~\ref{figSS}.
 
   \begin{figure}[!h]
  \centering
  \includegraphics[width=0.8\linewidth]{Figures/reset.png}
   \caption{The new table list after performing reset operation.}
  \label{reset}
  \end{figure}  
  
 \section{Populate Tables}
 
                  After performing a series of operations on the suggested schema, users confirms the final schema. The system is now accessible to populate the table values from an XML document. The XML document should obey the structure of the XML schema definition. Once the user finalizes the schema, the system requests for the input XML document.
 
   \begin{figure}[!b]
  \centering
  \includegraphics[width=0.95\linewidth]{Figures/custTable.png}
   \caption{\enquote{Customer} table with values.}
  \label{figPT}
  \end{figure}
  
                 To populate the schema tables, the system loops through the final schema and retrieves table names and their individual XML paths. Using these paths, the system fetches all the node lists existing in the respective paths. Then, the system iterates through the column elements and excerpts the same from the elements of the node lists to fill the tables.

                 The Primary and Foreign key values introduced by the system that are not part of the input XML Schema document are populated using counters.
                 
 
   \begin{figure}[!b]
  \centering
  \includegraphics[width=1.0\linewidth]{Figures/AlterSchema.png}
   \caption{Sample relational schema after performing a series of operations. }
  \label{figFS}
  \end{figure}
  
 \section{The user interface}
 
 The user interface is one of the key component of our system as it enables users in selecting appropriate schema by performing specific operations on suggested schema. For the implementation of the user interface, various concepts of Swing, a graphical user interface toolkit \cite {Swingurl} are utilized. The user interface implemented by our system is shown in the figure~\ref{figUI}.
 
 \subsection{Action Combo Box}
 This combo box is a drop-down list for the operations supported by the system on the suggested schema. It allows the user to select his choice of action on the schema. The operation list includes \enquote{Split Tables}, \enquote{Merge Tables}, \enquote{Delete Columns}, \enquote{Delete a Table}, \enquote{Rename Table} and \enquote{Reset Schema}. Based on the user's choice, the system updates the user interface. For instance, if the user opts to merge then the system activates both the table combo boxes allowing the user to select his choice of tables.
 
  \subsection{Table Combo Boxes}
                  The user interface comprises of two table combo boxes, each of them displays the table lists. The nature of the operation decides if a table box is active or not. Primary Table box is active during almost all the operations, whereas the secondary one is active only during the merge operation. As the user selects a table, the system updates the table models with columns of the table. 
                  
  \subsection{Table Models}
  Two table models used in the user interface displays the comprehensive information regarding the selected table. This includes column names, column types, and if a column is a primary or a foreign key. They allow users to select the rows during \enquote{Split Tables} and \enquote{Delete Columns} actions. Once a user selects the table combo box the corresponding table model gets activated.  
  
  \subsection{Text Editor}
  The text area occupies a major part of the user interface. Initially, it displays the suggested schema, as the user performs operations, the system updates the schema on the display. This text area also allows the user to input the new table name during the \enquote{Rename Table} operation. If the user selects the operation type as \enquote{Rename Table} and the table of his choice the display area clears the schema and waits for the user to enter the new table name. Once the user concludes rename operation, the text area gets back to the schema display mode. In this way, the text area serves multi-purpose in the user interface.
 
  \begin{figure}[!h]
  \centering
  \includegraphics[width= 1.0\linewidth]{Figures/UI4.png}
   \caption{The user interface layout.}
  \label{figUI}
  \end{figure}

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  TEI Shredding and System Analysis %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{System Analysis using TEI}
XML Schema Definition files of XML and TEI documents with varying complexity levels are fed into our system to monitor its functionality. The following key points include the system effectiveness  and limitations in converting these documents into relational data.

\begin{itemize}
\item The system successfully shreds input XSDs to suggest equivalent relational schema for all the input files that are relational in nature. Here, relational nature corresponds to hierarchical relation among the elements and supporting identity constraint information of the input schema documents. Consider the figure \ref{figTEI}, it represents XML Schema Definition file of TEI document, which is relational in nature and its equivalent relational schema suggested by the system in the figure \ref{figTEIOP}. 

\begin{figure}[!t]
  \centering
  \includegraphics[width= 0.88\linewidth]{Figures/TEI_File.png}
   \caption{An XML Schema Definition file defining a TEI structure.}
  \label{figTEI}
  \end{figure}
\item It parses all the XML Schema Definition files containing tags like \textless complexType\textgreater, \textless sequence\textgreater, \textless choice\textgreater, \textless any\textgreater, \textless key\textgreater, \textless keyref\textgreater, \textless simpleContent\textgreater and other common tags like \textless element\textgreater, \textless attribute\textgreater. It fails to capture information from the input schema files if they include advanced element components like \textless restriction\textgreater, \textless fixed\textgreater, \textless default\textgreater\ tags.

\item It utilizes the key information from input schema document to introduce the primary and foreign keys in the output suggested relational schema. Keys are essential for a good relational data model because they ensure row-level accessibility by allowing each record in a table to be precisely identified. Consider the figure \ref{figTEI}, the key information of this XSD file includes two keys, \textless head\textgreater\ and \textless type\textgreater. Our system parses this information and appends these columns as the primary keys of the tables \textless listwit\textgreater\ and \textless listbibl\textgreater\ in the relational schema, the same is shown in the figure \ref{figTEIOP}. Our system is tightly coupled with the identity constraints of the input XML Schema document to suggest relational schema and certain schema operations are also dependent on the input key information.

\item Our system preserves and transforms the hierarchical  nature of XML documents into relational nature by inheriting the primary key of the parent element table as foreign key of the child element table referring to the parent table. The system enables this inheritance  during the suggested schema phase of mapping. The same is illustrated in the figure \ref{figTEIOP} the element \textless type\textgreater\ is the primary key of the table \textless listbibl\textgreater\ and foreign key of the table \textless bibl\textgreater. 

\item Element \textless witness\textgreater\ in the figure \ref{figTEIrecur} is a recurring simple element with \enquote{xs:string} type. This implies that the simple element \textless witness\textgreater\ occurs multiple times within its parent element \textless listwit\textgreater, this is one of the prominent feature supported by the  XML documents. If the system maps this column as part of the table \textless listwit\textgreater\ then the concept of primary key fails because after populating tables one can observe that same primary key value occurs multiple times as the table has multiple \textless witness\textgreater values against the same primary key value \textless head\textgreater\ in the example. To address this difference in nature between the XML documents and Relational Databases our system introduces new table for simple elements with multiple occurrences along with the primary key of parent table as the foreign key of the new table.

   \begin{figure}[!t]
  \centering
  \includegraphics[width=0.7\linewidth]{Figures/TEIoccurences.png}
   \caption{ Sample TEI XSD code with recurring simple element. }
  \label{figTEIrecur}
  \end{figure}
  
\item Due to the heterogeneous nature of XML and Relational Databases, there might exist other possible relational schemas than the one suggested by the mapping technique. The system provides users provision to alter the suggested schema by performing certain operations mentioned in the section 4.2, providing flexibility to obtain the appropriate relational schema for the input XML Schema document. All these operations involve simple decision-making and easy to perform, making our XML to relational system a semi-automated tool as it automatically suggests relational schema for the input XML and TEI documents and then allows human intervention. 

\item Even though all the schema operations are easy to perform, users are expected to have a minimal knowledge regarding the concepts of relational tables for decision-making. For example, consider TEI or XML experts, as they have a profound knowledge of concepts of hierarchical nature and the relationship among the elements, decision making becomes quite simple.  

\item Once a user finalizes schema, the system prompts for an XML document and this document is expected to be valid with respect to the input XML schema document. The system does not include an XML schema validator to check the validity of the input XML document. It throws an error and leaves the tables unpopulated if the input XML document is not a valid document.
\end {itemize}
   \begin{figure}[!h]
  \centering
  \includegraphics[width=1.0\linewidth]{Figures/TEIOP.png}
   \caption{ Suggested relational schema of the TEI XSD shown in \ref{figTEI}. }
  \label{figTEIOP}
  \end{figure}

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% CONCLUSION %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \chapter {Conclusion}
 XML is a major standard for transmitting information over the Internet. Relational databases are a ubiquitous data storage and processing model. Transforming data between these two models is a key research area. This Thesis introduces a flexible, schema-aware mapping technique for converting XML data into an appropriate relational models by combining automatic and manual schema design. Our system generates relational data models for input TEI critical texts which are input to the the Improvise visualization environment. This approach helps in storing, querying, and analyzing input XML data and assists scholars to analyze TEI data and draw conclusions.

The first half of this thesis document introduced the motivation for this project, challenges in the conversion process, a summary of associated technologies, and a summary of current approaches to the problem.  Advantages and disadvantages of several existing mapping techniques, and some of their prominent features incorporated into our system, were described. By using existing approaches, we conclude that a schema-aware mapping technique an most appropriate and effective method of conversion. Having a supporting schema document describing XML as input is essential; XML Schema Definition documents are a suitable choice among the several schema supporting documents.

In the second half discusses the design and implementation of the mapping technique followed by the key components of the system. Introduces the principal strategies of our mapping techniques to develop suggested schema, the set of actions users can perform to obtain an appropriate schema and the system analysis.

The contributions of this thesis are as follows:

\begin{itemize}
\item A comprehensive data translation system shreds input XML documents into an equivalent relational database model using a schema-aware mapping technique.
\item Unlike existing systems, our system allows users to choose the best suitable schema by performing simple operations.
\item To the best of our knowledge, this system is the first one to consider identity constraints of the input XSD file in  suggesting the relational schema.
\item The system design is modular and easily accommodates changes and extensions to the system.
\item By providing an XML Schema Definition file, a Text Encoding Initiative file can also be converted into its corresponding relational model.
\item The system has the ability to accomplish the mapping of complex input XML files into relational databases quite efficiently.
\end{itemize}

\newpage
The current system reflects an attempt to design an efficient XML to relational mapping system with simple human intervention. Work in the TEI, XML, and Relational Database areas are so broad and diverse that there is a lot of scope for introducing new features into our system. Special consideration was taken during the design of the system to make it extensible for adding future features. A few of the potentially interesting extensions for our project include:

\begin{itemize}
\item Introducing new schema operations beyond the existing operations, such as adding primary keys, adding foreign keys, ordering  columns,  and rename columns.

\item The current user interface is simple and can be augmented with new features, such as a visual tool to display the XML trees of selected tables.

\item Allowing users to perform data wrangling operations, such as to split existing column values using separators.

\item Generate XML and XSD documents from the populated relational tables; in other words, an efficient mapping technique to transform Relational data back to XML. This is much simpler direction to process.

\item Capability to shred input XML Schema documents involving other elements or tags that are not taken into consideration in the current design, such as \enquote{default}, \enquote{fixed} , \enquote{restriction}.

\item Analyze the performance of the system and compare it with existing, fully automated approaches.

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% BIBLIOGRAPHY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{
\singlespacing

\bibliographystyle{abbrv}
\nocite{*}
\bibliography{thesis}
}





\end{document}
