Thesis (M.S.C.I.T.)--Regis University, Denver, Colo., 2006. / Title from PDF title page (viewed on Apr. 7, 2006). Includes bibliographical references.

Thesis (M.S.C.I.T.)--Regis University, Denver, Colo., 2006. / Title from PDF title page (viewed on May 25, 2006). Includes bibliographical references.

Master of Science

Databases form the common component of many software systems, including mission critical transaction processing systems and multi-tier Internet applications. There is a large body of research in the performance of database management system components, while studies of overall database system performance have been limited. Moreover, performance models specifically targeted at the database design have not been extensively studied. This thesis attempts to address this concern by proposing a performance evaluation method for database designs based on queueing network models. The method is targeted at designs of large databases in which I/O is the dominant cost factor. The database design queueing network performance model is suitable in providing what if comparisons of database designs before database system implementation. A formal specification that captures the essential database design features while keeping the performance model sufficiently simple is presented. Furthermore, the simplicity of the modelling algorithms permits the direct mapping between database design entities and queueing network models. This affords for a more applicable performance model that provides relevant feedback to database designers and can be straightforwardly integrated into early database design development phases. The accuracy of the modelling technique is validated by modelling an open source implementation of the TPC-C benchmark. The contribution of this thesis is considered to be significant in that the majority of performance evaluation models for database systems target capacity planning or overall system properties, with limited work in detailed database transaction processing and behaviour. In addition, this work is deemed to be an improvement over previous methodologies in that the transaction is modelled at a finer granularity, and that the database design queueing network model provides for the explicit representation of active database rules and referential integrity constraints. / Iqra Foundation

År 1970 introducerades normalisering med syfte att organisera data i relationsdatabaser för att undvika redundant data och reducera risker för anomalier. Idag finns indikationer på att en mer nyanserad bild av normalisering behövs då dagens databaser ställs inför nya utmaningar och krav. Det här arbetet utförs i form av en fallstudie där en analys av tre databaser inom olika verksamheter genomförs. Med utgångspunkt i normalformerna genomförs en explorativ analys för att identifiera vilka aspekter som påverkar normalisering i industrin. Slutsatsen av arbetet är att det är svårt för en oberoende part till databasen att avgöra och tolka normalformernas uppfyllnad. Faktorer som påverkar normalisering av databaser är: utvecklarens intuition, användarens påverkan av datakvalitet samt den tekniska skuld som quickfixes orsakar. / Normalization was first introduced in 1970 with the purpose to organize data within relational databases in a way to avoid data redundancy and reduce the number of anomalies. As databases are facing new challenges and requirements, indications have been identified which points to a need for a more detailed view of normalization. This work is the outcome of a case study where three databases are analyzed. With the normal forms as starting point, an explorative analysis is made with the goal to identify different aspects that affects the way normalization is conducted within the industry. The conclusion is that it is difficult for an outsider to the database to interpret and determine whether the normal forms are fulfilled or not. Aspects affecting normalization are: the developer's intuition, users' impact on data quality and the technical debt that quickfixes creates.

Databases form the common component of many software systems, including mission critical transaction processing systems and multi-tier Internet applications. There is a large body of research in the performance of database management system components, while studies of overall database system performance have been limited. Moreover, performance models specifically targeted at the database design have not been extensively studied. This thesis attempts to address this concern by proposing a performance evaluation method for database designs based on queueing network models. The method is targeted at designs of large databases in which I/O is the dominant cost factor. The database design queueing network performance model is suitable in providing what if comparisons of database designs before database system implementation. A formal specification that captures the essential database design features while keeping the performance model sufficiently simple is presented. Furthermore, the simplicity of the modelling algorithms permits the direct mapping between database design entities and queueing network models. This affords for a more applicable performance model that provides relevant feedback to database designers and can be straightforwardly integrated into early database design development phases. The accuracy of the modelling technique is validated by modelling an open source implementation of the TPC-C benchmark. The contribution of this thesis is considered to be significant in that the majority of performance evaluation models for database systems target capacity planning or overall system properties, with limited work in detailed database transaction processing and behaviour. In addition, this work is deemed to be an improvement over previous methodologies in that the transaction is modelled at a finer granularity, and that the database design queueing network model provides for the explicit representation of active database rules and referential integrity constraints.

