Query containment under bag and bag-set semantics

Conjunctive queries (CQs) are at the core of query languages encountered in many logic-based research fields such as AI, or database systems. The majority of existing work assumes set semantics but often in real applications the manipulation of duplicate tuples is required. One of the major problems that arises as part of advanced features of query optimization, data integration, query reformulation and many other research topics is testing for containment of such queries. In this work, we investigate the complexity of query containment problem for CQs under bag semantics (i.e. duplicate tuples are allowed in both the database and the results of queries) and under bag-set semantics (i.e. duplicates are allowed in the result of the queries but not in the database). We derive complexity results for these problems for five major subclasses of CQs; and we also find necessary conditions for CQ query containment. The general case of these problems remains open.     

A formal perspective on the view selection problem

The view selection problem is to choose a set of views to materialize over a database schema, such that the cost of evaluating a set of workload queries is minimized and such that the views fit into a prespecified storage constraint. The two main applications of the view selection problem are materializing views in a database to speed up query processing, and selecting views to materialize in a data warehouse to answer decision support queries. In addition, view selection is a core problem for intelligent data placement over a wide-area network for data integration applications and data management for ubiquitous computing. We describe several fundamental results concerning the view selection problem. We consider the problem for views and workloads that consist of equality-selection, project and join queries, and show that the complexity of the problem depends crucially on the quality of the estimates that a query optimizer has on the size of the views it is considering to materialize. When a query optimizer has good estimates of the sizes of the views, we show a somewhat surprising result, namely, that an optimal choice of views may involve a number of views that is exponential in the size of the database schema. On the other hand, when an optimizer uses standard estimation heuristics, we show that the number of necessary views and the expression size of each view are polynomially bounded. Received: November 20, 1001 / Accepted: May 30, 2002 / Published online: September 25, 2002     

查询代价视图选择问题的研究及实现

实视图选择问题是数据仓库研究的重要问题之一。数据仓库存储实视图主要为OLAP查询,用户查询响应时间是首要考虑的问题,提出了查询代价视图选择问题,给出了其代价模型。提出了对查询代价视图选择问题利用遗传算法来解决的方法和策略。经实验证明,该算法达到了良好的效果,效率高。     

Armstrong axioms and Boyce-Codd-Heath Normal Form under bag semantics

The theory of functional dependencies is based on relations, i.e. sets of tuples. Over relations, the class of functional dependencies subsumes the class of keys. Commercial database systems permit the storage of bags of tuples where duplicate tuples can occur. Over bags, keys and functional dependencies interact differently from how they interact over relations.We establish finite ground axiomatizations of keys and functional dependencies over bags, and show a strong correspondence to goal and definite clauses in classical propositional logic. We define a syntactic Boyce-Codd-Heath Normal Form condition, and show that the condition characterizes schemata that will never have any redundant data value occurrences in their instances. The results close the gap between the existing set-based theory of data dependencies and database practice where bags are permitted.     

View selection for designing the global data warehouse

A global data warehouse (DW) integrates data from multiple distributed heterogeneous databases and other information sources. A global DW can be abstractly seen as a set of materialized views. The selection of views for materialization in a DW is an important decision in the design of a DW. Current commercial products do not provide tools for automatic DW design. We provide a general method that, given a set of select-project-join queries to be satisfied by the DW, generates sets of materialized views that satisfy all the input queries. This process is complex since ‘common subexpressions' between the queries need to be detected and exploited. Our method is then applied to solve the problem of selecting such a materialized view set that fits in the space allocated to the DW for materialization and minimizes the combined overall query evaluation and view maintenance cost. We design algorithms which are implemented and we report on their experimental evaluation.     

On the declarative and procedural semantics of deductive object-oriented systems

We present declarative and procedural semantics for a deductive object-oriented language, Gulog. The declarative semantics is based on preferred minimal models. We describe both bottom-up and top-down query evaluation procedures and show that they are sound with respect to the declarative semantics. The results contribute to our understanding of the interaction of inheritance, overriding and deduction in the presence of both functional and set-valued methods, and multiple inheritance.     

