We propose a novel approach to encapsulate non-deterministic computations in functional logic programs. Our approach is based on set functions that return the set of all the results of a corresponding ordinary operati...
详细信息
ISBN:
(纸本)9781605585680
We propose a novel approach to encapsulate non-deterministic computations in functional logic programs. Our approach is based on set functions that return the set of all the results of a corresponding ordinary operation. A characteristic feature of our approach is the complete separation between a usually-non-deterministic operation and its possibly-non-deterministic arguments. this separation leads to the first provably order-independent approach to computing the set of values of non-deterministic expressions. the proof is provided within the framework of graph rewriting in constructor-based systems. We propose an abstract implementation of our approach and prove its independence of the order of evaluation. Our approach solves easily and naturally problems mishandled by current implementations of functional logic languages.
Naive parallel implementation of nondeterministic systems (such as a theorem proving system) and languages (such as a logic, constraint, or a concurrent constraint language) can result in poor performance. We present ...
详细信息
ISBN:
(纸本)0818677937
Naive parallel implementation of nondeterministic systems (such as a theorem proving system) and languages (such as a logic, constraint, or a concurrent constraint language) can result in poor performance. We present three optimization schemas based on flattening of the computation tree, procrastination of overheads, and sequentialization of computations that can be systematically applied to parallel implementations of non-deterministic systems/languages to reduce the parallel overhead and to obtain improved efficiency of parallel execution. the effectiveness of these schemas is illustrated by applying them to the ACE parallel logic programming system. Performance data presented shows that considerable improvement in performance can result.
"Scrap Your Boilerplate" (SYB) is an established style of generic functional programming. the present paper reconstructs SYB within the Prolog language withthe help of the univ operator and higher-order log...
详细信息
ISBN:
(纸本)9781605585680
"Scrap Your Boilerplate" (SYB) is an established style of generic functional programming. the present paper reconstructs SYB within the Prolog language withthe help of the univ operator and higher-order logic programming techniques. We pay attention to the particularities of Prolog. For instance, we deal with traversal of non-ground terms. We also develop an alternative model of SYB-like traversal based on metaprogramming. this generative, type-driven model is also amenable to type-driven optimization.
Deriving deadline and period for update transactions has long been recognized as an important problem in real-time database research. Despite years of active study, the state of the art only focuses on scheduling of u...
详细信息
ISBN:
(纸本)9781538608401
Deriving deadline and period for update transactions has long been recognized as an important problem in real-time database research. Despite years of active study, the state of the art only focuses on scheduling of update or control transaction separately. In this paper, we study the problem of deriving deadlines for update transactions in co-scheduling environment upon uniprocessor platforms. We consider how to compute deadlines for update transactions to minimize the total workload of the transaction set, while maintaining the temporal validity of real-time data objects and guaranteeing the EDF-schedulability of the hybrid transaction set. To address this problem, we propose a linear programming approach to derive deadlines for update transactions, namely DC-LP (Deadline Calculation based on Linear programming). Finally, the success ratio, workload and time performance of DC-LP are evaluated through extensive simulation experiments.
Most alias analyses produce approximate results in the presence of array slices. this may lead to inefficient code which is of concern, especially, in languages like Fortran90. in this paper, we present an overview of...
详细信息
ISBN:
(纸本)0818677937
Most alias analyses produce approximate results in the presence of array slices. this may lead to inefficient code which is of concern, especially, in languages like Fortran90. in this paper, we present an overview of a static alias analysis that gives accurate results in the presence of array slices in Fortran90.
programming by demonstration (PBD) systems offer an advantage of easy programming. However, they have difficulty in inferring user intent behind user actions, because of ambiguity of those actions. this paper describe...
详细信息
programming by demonstration (PBD) systems offer an advantage of easy programming. However, they have difficulty in inferring user intent behind user actions, because of ambiguity of those actions. this paper describes a novel approach `action management' to the inference problem. It is based on an idea that PBD systems are able to properly determine user intent by making users demonstrate only non-ambiguous actions. Withthe action management approach, a PBD system for creating database queries, called DADIE, can correctly infer user intent even in creating complex queries, such as join, group-by and subquery.
BPQL is a novel query language for querying business process specifications, introduced recently in [5,6]. It is based on an intuitive model of business processes as rewriting systems, an abstraction of the emerging B...
详细信息
ISBN:
(纸本)9783540759867
BPQL is a novel query language for querying business process specifications, introduced recently in [5,6]. It is based on an intuitive model of business processes as rewriting systems, an abstraction of the emerging BPEL (Business Process Execution Language) standard [7]. BPQL allows users to query business processes visually, in a manner very analogous to the language used to specify the processes. the goal of the present paper is to study the formal model underlying BPQL and investigate its properties as well as the complexity of query evaluation. We also study its relationship to previously suggested formalisms for process modeling and querying. In particular we propose a query evaluation algorithm of polynomial data complexity that can be applied uniformly to queries on the structure of the process specification as well as on the potential behavior of the defined process. We show that unless P=NP the efficiency of our algorithm is asymptotically optimal.
We present the graph operational semantics approach used for defining NiMo nets execution, which mix lazy, data-driven and a weak form of eager evaluation, all in parallel. NiMo is a totally graphic language from the ...
详细信息
ISBN:
(纸本)9781605585680
We present the graph operational semantics approach used for defining NiMo nets execution, which mix lazy, data-driven and a weak form of eager evaluation, all in parallel. NiMo is a totally graphic language from the family of higher order typed languages but with a strong data-flow inspiration. Programs are process networks that evolve showing the full state at each execution step and can be dynamically changed or completed. In NiMo parallelization is implicit. the conjunction of two kinds of tags determine which processes are able to act in the same execution step. According to their tag, processes can behave in five modes that can be globally or locally set for each one, and can be also dynamically changed. Combining modes gives a very flexible way to experiment different strategies to increase processor usage, decrease channel population, and achieve subnet synchronization. Together with symbolic execution it also provides the means for generative and multi-stage programming.
this paper's revisit of infinite relational databases, a model traditionally perceived as purely theoretical, was sparked by a concrete implementation setting, and the results obtained here were used in a practica...
详细信息
ISBN:
(纸本)9783540759867
this paper's revisit of infinite relational databases, a model traditionally perceived as purely theoretical, was sparked by a concrete implementation setting, and the results obtained here were used in a practical database problem. in the course of implementing a database system for querying Java software, we found that the universe of Java code can be effectively modeled as an infinite database. this modeling makes it possible to distinguish between queries which are "open-ended," that is, whose result may grow as software components are added into the system, and queries which are "closed," in that their result does not change as the software base grows. Further, closed queries can be implemented much more efficiently than open queries. Achievements include an algorithm for distinguishing between these two kinds of queries (we assume that queries are written in Datalog), and an algorithm to generate an efficient evaluation scheme of closed queries, which is a generalization of Vieille's famous QSQR algorithm for top-down evaluation of Datalog programs. A by-product of this work is a rather terse and elegant representation of QSQR.
We study the evaluation of positive conjunctive queries with Boolean aggregate tests (similar to HAVING queries in SQL) on probabilistic databases. Our motivation is to handle aggregate queries over imprecise data res...
详细信息
ISBN:
(纸本)9783540759867
We study the evaluation of positive conjunctive queries with Boolean aggregate tests (similar to HAVING queries in SQL) on probabilistic databases. Our motivation is to handle aggregate queries over imprecise data resulting from information integration or information extraction. More precisely, we study conjunctive queries with predicate aggregates using MIN, MAX, COUNT, SUM, AVG or COUNT(DISTINCT) on probabilistic databases. Computing the precise output probabilities for positive conjunctive queries (without HAVING) is #P-hard, but is in P for a restricted class of queries called safe queries. Further, for queries without self-joins either a query is safe or its data complexity is #P-Hard, which shows that safe queries exactly capture tractable queries without self-joins. In this paper, for each aggregate above, we find a class of queries that exactly capture efficient evaluation for HAVING queries without self-joins. Our algorithms use a novel technique to compute the marginal distributions of elements in a semiring, which may be of independent interest.
暂无评论