<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T14:14:45Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/5405" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/5405</identifier><datestamp>2017-03-21T17:21:14Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="ccadf312-a2cb-439b-83f4-1a11d7b4a340" confidence="600">Jiang, Wei</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2010-08-30T16:19:43Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2010-08-30T16:19:43Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2010-08-30T16:19:43Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2010</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/5405</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Support of order in query processing is a crucial component in&#xd;
relational database systems, not only because the output of a&#xd;
query is often required to be sorted in a specific order, but also&#xd;
because employing order properties can significantly reduce the&#xd;
query execution cost. Therefore, finding an effective approach to&#xd;
answer queries over ordered data is important to the efficiency of&#xd;
query processing in relational databases.&#xd;
&#xd;
In this dissertation, an ordered relational database model is&#xd;
proposed, which captures both data tuples of relations and tuple&#xd;
ordering in relations. Based on this conceptual model, ordered&#xd;
relational queries are formally defined in a two-sorted first-order calculus, which serves as a yardstick to evaluate&#xd;
expressive power of other ordered query representations.&#xd;
&#xd;
The primary purpose of this dissertation is to investigate the&#xd;
expressive power of different ordered query representations.&#xd;
Particularly, the completeness problem of ordered relational&#xd;
algebras is studied with respect to the first-order calculus:&#xd;
does there exist an ordered algebra such that any first-order expressible ordered&#xd;
relational query can be expressed by a finite sequence of ordered&#xd;
operations? The significance of studying the completeness problem&#xd;
of ordered relational algebras is in that the completeness of&#xd;
ordered relational algebras leads to the possibility of&#xd;
implementing a finite set of ordered operators to express all&#xd;
first-order expressible ordered queries in relational databases.&#xd;
&#xd;
The dissertation then focuses on the completeness problem of&#xd;
ordered conjunctive queries. This investigation is performed in an&#xd;
incremental manner: first, the ordered conjunctive queries with&#xd;
data-decided order is considered; then,&#xd;
the ordered conjunctive queries with t-decided order is&#xd;
studied; finally, the completeness problem for the general ordered&#xd;
conjunctive queries is explored. The completeness theorem&#xd;
of ordered algebras is proven for all three classes of ordered&#xd;
conjunctive queries.&#xd;
&#xd;
Although this ordered relational database model is only&#xd;
conceptual, and ordered operators are not implemented in this&#xd;
dissertation, we do prove that a complete set of ordered operators&#xd;
exists to retrieve all first order expressible ordered queries in&#xd;
the three classes of ordered conjunctive queries. This research&#xd;
sheds light on the possibility of implementing a complete set of&#xd;
ordered operators in relational databases to solve the performance&#xd;
problem of order-relevant queries.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">relational databases</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">The Completeness Problem of Ordered Relational Databases</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>