View-based query processing: On the relationship between rewriting,answering and losslessness

As a result of the extensive research in view-based query processing, three notions have been identified as fundamental, namely rewriting, answering, and losslessness. Answering amounts to computing the tuples satisfying the query in all databases consistent with the views. Rewriting consists in first reformulating the query in terms of the views and then evaluating the rewriting over the view extensions. Losslessness holds if we can answer the query by solely relying on the content of the views. While the mutual relationship between these three notions is easy to identify in the case of conjunctive queries, the terrain of notions gets considerably more complicated going beyond such a query class. In this paper, we revisit the notions of answering, rewriting, and losslessness and clarify their relationship in the setting of semistructured databases, and in particular for the basic query class in this setting, i.e., two-way regular path queries. Our first result is a clean explanation of the relationship between answering and rewriting, in which we characterize rewriting as a “linear approximation” of query answering. We show that applying this linear approximation to the constraint-satisfaction framework yields an elegant automata-theoretic approach to query rewriting. As for losslessness, we show that there are indeed two distinct interpretations for this notion, namely with respect to answering, and with respect to rewriting. We also show that the constraint-theoretic approach and the automata-theoretic approach can be combined to give algorithmic characterization of the various facets of losslessness. Finally, we deal with the problem of coping with loss, by considering mechanisms aimed at explaining lossiness to the user.     

Strong equivalence of logic programs under the infinite-valued semantics

We consider the notion of strong equivalence [V. Lifschitz, D. Pearce, A. Valverde, Strongly equivalent logic programs, ACM Transactions on Computational Logic 2 (4) (2001) 526-541] of normal propositional logic programs under the infinite-valued semantics [P. Rondogiannis, W.W. Wadge, Minimum model semantics for logic programs with negation-as-failure, ACM Transactions on Computational Logic 6 (2) (2005) 441-467] (which is a purely model-theoretic semantics that is compatible with the well-founded one). We demonstrate that two such programs are strongly equivalent under the infinite-valued semantics if and only if they are logically equivalent in the corresponding infinite-valued logic. In particular, we show that strong equivalence of normal propositional logic programs is decidable, and more specifically coNP-complete. Our results have a direct implication for the well-founded semantics since, as we demonstrate, if two programs are strongly equivalent under the infinite-valued semantics, then they are also strongly equivalent under the well-founded semantics.     

Simultaneous determination of view selection and update policy with stochastic query and response time constraints

Data warehouses are built to reply query searches efficiently from integrated data of various systems. To improve the performance of the system, the issue of materializing views within data warehouses must be explored. This involves to pre-compute a set of selected views which are fact and dimension tables, under given resource and quality constraints. The quality constraints include query processing time, data maintenance time and the freshness of data when queries are placed. Then there is the policy of updating, which treats the time issue of data reloading in data warehouses. A model is proposed to determine the view selection and update policy when the arrival of queries follows Poisson processes with the constraints of system response time, storage space and query dependent currency of data (on systems capable of periodic and query-triggered updates). To the best of the researchers’ knowledge, no other research has considered all these factors in their models. A two-phase greedy algorithm was developed to determine the optimal update policy for the view selection problem. Numerous experiments were performed to explore the sensitivity of the proposed model under various constraints and system parameter settings. The results show that the model has reasonable responses to the tunings and that the proposed algorithm can rapidly find acceptable solutions.     

竞争合作型协同进化免疫算法及其在旅行商问题中的应用

为提高人工免疫算法的收敛性能,提出了一种竞争合作型协同进化免疫优势克隆选择算法(CCCICA).把生态学中的协同进化思想引入到人工免疫算法中,考虑了环境和子群间相互竞争的关系,子种群内部通过局部最优免疫优势,克隆扩增,自适应动态高频混合变异等相关算子的操作加快了种群亲和度成熟速度.把信息熵理论引入到算法中完善了种群的多样性.所有子种群共享同一高层优良库,并将其作为抗体子种群领导集合,对高层优良种群进行免疫杂交操作,通过迁移操作把优良个体返回到各子种群,实现了整个种群信息交流与协作.针对旅行商问题(traveling salesman problem,TSP)多个实例结果表明:与其它智能算法相比较该算法具有较好的性能.     