Approved for public release; distribution is unlimited / Currently, the most common approach in developing database applications is to use an object-oriented language for the frontend module and a relational database for the backend datastore. The major disadvantage of this approach is the well-known "impedance mismatch" in which some form of mapping is required to connect the objects in the frontend and the relational tuples in the backend. Java Data Objects (JDO) technology is recently proposed Java API that eliminates the impedance mismatch. By using JDO API, the programmers deal strictly with objects. JDO hides the details of the backend datastore by providing the object-oriented view of the datastore. JDO automatically handles the mapping between the objects and the underlying data in the relational database, which is hidden from the programmer. This thesis investigates the effectiveness of JDO. Part of the analysis will develop a database application using JDO. Although JDO provides the benefits of object-orientation in design and implementation of the databases, it is not immune from problems and limitations. The thesis will also analyze the advantages and disadvantages of using JDO and discuss the areas requiring improvements in future releases. / Major, Hellenic Air Force

在此論文中，我們為一系列應用與數據庫系統的問題設計有理論保證的數據結構與/或算法。這些問題可以分為兩類。第一類是一些計算機科學中的經典問題：近似最近鄰居(approximatenearest neighbor)問題、近似最近點對(approximate closest pair )問題、skyline問題(亦稱maxima問題)和二維正交區域聚合(2d orthogonalrange aggregation)問題。第二類則是在此論文中提出的新問題：歷史分位數(historical quantile)問題、k-跳步最短路徑(k-skipshortest path)問題、XML文檔中的最近關鍵字(nearest keyword)問題、最連通節點(most connected vertex )問題和先入先出索引(FIFOindexing)問題。對於每一個問題，或者我們給出最壞情況亦高效的(worst-case efficient)解決方案；或者當最壞情況性能的意義不大時，我們證明方法的實例最優性(instance optimality)。 / In this thesis, we propose data structures and/or algorithms with theoretical guarantees for solving a series of problems that find applications in database systems. These problems can be classified into two categories. The first one contains several classic problems in computer science, including the approximate nearest neighbor problem, the approximate closest pair problem, the skyline problem (a.k.a. the maxima problem), and 2d orthogonal range search. The second category, on the other hand, consists of problems that are newly introduced by this thesis: the historical quantile problem, the k-skip shortest path problem, the nearest keyword problem on XML documents, the most connected vertex problem, and the FIFO indexing problem. For each problem, we establish either the worstcase efficiency of our solutions, or their instance optimality when worst-case performance is not interesting. / Detailed summary in vernacular field only. / Sheng, Cheng. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 277-298). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Computation models --- p.1 / Chapter 1.2 --- Thesis contributions and organization --- p.2 / Chapter 2 --- Nearest Neighbors and Closest Pairs --- p.7 / Chapter 2.1 --- Introduction --- p.7 / Chapter 2.2 --- Problem settings --- p.10 / Chapter 2.3 --- The preliminaries --- p.11 / Chapter 2.3.1 --- Rigorous-LSH and ball cover --- p.12 / Chapter 2.3.2 --- Adhoc-LSH --- p.13 / Chapter 2.3.3 --- Details of hash functions --- p.15 / Chapter 2.4 --- LSB-tree --- p.16 / Chapter 2.4.1 --- Building a LSB-tree --- p.16 / Chapter 2.4.2 --- Nearest neighbor algorithm --- p.18 / Chapter 2.5 --- Theoretical analysis --- p.21 / Chapter 2.5.1 --- Quality guarantee --- p.21 / Chapter 2.5.2 --- Space and query time --- p.25 / Chapter 2.5.3 --- Comparison with rigorous-LSH --- p.25 / Chapter 2.6 --- Extensions --- p.26 / Chapter 2.7 --- Closest pair search --- p.30 / Chapter 2.7.1 --- Ball pair search --- p.30 / Chapter 2.7.2 --- Solving the closest pair problem --- p.34 / Chapter 2.8 --- Related work --- p.38 / Chapter 2.9 --- Experiments --- p.41 / Chapter 2.9.1 --- Data and queries --- p.41 / Chapter 2.9.2 --- Competitors for nearest neighbor search --- p.42 / Chapter 2.9.3 --- Competitors for closest pair search --- p.43 / Chapter 2.9.4 --- Computing environments and assessment metrics --- p.44 / Chapter 2.9.5 --- Behavior of LSH implementations --- p.45 / Chapter 2.9.6 --- Comparison of NN solutions --- p.48 / Chapter 2.9.7 --- Comparison of CP solutions --- p.51 / Chapter 2.10 --- Chapter summary --- p.54 / Chapter 3 --- The Skyline Problem and Its Variants --- p.57 / Chapter 3.1 --- Introduction --- p.57 / Chapter 3.1.1 --- Previous results --- p.58 / Chapter 3.1.2 --- Our results --- p.60 / Chapter 3.2 --- Preliminaries --- p.63 / Chapter 3.3 --- Our skyline algorithm --- p.66 / Chapter 3.3.1 --- 3d --- p.67 / Chapter 3.3.2 --- 4d --- p.69 / Chapter 3.3.3 --- Higher dimensionalities --- p.70 / Chapter 3.3.4 --- Eliminating the general-position assumption --- p.74 / Chapter 3.4 --- Variants of the skyline problem --- p.74 / Chapter 3.5 --- Low-cardinality domains --- p.77 / Chapter 3.6 --- Non-fixed dimensionality --- p.80 / Chapter 3.6.1 --- An improved algorithm in internal memory --- p.80 / Chapter 3.6.2 --- Externalizing the algorithm --- p.82 / Chapter 3.7 --- Chapter summary --- p.83 / Chapter 4 --- Orthogonal Range Aggregation --- p.85 / Chapter 4.1 --- Introduction --- p.85 / Chapter 4.1.1 --- Applications --- p.86 / Chapter 4.1.2 --- Computation model --- p.87 / Chapter 4.1.3 --- Previous results --- p.87 / Chapter 4.1.4 --- Our results --- p.88 / Chapter 4.2 --- Preliminaries --- p.91 / Chapter 4.3 --- Bundled compressed B-tree --- p.93 / Chapter 4.4 --- Three-sided window-max --- p.95 / Chapter 4.4.1 --- The first structure --- p.96 / Chapter 4.4.2 --- The improved structure --- p.97 / Chapter 4.5 --- Segment-intersection-max --- p.101 / Chapter 4.6 --- Stabbing-max --- p.103 / Chapter 4.6.1 --- Ray-segment-max --- p.103 / Chapter 4.6.2 --- Stabbing-max --- p.106 / Chapter 4.7 --- Rectangle-intersection-sum --- p.106 / Chapter 5 --- Persistent Quantiles --- p.109 / Chapter 5.1 --- Introduction --- p.109 / Chapter 5.1.1 --- Problem definition --- p.111 / Chapter 5.1.2 --- Previous work --- p.112 / Chapter 5.1.3 --- Our main results --- p.113 / Chapter 5.2 --- Space lower bounds for historical quantile search --- p.114 / Chapter 5.3 --- A structure for historical quantile search --- p.119 / Chapter 5.3.1 --- Persistence technique --- p.119 / Chapter 5.3.2 --- High-level rationales and challenges --- p.121 / Chapter 5.3.3 --- The structure and its query algorithm --- p.122 / Chapter 5.3.4 --- Construction algorithm --- p.127 / Chapter 5.3.5 --- Complexity analysis --- p.130 / Chapter 5.3.6 --- An alternative simple solution --- p.132 / Chapter 5.4 --- Experiments --- p.133 / Chapter 5.4.1 --- Competitors and metrics --- p.133 / Chapter 5.4.2 --- Performance characteristics --- p.133 / Chapter 5.4.3 --- Performance on real data --- p.136 / Chapter 5.5 --- Chapter summary --- p.138 / Chapter 6 --- k-Skip Shortest Paths --- p.141 / Chapter 6.1 --- Introduction --- p.141 / Chapter 6.2 --- Related work --- p.144 / Chapter 6.2.1 --- Dijkstra and reach --- p.144 / Chapter 6.2.2 --- More results on SP computation --- p.148 / Chapter 6.3 --- k-skip Shortest Paths --- p.150 / Chapter 6.4 --- k-skip graph --- p.152 / Chapter 6.4.1 --- Size of k-skip cover --- p.152 / Chapter 6.4.2 --- Computing a k-skip cover --- p.154 / Chapter 6.4.3 --- Computing a k-skip graph --- p.156 / Chapter 6.5 --- Query algorithm --- p.158 / Chapter 6.5.1 --- High-level description --- p.158 / Chapter 6.5.2 --- Reach* --- p.160 / Chapter 6.5.3 --- Zoom-in --- p.163 / Chapter 6.6 --- Experiments --- p.164 / Chapter 6.7 --- Chapter summary --- p.168 / Chapter 7 --- Nearest Keyword Queries on XML Documents --- p.171 / Chapter 7.1 --- Introduction --- p.171 / Chapter 7.1.1 --- Motivation --- p.171 / Chapter 7.1.2 --- Contributions --- p.174 / Chapter 7.2 --- Preliminaries --- p.175 / Chapter 7.3 --- Nearest keyword search --- p.178 / Chapter 7.3.1 --- Overview --- p.178 / Chapter 7.3.2 --- TVP characteristics --- p.180 / Chapter 7.3.3 --- Finding the minimum TVP --- p.183 / Chapter 7.4 --- Nearest keyword search as an operator --- p.186 / Chapter 7.4.1 --- XPath evaluation --- p.186 / Chapter 7.4.2 --- Finding approximate group steiner trees --- p.192 / Chapter 7.5 --- Related work --- p.193 / Chapter 7.6 --- Experiments --- p.196 / Chapter 7.7 --- Chapter summary --- p.202 / Chapter 8 --- FIFO Indexes for Decomposable Problems --- p.203 / Chapter 8.1 --- Introduction --- p.203 / Chapter 8.1.1 --- FIFO update scheme and its applications --- p.203 / Chapter 8.1.2 --- Technical motivations --- p.204 / Chapter 8.1.3 --- Problems, computation models, and basic notations --- p.205 / Chapter 8.1.4 --- Previous results --- p.207 / Chapter 8.1.5 --- Our results --- p.210 / Chapter 8.2 --- Making a static structure FIFO --- p.213 / Chapter 8.2.1 --- The RAM model --- p.214 / Chapter 8.2.2 --- The EM model --- p.220 / Chapter 8.3 --- Solving concrete problems --- p.221 / Chapter 8.4 --- Chapter summary --- p.225 / Chapter 9 --- The Most Connected Vertex Problem --- p.227 / Chapter 9.1 --- Introduction --- p.227 / Chapter 9.1.1 --- Motivation --- p.227 / Chapter 9.1.2 --- Our main results --- p.230 / Chapter 9.2 --- Problem and Related Work --- p.232 / Chapter 9.3 --- Preliminaries --- p.235 / Chapter 9.4 --- Exact algorithms --- p.239 / Chapter 9.5 --- Theoretical analysis of the exact algorithms --- p.244 / Chapter 9.5.1 --- The randomized algorithm class --- p.244 / Chapter 9.5.2 --- The deterministic algorithm class --- p.251 / Chapter 9.6 --- Approximate algorithms and their analysis --- p.254 / Chapter 9.6.1 --- 1-MCV --- p.254 / Chapter 9.6.2 --- k-MCV --- p.259 / Chapter 9.7 --- Experiments --- p.262 / Chapter 9.7.1 --- Datasets --- p.262 / Chapter 9.7.2 --- Methods --- p.264 / Chapter 9.7.3 --- How pessimistic is the worst case? --- p.265 / Chapter 9.7.4 --- Performance of random-probe algorithms --- p.266 / Chapter 9.7.5 --- Performance of deterministic-probe algorithms --- p.268 / Chapter 9.7.6 --- Performance of AMCV --- p.269 / Chapter 9.8 --- Chapter summary --- p.274 / Bibliography --- p.277

