Study on Optimization for Constraint Query Processing and Framework for Constraint Databases

点击翻译按钮获取中文摘要

A central research theme for constraint query processing includes a study on methods for solving constraint satisfaction problems in constraint databases. At the start of this study, we investigated many frameworks related to the processing of constraint databases. In order to proceed effectively, we focused on the following constraints : character sequence, network structure, spatial data, computational geometry, and finite domain. The fruitful productions of the study are below :(1) Character Sequence ConstraintsIn order to solve the character sequence constraints that are represented as extracting frequent subsequences from databases storing character or word sequences, we focused on molecular sequence databases and revealed methods for extracting frequent sequential patterns with a regular expression that has a capability to represent variable wildcard regions and ambiguous characters. Moreover, we revealed a dynamic load-balancing technique on distributed parallel processing to sp … More eed up the processing of frequent variable pattern extraction.(2) Network Structure ConstraintsTo solve the network structure constraints that are represented as understanding databases with a network relationship, we revealed a method for decomposing the network relation of a Blog user space using a clustering technique. Sub-networks extracted by the decomposition denote Blog user communities.(3) Spatial Data ConstraintsTo solve special data constraints included in constraint databases that store special information, we focused on logs of Web services that are accessed from cellular phones tracked by GPS, and revealed a method to speed up the extraction of frequent neighboring attribute patterns from constraint databases that store spatial objects located in two-dimensional space.(4) Computational Geometry ConstraintsTo solve computational geometry constraints, we focused on a reconciliation graph that is constructed by connecting the leaf layers of two ordered heterogeneous trees, i.e., genetic and taxonomic trees. As a result, we revealed a method that drastically reduces the number of crossovers on a reconciliation graph.(5) Finite Domain ConstraintsTo solve finite domain constraints defined over finite sets, we focused on a job-shop scheduling problem that is defined by n jobs J_1, J_2, ., J_n of varying sizes, which need to be scheduled on m identical machines, while trying to minimize the total length of the schedule. As a result, we revealed a method to speed up the computation of a constraint solver in PC cluster environments. Less