M.Sc. (Computer science) / Knowledge representation suffers from certain problems, which is not a result of the inadequacies of knowledge representation schemes, but of the way in which they are used and implemented. In the first part of this dissertation we examine the relational model (as used in relational database management systems) and we examine frames (a knowledge representation scheme used in expert systems), as proposed by M. Minsky [MIN75]. We then provide our own definition of frames. In the second part, we examine similarities between the two models (the relational model and our frame model), establishing frames as a superclass of relations. We then define normalization for frames and examine how normalization might solve some of the problems we have identified. We then examine the integration of knowledge-based systems and database management systems and classify our normalization of frames as such an attempt. We conclude by examining the place of normalization within the expert system development life cycle

Master of Science

SQL provides a fairly straightforward means of querying database data. However, as with all command languages, SQL can get very complicated, even for experienced programmers. This complexity can be intimidating to the novice or intermediate user who needs to access data from a database with complex SQL statements, especially when users don't want to know or even become familiar with a command oriented query language like SQL. / Master of Science

No description available.

We study representation systems for relational data based on relational algebra expressions with unions, products, and singleton relations. Algebraic factorisation using the distributivity of product over union allows succinct representation of many-to-many relationships; further succinctness is brought by sharing repeated subexpressions. We show that these techniques are especially applicable to results of conjunctive queries. In the first part of the dissertation we derive tight asymptotic size bounds for two flavours of factorised representations of results of conjunctive queries. Any conjunctive query is characterised by rational parameters that govern the factorisability of its results independently of the database instance. We relate these parameters to fractional edge covers and fractional hypertree decompositions. Factorisation naturally extends from relational data to its provenance. We characterise conjunctive queries by tight bounds on their readability, which captures how many times each input tuple is used to contribute to an output tuple, and we define syntactically the class of queries with bounded readability. In the second part of the dissertation we describe FDB, a relational database engine that uses factorised representations at the physical layer to reduce data redundancy and boost query performance. We develop algorithms for optimisation and evaluation of queries with selection, projection, join, aggregation and order-by clauses on factorised representations. By introducing novel operators for factorisation restructuring and a new optimisation objective to maintain intermediate and final results succinctly factorised, we allow query evaluation with lower time complexity than on flat relations. Experiments show that for data sets with many-to-many relationships, FDB can outperform relational engines by orders of magnitude.

published_or_final_version / abstract / Computer Science / Master / Master of Philosophy

In the second part, we further investigate algebraic structure of relational databases. The decomposition theory for relational databases is based on data dependencies. Nevertheless, the set-theoretic representations of data dependencies in terms of the attributes of relation schemes are incompatible with partial ordering operations. This brings a gap between the database decomposition theory and our theory. We identify the unique component constraint as a necessary condition for binary decomposition of a relation, i.e. there is a unique component for every join key value in the bipartite graph. We generalize the running intersection property as the partial ordering counterpart under the unique component constraint. It follows that we characterize the multivalued and acyclic join dependencies in terms of commutativity and unique component constraint. This shows the decompositions specified by these dependencies are special cases of our theory. Furthermore, we propose a lossless decomposition method for the class of data dependencies that is based on commutativity, and demonstrate that existing relational operations are sufficient for this method. / Relational information systems, systems that can be represented by tables of finite states, are widely used in many areas such as logic circuits, finite state machines, and relational databases. Decomposition is a natural method to remove redundancy of complex systems. It divides a system into a network of simpler components. In order to preserve the original functionalities of the system, any valid decomposition has to be lossless. This work is divided into two parts. In the first part, we develop a mathematical model for lossless decompositions of relational information systems. Commutative partitions play an important role in decompositions. The commutativity is essentially a general algebraic formulation of independency of two partitions. We express the interdependency of two commutative partitions by a bipartite graph, and classify the hierarchical independency structures by the topological property of bipartite graphs. In particular, we show that two partitions are decomposable, the strongest kind of independency, if and only if the associated bipartite graph is uniform. Moreover, we adopt Shannon's entropy to quantify the amount of information contained in each partition, and formulate information-lossless decompositions by entropy equalities. Under the assumption of running intersection property, we show that the general formulation of information-lossless decompositions of relational information systems is given by the entropy inclusion-exclusion equality. We also present the applications of these formulations to the above engineering systems to manifest the information-lossless decomposition processes. / Lo, Ying Hang. / Adviser: Tony T. Lee. / Source: Dissertation Abstracts International, Volume: 70-06, Section: B, page: 3606. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 159-163). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

In this dissertation, we propose new design guidelines to reduce the amount of redundancy that databases carry. We use techniques from information theory to define a measure that evaluates a database design based on the worst possible redundancy carried in the instances. We then continue by revisiting the design problem of relational data with functional dependencies, and measure the lowest price, in terms of redundancy, that has to be paid to guarantee a dependency-preserving normalization for all schemas. We provide a formal justification for the Third Normal Form (3NF) by showing that we can achieve this lowest price by doing a good 3NF normalization. We then study the design problem for XML documents that are views of relational data. We show that we can design a redundancy-free XML representation for some relational schemas while preserving all data dependencies. We present an algorithm for converting a relational schema to such an XML design. We finally study the design problem for XML documents that are stored in relational databases. We look for XML design criteria that ensure a relational storage with low redundancy. First, we characterize XML designs that have a redundancy-free relational storage. Then we propose a restrictive condition for XML functional dependencies that guarantees a low redundancy for data values in the relational storage.

In this dissertation, we propose new design guidelines to reduce the amount of redundancy that databases carry. We use techniques from information theory to define a measure that evaluates a database design based on the worst possible redundancy carried in the instances. We then continue by revisiting the design problem of relational data with functional dependencies, and measure the lowest price, in terms of redundancy, that has to be paid to guarantee a dependency-preserving normalization for all schemas. We provide a formal justification for the Third Normal Form (3NF) by showing that we can achieve this lowest price by doing a good 3NF normalization. We then study the design problem for XML documents that are views of relational data. We show that we can design a redundancy-free XML representation for some relational schemas while preserving all data dependencies. We present an algorithm for converting a relational schema to such an XML design. We finally study the design problem for XML documents that are stored in relational databases. We look for XML design criteria that ensure a relational storage with low redundancy. First, we characterize XML designs that have a redundancy-free relational storage. Then we propose a restrictive condition for XML functional dependencies that guarantees a low redundancy for data values in the relational storage.

Thesis (M. Phil.)--University of Hong Kong, 2002. / Includes bibliographical references.