Modeling and solving the project selection and scheduling

This paper considers the integrated bi-objective problem of projects selection and scheduling to optimize both total expected benefit and resource usage variation. The benefit is time-dependent. Although this integrated problem has become a very active field of research, the available model and algorithms suffer from serious shortcomings. This paper analyzes the available methods and develops a novel mathematical model, in form of a mixed integer linear program, for the problem. Then, it proposes an ant colony optimization algorithm employing four features of ant generation, colonial, Pareto front updating, and pheromone updating mechanisms. To evaluate the proposed algorithm, it is compared with two available genetic algorithm and scatter search. Using comprehensive numerical experiments and statistical tools, it is shown that the proposed ant colony optimization outperforms the two available algorithms.     

结合语义与事务属性的QoS感知的服务优化选择

服务级别协议（SLA）等级感知的服务选择是NP难题。针对服务选择中维度与粒度方面的问题,提出结合语义与事务属性的服务质量（QoS）感知的服务优化选择模型。该模型从语义链接匹配度、QoS与事务三个维度对服务进行优化选择,并设计了支持多粒度的编码策略。针对服务选择中时间复杂度高的问题,提出了克隆选择与遗传算法相结合的混合优化算法。该算法首先采用动态适应度函数,逐代淘汰不满足约束的个体;其次给出了事务属性的优先级,并根据优先级设计了知识启发式的交叉与变异算子,以保证个体满足事务属性要求;最后在遗传算法中对优秀个体进行克隆选择,以增强对最优解的搜索能力。仿真实验中,该算法在服务选择的精确度和成功率方面均优于遗传算法;在时间花费上稍高于遗传算法但远低于穷举法。实验结果表明,所提算法能在较少时间花费的基础上保证服务选择的质量。     

A comprehensive framework for project selection problem under uncertainty and real-world constraints

This paper proposes a comprehensive framework for project selection problem under uncertainty and subject to real-world constraints, like segmentation, logical, and budget constraints. The framework consists of two main phases. In the first phase, the candidate projects are ranked considering the uncertainty, through a Monte Carlo simulation linked to a multi-criteria approach. In the second phase, the overall complete preorder of the projects in different iterations is first determined and then used in another Monte Carlo simulation linked to an integer programming module in order to effectively drive the final portfolio selection while satisfying the budget, segmentation and other logical constraints. The proposed framework is implemented in a case study to show its usefulness and applicability in practice. Finally, a comparison is carried out between the proposed approach and its deterministic counterpart and the corresponding results are discussed.     

On the location selection problem using analytic hierarchy process and multi-choice goal programming

Location selection is a crucial decision in cost/benefit analysis of restaurants, coffee shops and others. However, it is difficult to be solved because there are many conflicting multiple goals in the problem of location selection. In order to solve the problem, this study integrates analytic hierarchy process (AHP) and multi-choice goal programming (MCGP) as a decision aid to obtain an appropriate house from many alternative locations that better suit the preferences of renters under their needs. This study obtains weights from AHP and implements it upon each goal using MCGP for the location selection problem. According to the function of multi-aspiration provided by MCGP, decision makers can set multi-aspiration for each location goal to rank the candidate locations. Compared to the unaided selection processes, the integrated approach of AHP and MCGP is a better scientific and efficient method than traditional methods in finding a suitable location for buying or renting a house for business, especially under multiple qualitative and quantitative criteria within a shorter evaluation time. In addition, a real case is provided to demonstrate the usefulness of the proposed method. The results show that the proposed method is able to provide better quality decision than normal manual methods.     

A maintenance centric approach to the view selection problem