by Yen-Hui Hung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (leaves 76-78). / Abstract --- p.i / Acknowledgments --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background ® / Chapter 2.1 --- Multilingual Information Processing --- p.6 / Chapter 2.1.1 --- Codesets --- p.6 / Chapter 2.1.2 --- Converters --- p.8 / Chapter 2.1.3 --- Collations --- p.8 / Chapter 2.1.4 --- Internationalization and Localization --- p.9 / Chapter 2.2 --- OBST --- p.10 / Chapter 2.3 --- Related Work --- p.11 / Chapter 2.3.1 --- Sybase --- p.11 / Chapter 2.3.2 --- Oracle --- p.13 / Chapter 2.3.3 --- COBASE --- p.15 / Chapter 2.3.4 --- SQL92 Standard --- p.15 / Chapter 3 --- Defects of Existing Systems and Proposed Language Extensions --- p.21 / Chapter 3.1 --- Defects of Existing Methods - Locale Model --- p.22 / Chapter 3.2 --- Defects of SQL92 --- p.22 / Chapter 3.3 --- Proposed Language Extensions --- p.24 / Chapter 3.3.1 --- Inserting tuples --- p.24 / Chapter 3.3.2 --- Updating tuples --- p.25 / Chapter 3.3.3 --- Querying (Retrieving tuples) --- p.26 / Chapter 3.3.4 --- String matching --- p.26 / Chapter 3.3.5 --- Performing Joins --- p.28 / Chapter 3.3.6 --- Sorting and Indexing --- p.30 / Chapter 4 --- DBMS Design and Implementation --- p.32 / Chapter 4.1 --- System Architecture --- p.34 / Chapter 4.2 --- Lexical Analyzer and Parser --- p.36 / Chapter 4.3 --- Database Objects --- p.37 / Chapter 4.4 --- Data Dictionary --- p.39 / Chapter 4.5 --- Character Objects Related Facilities --- p.41 / Chapter 4.5.1 --- Codesets --- p.42 / Chapter 4.5.2 --- Collations --- p.46 / Chapter 4.5.3 --- Converters --- p.48 / Chapter 4.6 --- Indexing --- p.50 / Chapter 4.7 --- Query Processor --- p.52 / Chapter 4.7.1 --- Join --- p.54 / Chapter 4.7.2 --- Sorting tuples - the order by clause --- p.54 / Chapter 4.7.3 --- "Group Structure, Aggregate Functions and Projection" --- p.55 / Chapter 4.8 --- Scalar and Conditional Expressions --- p.56 / Chapter 4.8.1 --- Representation of Scalar and Condition Expressions --- p.57 / Chapter 4.8.2 --- Implementations --- p.58 / Chapter 4.9 --- User Interface --- p.59 / Chapter 5 --- Case Study - A Bookshop --- p.62 / Chapter 5.1 --- Creating tables and inserting tuples --- p.62 / Chapter 5.2 --- Updating Tuples --- p.65 / Chapter 5.3 --- Querying --- p.65 / Chapter 5.4 --- String Matching --- p.66 / Chapter 5.5 --- Performing Joins --- p.67 / Chapter 5.6 --- Ordering Display --- p.68 / Chapter 5.7 --- Indexing --- p.70 / Chapter 6 --- Conclusions and Future Work --- p.73 / Bibliography --- p.76 / Chapter A --- Grammer Rules --- p.79 / Chapter A.1 --- Data Definition Language --- p.79 / Chapter A.2 --- Data Manipulation Language --- p.82 / Chapter A.3 --- Condition Expressions --- p.83 / Chapter A.4 --- Scalar Expressions --- p.84 / Chapter A.5 --- Data Type --- p.85 / Chapter A.6 --- Names and Identifiers --- p.87 / Chapter A.7 --- Lexical Element --- p.88 / Chapter B --- Programmers' Guide --- p.90 / Chapter B.l --- Charset.obst --- p.92 / Chapter B.2 --- Table.obst --- p.95 / Chapter B.3 --- dbSchema.obst --- p.101 / Chapter B.4 --- dbEnv.obst --- p.103 / Chapter B.5 --- Query.obst --- p.104 / Chapter B.6 --- Misc.obst and External.obst --- p.117 / Chapter B.7 --- Main --- p.118 / Chapter B.8 --- RPC interfaces --- p.120 / Chapter C --- Installation Manual --- p.122 / Chapter C.l --- Steps to install the DBMS server --- p.123 / Chapter C.2 --- Steps to install the WWW client --- p.124 / Chapter D --- User Manual --- p.125 / Chapter D.l --- User Interface Layout --- p.125 / Chapter D.2 --- Steps in Performing Database Operations --- p.128 / Chapter D.2.1 --- Creating new tables --- p.129 / Chapter D.2.2 --- Browsing existing tables --- p.131 / Chapter D.2.3 --- Inserting new records --- p.131 / Chapter D.2.4 --- Deleting records --- p.132 / Chapter D.2.5 --- Creating indexes --- p.132 / Chapter D.2.6 --- Showing existing schemas and tables --- p.133

Thesis (M.S.)--Brigham Young University. School of Technology, 2006. / Includes bibliographical references (p. 119-121).