The View Selection Problem is an optimization problem designed to enhance query performance through the pre-computation and storage of select views given resource constraints. Assuring the materialized views can be updated within a reasonable time frame has become a chief concern for recent models. However, these methods are crafted simply to fit a solution within a feasible range and not to minimize the resource intensive maintenance process. In this paper, we submit two novel advances in terms of model formulation and solution generation to reduce maintenance costs. Our proposed model, the Minimum-Maintenance View Selection Problem, combines previous techniques to minimize and constrain update costs. Furthermore, we define a series of maintenance time reducing principles in solution generation embodied in a constructor heuristic. The model and constructor heuristic are evaluated using an existing clinical data warehouse and state-of-the-art heuristics. Our analysis shows our model produces the lowest-cost solution relative to extant models. Also, they indicate algorithms seeded with our constructor heuristic to be superior solutions to all other methods tested.     

On solving a maximin reliability estimation problem by selection of the instant for standby switching-on

The apparatus of duel situations with time instant selection was used to consider certain examples of analytical determination of the maximin of discontinuous criterion which characterizes the probability of maintaining system serviceability through selection of the optimal instant for activation of the redundant unit. A certain generalization to the problem of seeking the maximin of discontinuous criterion was also presented.     

A multiple-attribute method for concurrently solving the pickup-dispatching problem and the load-selection problem of multiple-load AGVs

The pickup dispatching and the load selection are two control problems in multiple-load AGVs. Although they affect each other and are affected by various attributes, many researchers have solved them as separate problems and adopted single-attribute methods for them. In this paper, we propose a multiple-attribute method that can solve them simultaneously. The proposed method has four stages: preparation, clustering, evaluation and execution. At the preparation stage, we calculate the weights for three attributes (i.e., slack time, waiting time and distance) that are important to our problems based on the system's current status. These weights will be useful at the second and third stages. At the clustering stage, parts needing vehicle service are clustered into part groups based on their similarity in these three attributes. At the evaluation stage, part groups are evaluated by considering these three attributes. The part group with the greatest evaluation value will be served by the AGV. At the execution stage, a procedure is proposed to assist the AGV in picking up parts efficiently. Simulations were conducted to test the performance of the proposed method in throughput, flow time, and tardiness. The results show that the proposed method outperforms not only single-attribute methods, but also methods that solve pickup dispatching and load selection separately.     

一类部分信息下带有劳动力收入的最优投资消费问题

最优投资消费问题属于一类典型的随机最优控制问题. 劳动力收入可通过影响期望效用从而影响投资消 费策略的制定. 本文首次在股票收益率和劳动力收入均为不可观测过程情形下, 研究了一类部分信息下的最优投资 消费问题. 首先综合运用Kalman滤波和非线性滤波, 得到了Zakai方程的显式解, 将部分信息下的随机最优控制问题 转化为完备信息下的随机最优控制问题. 其次通过求解HJB方程以及证明验证定理, 得到了该类最优投资消费问题 的最优策略以及值函数的显式表达. 最后采用真实市场数据进行仿真, 对比经典完备信息模型与本文部分信息模型 所得最优策略的差异, 验证了本文所得最优策略在有效利用市场信息方面的优越性.     

Portfolio selection problem with nonlinear wealth equations under non-extensive statistical mechanics for time-varying SDE

This paper is dedicated to the study of continuous-time mean–variance optimal portfolio selection problem with non-linear wealth equations under non-extensive statistical mechanics for the time-varying stochastic differential equation model. Firstly, we allow the returns and variance of risky assets are time-varying functions, which can fit the financial data better. Secondly, we consider an investor with the non-linear wealth equation. In fact, the wealth equations are not linear in many cases. The investor has to pay some taxes, which leads to a non-linear wealth equation. Moreover, since the return of the stocks price may be affected by a large investors portfolio selection, the wealth equation is non-linear in this case. Thirdly, the non-linear wealth equation driven by Tsallis distribution is constructed under non-extensive statistical mechanics, which can capture the characteristics of fat tails and aiguilles of the risky asset’s return. The viscosity solution of the HJB equation for the portfolio problem is proposed by the optimal stochastic control theory and Lagrange multiplier method. Finally, the efficient portfolio strategy and efficient frontier under non-extensive statistical mechanics are obtained. Furthermore, numerical analysis and real data study are discussed to show our results.