Extracting structured information and key details from medical report narratives is crucial to support healthcare data management, analysis and decision-making. However, the specialized nature of the reports, the complexity of the contents, and the high accuracy requirements of the results pose significant challenges to the structuring task. In this paper, we develop an LLM-based method to extract structure information from medical report narratives. Defining the structuring problem as mapping the narrative reports to the domain ontology, we design a framework to develop specialized LLMs that automatically learn and establish the mappings. At the core of this framework are report partitioning and interactive training data generation modules are. By separating complete reports into logically independent segments and training the LLMs on these segments independently, the trained LLMs can accurately capture the semantic relationships within each segment. Additionally, we explore different LLMs and formulate a simplistic scoring method to compare their accuracy, enabling us to select the best-performing model. Experimental evaluation on a real-world breast ultrasound report dataset demonstrates that our method achieves high accuracy with a small training dataset (400 samples). Specifically, the accuracy of structural information extraction and the attribute-value matching accuracy both exceed 96%.

Automatic tracking and segmentation of lesions in ultrasound videos could assist in early diagnosis and treatment plan development. However, this task is quite challenging due to problems such as low visual saliency of the lesions and large variation between adjacent frames. In this paper, we develop a Spatial-Temporal Fusion Network (STFNet) for unsupervised ultrasound video object segmentation. First, an Edge Blur Enhancement Module is designed to extract and preserve the edge details of the target objects in ultrasound frames for spatial feature enhancement. Then, a Dynamic Alignment Module is developed to correct the inter-frame inconsistencies by aligning target objects from adjacent frames with those in the current frame for temporal feature enhancement. To incorporate both the spatial and temporal information, we further implement a mixed training strategy. These innovations collectively refine the model’s learning process and substantially boost segmentation accuracy. Extensive evaluations on real lymphoma ultrasound video data demonstrate the competitive segmentation results of STFNet. Specifically, compared with the best results among seven competing baselines, STFNet achieves the best scores in terms of region similarity ${\mathcal{J}}$, contour accuracy ${\mathcal{F}}$ as well as their average ${\mathcal{J}}\& {\mathcal{F}}$.

Software systems rely on events for logging, coordination, handling unusual situations, and more. Monitoring events from systems that provide services can ensure that the service complies with policies, regulations, and other business rules. Notably, detecting violations of rules as early as possible is much desired as, for example, the service may reclaim resources from erring enactments. The primary goal of this paper is to develop techniques for detecting rule violations as early as possible. We formalize a model for events and a language to specify constraints on event timing and data. We develop algorithms to detect violations of individual rules at the earliest possible time, then use a chase process to detect violations of acyclic sets of rules. We also present optimization techniques to reduce monitoring overhead. Finally, we implement and evaluate our algorithms through experiments to demonstrate our approach is feasible and beneficial.

Real-time tracking and segmentation of ultrasound video sequence are prerequisite for identifying and analyzing lesions. While significant progress has been made in natural video object segmentation, developing a model for ultrasound video is still challenging due to problems such as low distinguishability and low visual saliency of the target objects, large variation between adjacent frames. These challenges are inherently complex and cannot be effectively tackled through a single process. This paper develops an end-to-end multi-stage network (EMNet) for ultrasound video object segmentation. EMNet consists of two stages. The inital mask generation stage comprises a contrast-enhanced layer to enhance visual contrast between targets and backgrounds. In this stage, a module that adopts the encoder-attention-decoder structure is designed for mask induction. After obtaining the initial segmentation mask, the mask refinement stage is followed to further improve initial segmentation. To prevent the propagation of errors, a gating mechanism is designed to control the fusion of segmentation probability maps in the initial and refinement stages. By transforming certain fixed parameters in different stage into trainable parameters and establishing an end-to-end learning process, we optimized the performance of our approach. We evaluate EMNet on real-world lymphoma ultrasound video dataset. Compared with the best results among seven competing baselines, EMNet achieves the best performance in terms of ℐ&ℱ and ℱ measures, the second-best performance with Param and FPS measures, which demonstrates the competitive performance in terms of both speed and accuracy.

Smooth Inter-organization or cross-domain data flows are increasingly demanded when more organizations are becoming data-driven, which will eventually lead to the rise of a new form of the world economy, that is, data economy (DE). Through exploring relevant concepts, technologies, issues and challenges facing DE, this paper discusses the operational concepts of DE ecosystem and its key elements, particularly data products and data marketplaces, and the trends of their developments. It then presents directions for research and development of DE ecosystem and its key elements, in order to help organizations and industry to prepare for the arrival of DE and identify areas for innovations and disruptive technologies. The paper also discusses the requirements of the data product design in the enterprise data ecosystem (EDE) for the rising data economy and the gaps that exist in the current data engineering and technologies, particularly examining the role of service technology in the development and practice of data economy ecosystems.

Business services are provided by enacting interrelated business processes. Service providers must ensure enactments comply with policies, regulations, and business rules, including rules with quantitative time constraints. Enforcing such rules at design-time may be too restrictive, so effective service provisioning includes expressing rules in a formal specification language and detecting violations of these rules at runtime. Many specification languages do not include quantitative time constraints; for languages with such constraints, it is often unknown if they have runtime monitors whose auxiliary data storage is of bounded size. In this paper, we formulate a technical model of services, a logic language with quantitative time constraints for specifying rules, and develop techniques for automatically generating monitors to detect rule violations. This approach involves two steps, translating: (1) rules to formulas in linear temporal logic (LTL) on finite traces, and (2) LTL formulas to finite state machines. Since algorithms exist for step (2), we focus on step (1), i.e., mapping rules to equivalent LTL formulas. We present and establish the correctness of two translation techniques for “singly-linked” rules. We also compare the size of formulas produced by these techniques with a method of translation derived from Kamp’s Theorem, showing an improvement from hyper-exponential to exponential size.

No abstract available.

Business processes are designed to achieve business goals under procedural rules by orchestrating tasks, information and documents. Managing data inconsistency in business processes is a challenging task. If not managed properly, business will face negative financial consequences. From literatures, BPMN modelling approaches deal with inconsistency problem by patterns; data provenance approaches analyze data generated in business process and investigate the reachability between data points. Although substantial works have been done, the data inconsistency problem has not been properly resolved. In particular, it is still lacking of modelling language and resolution for inconsistency caused by multiple starting points of business processes and dynamics of business processes execution. This paper provides data consistency solution in two aspects: a business process modelling in enriched business workflow notation with data states and temporal properties, and a workflow query algorithm to discovery data inconsistency issue.

We introduce an extension to the declarative and artifact-centric Guard Stage Milestone (GSM) process modeling language to represent temporal aspects (duration, deadlines, lower- and upper-bound constraints), define the correctness of executions of GSM processes with respect to temporal constraints, check controllability of processes, compute execution plans respecting temporal constraints, and provide a translation method allowing to execute controllable GSM+T processes on standard GSM Engines.

Conceptual elevation of data in business process modeling was first formulated in 2003. The research community responded to this new idea enthusiastically. In the past decade, there have been numerous research activities concerning the interactions between business processes/activities and data in many aspects of business process management. Many of the advancements have or will have impacted on design/modeling, analysis, implementation of business processes in practice. However, there is still a lack of techniques for developing a suite of "interrelated" processes realizing a business service. Interrelated processes are a cluster of processes that share data and other resources, are collectively constrained by regulations and policies, influence KPIs as a group. Many current practical applications of business workflow systems are in urgent need for tools and techniques for process clusters. In this paper, we formulate a broad notion of an "Enterprise Process Framework" (EPF) to address this need and outline several interesting research challenges arising from EPFs.

An important omission in current development practice for business process (or workflow) management systems is modeling of data & access for a business process, including relationship of the process data and the persistent data in the underlying enterprise database(s). This paper develops and studies a new approach to modeling data for business processes: representing data used by a process as a hierarchically structured business entity with (i) keys, local keys, and update constraints, and (ii) a set of data mapping rules defining exact correspondence between entity data values and values in the enterprise database. This paper makes the following technical contributions: (1) A data mapping language is formulated based on path expressions, and shown to coincide with a subclass of the schema mapping language Clio. (2) Two new notions are formulated: Updatability allows each update on a business entity (or database) to be translated to updates on the database (or resp. business entity), a fundamental requirement for process implementation. Isolation reflects that updates by one process execution do not alter data used by another running process. The property provides an important clue in process design. (3) Decision algorithms for updatability and isolation are presented, and they can be easily adapted for data mappings expressed in the subclass of Clio.

Traditional approaches to Business Process Management (BPM) focus primarily on the process aspects, and treat the persistent data accessed and manipulated by the business processes as second class citizens. A recent approach to BPM, based on "business artifacts", is centered on a modeling framework that places data and process on an equal footing. The approach has been shown useful in various application domains, and one variant of business artifacts forms the basis of the emerging OMG Case Management Model and Notation (CMMN) standard. Research results have been developed around conceptual models, enterprise interoperation, business intelligence, and verification. This data-centric approach has the potential to provide the basis for a new generation of BPM technology in support of diverse application, and fueled by the insights into abstraction and data management that have been the hallmark of database research since the 70's.

Data and its manipulation are essential in business processes (BPs). It is desirable to ensure within BP executions that every update to a database server guarantees to satisfy all relevant data integrity constraints (ICs). Furthermore, the earlier in a BP execution a violation is detected the more dependable the BP is. This paper studies the Process Safety Problem (PSP): will an incoming message be used in a database update causing IC violations? PSP is unsolvable in general. Taking advantage of the design-time "guard injection" technique, we propose a runtime proactive enforcement mechanism, called "process safe guarding", based on symbolic execution of BPEL processes for a bounded number of steps under "conservative strategy". Related challenges are also discussed.

No abstract available.

Almost all medium- and large-scale businesses rely on electronic workflow systems to manage their business processes. A key challenge is to enable the easy re-use and modification of these workflow schemas and their piece-parts, so that they can be adapted to new business situations. This paper describes an approach for automatic construction (and thus, evolution) of a workflow schema that satisfies a specified condition (or "goal"), starting from a set of basic building block services (or "tasks"). We use a workflow model based on "business artifacts", which represent key (real or conceptual) business entities, and include both the business-relevant data about them and a specification of their lifecycle, that is, how they can evolve over time as they move through the workflow as the result of services being applied to them.

Artifact-centric business process models allow to describe artifacts (data objects) and their life cycles, which allow designers to focus on individual artifact in business processes, thus simplifies the design and analysis of business process model. However, this feature is a double-edged sword. The description of the relationships between artifacts becomes a new and nontrivial problem. It is better that the associations among business artifacts are specified at a high level as logical assertions. We think taking business constraints as complements of artifact-centric business operational model is an useful idea. Based on this consideration,in this paper, we propose an approach which combines both the declarative way and the procedural way in the construction of business processes. This flexibility can help designers to separate the parts of a business process that are more likely to change from those that are less likely to change. We propose a language TiLE to specify business constraints, and give complexity results on the satisfiability of TiLE. Moreover, we discussed how to enforce the constraints at run-time.

The main objective of composing web services is to identify usable web services through discovery and to orchestrate or assemble selected services according to the goal specification. In this paper, we formulate and study a framework of composing web services through discovery from a given goal service. A general algorithm for composition with or without a goal service invocation request is developed. Two notions of completeness, "schema completeness" and "instance completeness", are defined, which measure the ability of how thoroughly an algorithm can find a composition. The two notions correspond to compositions without or with a goal service request, resp. We show that schema completeness can be achieved by depth-first or breadth-first search combined with a tightening strategy. Further, the breadth-first search avoids redundancy. We also show that while instance complete algorithms exist, they generally need do invoke all candidate services.

We develop a framework to compose services through discovery and orchestration for a given goal service. Tightening techniques are used in composition algorithms to achieve completeness.

A critical issue in moving object databases is to develop appropriate indexing structures for continuously moving object locations so that queries can still be performed efficiently. However, such location changes typically cause a high volume of updates, which in turn poses serious problems on maintaining index structures. In this paper we propose a Lazy Group Update (LGU) algorithm for disk-based index structures of moving objects. LGU contains two key additional structures to group ``similar'' updates so that they can be performed together: a disk-based insertion buffer (I-Buffer) for each internal node, and a memory-based deletion table (D-Table) for the entire tree. Different strategies of ``pushing down'' an overflow I-Buffer to the next level are studied. Comprehensive empirical studies over uniform and skewed datasets, as well as simulated street traffic data show that LGU achieves a significant improvement on update throughput while allowing a reasonable performance for queries.

In main memory systems, the L2 cache typically employs cache line sizes of 32-128 bytes. These values are relatively small compared to high-dimensional data, e.g., >32D. The consequence is that existing techniques (on low-dimensional data) that minimize cache misses are no longer effective. We present a novel index structure, called /spl Delta/-tree, to speed up the high-dimensional query in main memory environment. The /spl Delta/-tree is a multilevel structure where each level represents the data space at different dimensionalities: the number of dimensions increases toward the leaf level. The remaining dimensions are obtained using principal component analysis. Each level of the tree serves to prune the search space more efficiently as the lower dimensions can reduce the distance computation and better exploit the small cache line size. Additionally, the top-down clustering scheme can capture the feature of the data set and, hence, reduces the search space. We also propose an extension, called /spl Delta//sup +/-tree, that globally clusters the data space and then partitions clusters into small regions. The /spl Delta//sup +/-tree can further reduce the computational cost and cache misses. We conducted extensive experiments to evaluate the proposed structures against existing techniques on different kinds of data sets. Our results show that the /spl Delta//sup +/-tree is superior in most cases.

We present a framework for analyzing interactions among Web services that communicate with asynchronous messages. We model the interactions among the peers participating in a composite Web service as conversations, the global sequences of messages exchanged among the peers. This naturally leads to the following model checking problem: Given an LTL property and a composite Web service, do the conversations generated by the composite Web service satisfy the property? We show that asynchronous messaging leads to state space explosion for bounded message queues and undecidability of the model checking problem for unbounded message queues. We propose a technique called synchronizability analysis to tackle this problem. If a composite Web service is synchronizable, its conversation set remains the same when asynchronous communication is replaced with synchronous communication. We give a set of sufficient conditions that guarantee synchronizability and that can be checked statically. Based on our synchronizability results, we show that a large class of composite Web services with unbounded message queues can be verified completely using a finite state model checker such as SPIN. We also show that synchronizability analysis can be used to check the reliability of top-down conversation specifications and we contrast the conversation model with the Message Sequence Charts. We integrated synchronizability analysis to a tool we developed for analyzing composite Web services.

The e-services paradigm promises to enable rich, flexible, and dynamic inter-operation of highly distributed, heterogeneous network-enabled services. Among the challenges, a fundamental question concerns the design and analysis of composite e-services. This paper proposes techniques towards automated design of composite e-services. We consider the Roman model which represents e-services as activity-based finite state automata. For a given set of existing e-services and a desired e-service, does there exist a "mediator" which delegates activities in the desired e-service to existing e-services? The question was raised in an early study by Berardi et. al. for a restricted subclass of delegators which does not take into consideration of future activities. In this paper, we define a more general class of delegators called "lookahead" delegators and we show that the hierarchy based on the amount of lookahead is strict. We, then, study the complexity of constructing such delegators. We prove that in the case of deterministic e-services, a k-lookahead delegator can be computed in time polynomial in the size of target and subcontractor e-services, and exponential in k and the number of subcontractor e-services. We also present Wozart, an automated mediator construction tool implemented to realize our approaches.

A conversation protocol is a top-down specification framework which specifies desired global behaviors of a Web service composition. In our earlier work (Fu et al., 2003) we studied the problem of realizability, i.e., given a conversation protocol, can a Web service composition be synthesized to generate behaviors as specified by the protocol. Several sufficient realizability conditions were proposed by Fu et al. (2003) to ensure realizability. Conversation protocols studied by Fu et al. (2003), however, are essentially abstract control flows without data semantics. This paper extends the work by Fu et al. (2003) and achieves more accurate analysis by considering data semantics: to overcome the state-space explosion caused by the data content, we propose a symbolic analysis technique for each realizability condition. In addition, we show that the analysis of the autonomy condition can be done using an iterative refinement approach.

The use of XML as the de facto data exchange standard has allowed integration of heterogeneous web based software systems regardless of implementation platforms and programming languages. On the other hand, the rich tree-structured data representation, and the expressive XML query languages (such as XPath) make formal specification and verification of software systems that manipulate XML data a challenge. In this paper, we present our initial efforts in automated verification of XML data manipulation operations using the SPIN model checker. We present algorithms for translating (bounded) XML data and XPath expressions to Promela, the input language of SPIN. The techniques presented in this paper constitute the basis of our Web Service Analysis Tool (WSAT) which verifies LTL properties of composite web services.

TPR-tree is a practical index structure for moving object databases. Due to the uniform distribution assumption, TPR-tree's bulk loading algorithm (TPR) is relatively inefficient in dealing with non-uniform datasets. In this paper we present a histogram-based bottom up algorithm (HBU) along with a modified top-down greedy split algorithm (TGS) for TPR-tree. HBU uses histograms to refine tree structures for different distributions. Empirical studies show that HBU outperforms both TPR and TGS for all kinds of non-uniform datasets, is relatively stable over varying degree of skewness and better for large datasets and large query windows.

In this paper, we consider a data model for uncertain trajectories of moving objects. In our model, the trajectory is a vector of uniform stochastic processes. We study "universal range queries" which examine whether the spatial properties of being inside a region hold throughout an entire time interval. An example of universal range queries is: "Retrieve all trucks staying in Santa Barbara area from 17:00 to 18:00 today". The main technical contributions are efficient algorithms for computing probabilistic answers to universal range queries. We show that the algorithms are efficient using theoretical worst case analysis and empirical studies. Interestingly, the practical complexity is better than theoretical bounds.

The web services paradigm promises to enable rich, exible, and dynamic interoperation of highly distributed and heterogeneous web-hosted services. Substantial progress has already been made towards this goal (e.g., emerging standards such as SOAP, WSDL,

This paper presents a set of tools and techniques for analyzing interactions of composite web services which are specified in BPEL and communicate through asynchronous XML messages. We model the interactions of composite web services as conversations, the global sequence of messages exchanged by the web services. As opposed to earlier work, our tool-set handles rich data manipulation via XPath expressions. This allows us to verify designs at a more detailed level and check properties about message content. We present a framework where BPEL specifications of web services are translated to an intermediate representation, followed by the translation of the intermediate representation to a verification language. As an intermediate representation we use guarded automata augmented with unbounded queues for incoming messages, where the guards are expressed as XPath expressions. As the target verification language we use Promela, input language of the model checker SPIN. Since SPIN model checker is a finite-state verification tool we can only achieve partial verification by fixing the sizes of the input queues in the translation. We propose the concept of synchronizability to address this problem. We show that if a composite web service is synchronizable, then its conversation set remains same when asynchronous communication is replaced with synchronous communication. We give a set of sufficient conditions that guarantee synchronizability and that can be checked statically. Based on our synchronizability results, we show that a large class of composite web services with unbounded input queues can be completely verified using a finite state model checker such as SPIN.

We adapt and optimize the BD-tree for main memory data processing. We compare the memory-based BD-tree against the B/sup +/-tree and CSB/sup +/-tree. We present cost models for exact match query for these indexes, including L2 cache and translation lookahead buffer (TLB) miss model and execution time model. We also implemented these structures and conducted experimental study. Our analytical and experimental results show that a well-tuned BD-tree is superior in most cases.

The emerging paradigm of electronic services promises to bring to distributed computation and services the flexibility that the web has brought to the sharing of documents. An understanding of fundamental properties of e-service composition is required in order to take full advantage of the paradigm. This paper examines proposals and standards for e-services from the perspectives of XML, data management, workflow, and process models. Key areas for study are identified, including behavioral service signatures, verification and synthesis techniques for composite services, analysis of service data manipulation commands, and XML analysis applied to service specifications. We give a sample of the relevant results and techniques in each of these areas.

In this paper, we present a novel index structure, called Δ-tree, to speed up processing of high-dimensional K-nearest neighbor (KNN) queries in main memory environment. The Δ-tree is a multi-level structure where each level represents the data space at different dimensionalities: the number of dimensions increases towards the leaf level which contains the data at their full dimensions. The remaining dimensions are obtained using Principal Component Analysis, which has the desirable property that the first few dimensions capture most of the information in the dataset. Each level of the tree serves to prune the search space more efficiently as the reduced dimensions can better exploit the small cache line size. Moreover, the distance computation on lower dimensionality is less expensive. We also propose an extension, called Δ+-tree, that globally clusters the data space and then further partitions clusters into small regions to reduce the search space. We conducted extensive experiments to evaluate the proposed structures against existing techniques on different kinds of datasets. Our results show that the Δ+-tree is superior in most cases.

This paper introduces a framework for modeling and specifying the global behavior of e-service compositions. Under this framework, peers (individual e-services) communicate through asynchronous messages and each peer maintains a queue for incoming messages. A global "watcher" keeps track of messages as they occur. We propose and study a central notion of a "conversation", which is a sequence of (classes of) messages observed by the watcher. We consider the case where the peers are represented by Mealy machines (finite state machines with input and output). The sets of conversations exhibit unexpected behaviors. For example, there exists a composite e-service based on Mealy peers whose set of conversations is not context free (and not regular). (The set of conversations is always context sensitive.) One cause for this is the queuing of messages; we introduce an operator "prepone" that simulates queue delays from a global perspective and show that the set of conversations of each Mealy e-service is closed under prepone. We illustrate that the global prepone fails to completely capture the queue delay effects and refine prepone to a "local" version on conversations seen by individual peers. On the other hand, Mealy implementations of a composite e-service will always generate conversations whose "projections" are consistent with individual e-services. We use projection-join to reflect such situations. However, there are still Mealy peers whose set of conversations is not the local prepone and projection-join closure of any regular language. Therefore, we propose conversation specifications as a formalism to define the conversations allowed by an e-service composition. We give two technical results concerning the interplay between the local behaviors of Mealy peers and the global behaviors of their compositions. One result shows that for each regular language, its local prepone and projection-join closure corresponds to the set of conversations by some Mealy peers effectively constructed from . The second result gives a condition on the shape of a composition which guarantees that the set of conversations that can be realized is the local prepone and projection-join closure of a regular language.

MOTIVATION: Many tools have been developed to visualize protein structures. Tools that have been based on Java 3D((TM)) are compatible among different systems and they can be run remotely through web browsers. However, using Java 3D for visualization has some performance issues with it. The primary concerns about molecular visualization tools based on Java 3D are in their being slow in terms of interaction speed and in their inability to load large molecules. This behavior is especially apparent when the number of atoms to be displayed is huge, or when several proteins are to be displayed simultaneously for comparison. RESULTS: In this paper we present techniques for organizing a Java 3D scene graph to tackle these problems. We have developed a protein visualization system based on Java 3D and these techniques. We demonstrate the effectiveness of the proposed method by comparing the visualization component of our system with two other Java 3D based molecular visualization tools. In particular, for van der Waals display mode, with the efficient organization of the scene graph, we could achieve up to eight times improvement in rendering speed and could load molecules three times as large as the previous systems could. AVAILABILITY: EPV is freely available with source code at the following URL: http://www.cs.ucsb.edu/~tcan/fpv/

An important class of queries in moving object databases involves trajectories. We propose to divide trajectory predicates into topological and non-topological parts; extend the 9 intersection model of Egenhofer-Franzosa to a 3-step evaluation strategy for trajectory queries: a filter step, a refinement step, and a tracing step.The filter and refinement steps are similar to region searches. As in spatial databases, approximations of trajectories are typically used in evaluating trajectory queries. In earlier studies, minimum bounding boxes (mbrs) are used to approximate trajectory segments which allow index structures to be built, e.g., TB-trees and R*-trees. The use of mbrs hinders the efficiency since mbrs are very coarse approximations especially for trajectory segments. To overcome this problem, we propose a new type of approximations, "minimum bounding octagon prism" mbop. We extend R*-tree to a new index structure "Octagon-Prism tree" (OP-tree) for mbops of trajectory segments. We conducted experiments to evaluate efficiency of OP-trees in performing region searches and trajectory queries. The results show that OP-trees improve region searches significantly over synthetic trajectory data sets to TB-trees and R*-trees and can significantly reduce the evaluation cost of trajectory queries compared to TB-trees.

Database applications for moving objects pose new challenges in modeling, querying, and maintenance of objects whose locations are rapidly changing over time. Previous work on modeling and querying spatio-temporal databases and constraint databases focus primarily on snapshots of changing databases. In this paper we study query evaluation techniques for moving object databases where moving objects are being updated frequently. We consider a constraint database approach to moving objects and queries. We classify moving object queries into: and queries. We argue that while traditional constraint query evaluation techniques are suitable for past queries, new techniques are needed for continuing and future queries. Motivated by nearest-neighbor queries, we define a query language based on a single generalized function f mapping from objects to continuous functions from time to ℝ. Queries in this language may be past, continuing, or future. We show that if f maps to polynomials, queries can be evaluated efficiently using the plane sweeping technique from computational geometry. Consequently, many known distance based queries can be evaluated efficiently.

For an enterprise to take advantage of the opportunities afforded by electronic commerce it must be able to make decisions about business transactions in near-real-time. In the coming era of segment-of-one marketing, these decisions will be quite intricate, so that customer treatments can be highly personalized, reflecting customer preferences, the customer's history with the enterprise, and targeted business objectives. This paper describes a paradigm called "decision flows" for specifying a form of incremental decision-making that can combine diverse business factors in near-real-time. This paper introduces and empirically analyzes a variety of optimization strategies for decision flows that are "data-intensive", i.e. that involve many database queries. A primary focus is on the use of parallelism and eagerness (a.k.a. speculative execution) to minimize work and/or reduce response time. A family of optimization techniques is developed, including algorithms and heuristics for scheduling tasks of the decision flow. Using a prototype execution engine the techniques are compared and analyzed in connection with decision-making applications having differing characteristics.

Efficient evaluation of spatial join is an important issue in spatial databases. The traditional evaluation strategy is to perform a join of "minimum bounding rectangles" (MBR) of the spatial objects (MBR-filter) and evaluate the actual join of the objects using the results of the join on approximations. Improvements to add additional filtering using more accurate approximations were also considered. In the present paper, we develop efficient algorithms for evaluating joins of "trapezoids" without using MBR'S. For the case where there are no intersecting non-horizontal boundaries of trapezoids in the same set, a spatial join of two sets of N trapezoids can be evaluated in O(N logb N+k) I/Os, where b is the page size and k the number of trapezoid intersections. For the general case without any assumptions, a join can be done in O((N+l+k) logb N) I/Os, where l is the total number of intersections of non-horizontal boundaries within the same set, and N, k, b are the same as above. The new algorithms can be used to evaluate spatial joins for polygons. One possibility is to decompose polygons into trapezoids and apply a trapezoid join algorithm. In particular, this approach is efficient for "I/O bounded polygons" (each of which can be retrieved in a constant number of I/Os). Given two sets of N "I/O bounded polygons, we show that in the case where there are no boundary intersections among polygons of the same set, the join of the two sets can be computed in O(N log/sub b/ N+k) I/Os, and in the case where there is no such assumption, the join takes O((N+l+k) log/sub b/ N) I/Os, where b is the page size, k the number of pairs of intersecting polygons, and l the number of boundary intersections within the same polygon set. Another possibility is to approximate objects by I/O bounded polygons (e.g., 5-corner convex polygons) which are finer than rectangles and use the new algorithms as a filter.

We develop a data integration approach for the efficient evaluation of queries over autonomous source databases. The approach is based on some novel applications and extensions of constraint database techniques. We assume the existence of a global database schema. The contents of each data source are described using a set of constraint tuples over the global schema; each such tuple indicates possible contributions from the source. The "source description catalog" (SDC) of a global relation consists of its associated constraint tuples. Such a method of description is advantageous since it is flexible to add new sources and to modify existing ones. In our framework, to evaluate a conjunctive query over the global schema, a plan generator first identifies relevant data sources by "evaluating" the query against the SDCs using techniques of constraint query evaluation; it then formulates an evaluation plan, consisting of some specialized queries over different paths. The evaluation of a query associated with a path is done by a sequence of partial evaluations at data sources along the path, similar to sideways information passing of Datalog; the partially evaluated queries travel along their associated paths. Our SDC based query planning is efficient since it avoids the NP-complete query rewriting process. We can achieve further optimization using techniques such as emptiness test.

Constraint databases integrate database technology with constraint solving to deal with new applications such as spatial or geographical applications and those requiring arithmetic computations. Although the conceptual framework is elegant, issues related to efficient query evaluation and optimization techniques have not been sufficiently addressed. We study efficient evaluation of spatial join in linear constraint databases in terms of the I/O complexity. We develop an extension of the classical B/sup +/-trees, called interval B/sup +/-trees, and show that they can be used to efficiently evaluate the spatial join of relations with dense-order and linear constraints. Specifically, we develop a general algorithm for joining two sets of rectangles using interval B/sup +/-trees. We show that the algorithm has the worst case I/O complexity of O(bNlog/sub b/(N/b)+k), where N is the number of input rectangles and k the number of intersections. We show that the algorithm can be used in performing joins of relations with linear constraints. For relations with dense-order constraints where the spatial objects are not strictly rectangles, we extend the algorithm so that it can process the natural join of two N-tuple relations within O(bNlog/sub b/(N/b)+k) I/Os, where k is the number of intersections. It remains open if one can achieve the same upper bound in the linear case.

We develop a new technique based on counter machines to study the containment and equivalence of queries with linear constraints overintegers Z, natural numbers M, rational numbers Q and real numbers RWe show that the problems are decidable in double exponential time with an exponential time lower bound for conjunctive queries with linear constraints over Z and lV, decidable in double exponential time for constant-free conjunctive queries with linear constraints over Q and R. For the general classes of conjunctive queries with linear constraints over Q and R, the problems are decidable in double exponential space using reductions to the first-order theory of reals with addition.We also use the counter machine technique to show that for "connected" first-order queries with linear constraints over Z and lV, the containment and equivalence problems are decidable over "bounded-degree databases".

) St ephane Grumbach I.N.R.I.A. Rocquencourt BP 105 78153 Le Chesnay, France [email protected] Jianwen Su Computer Science Department University of California Santa Barbara, California 93106, USA [email protected] Abstract We develop a framework for (real) constraint databases based on finite precision arithmetic which fulfills the main requirements of practical constraint databases. First, it allows the manipulation of approximate values, standard in scientific applications. More importantly, it permits the extension of the relational calculus with aggregate functions, while preserving the fundamental property of closed form evaluation with PTIME data complexity. This is an important step since the initial model of [KKR90] cannot be extended to aggregate functions. Moreover, finite precision computation plays a central role in efficient query processing. We introduce the finite precision semantics of queries and prove expressive power results concerning it. We then prese...

After inserting a tuple into (or deleting a tuple from) a database, a "first-order incremental evaluation system" (or "foies") for a database query derives the new query answer by using a non recursive or first-order query on the new database, the old answer, and perhaps some (stored) auxiliary relations.Furthermore, the auxiliary relations must also be maintained in the same manner, i.e., derived using first-order queries.In this paper we measure the space needed by foies in terms of the maximal arity of the auxiliary relations and present results on existence and nonexistence of space restricted foies for a variety of conventional queries.We construct space efficient foies for these queries, and show that the space bounds are tight using a variation of Ehrenfeucht-Fraiss6 games.In particular, we show that, for transitive closure over undirected graphs, the minimum space bound of its foies is exactly 2; this resolves an open problem raised by Patnaik and Immerman in PODS '94. 1 Introduction Recently, there have been research interests focusing on incremental evaluations of database queries [BLT86, AP87, Kuc91, WDSY91, DT92, DS93a, DS93b, DST93, DS95, GMS93, P194, RRSS94].In par-

We consider infinite databases which admit a finite representation in terms of dense-order constraints.

We study classes of infinite but finitely representable databases based on constraints, motivated by new database applications such as geographical databases. The mathematical framework is based on classical decidable first-order theories. We investigate the theory of finitely representable models and prove that it differs strongly from both classical model theory and finite model theory. In particular, we show that most of the well known theorems of either one fail (compactness, completeness, locality, 0/1 laws, etc.). An immediate consequence is the lack of tools to consider the definability of queries in the relational calculus over finitely representable databases. We illustrate this very challenging problem through some classical examples.

Conventional database query languages are considered in the context of untyped sets. The algebra without while has the expressive power of the typed complex object algebra. The algebra plus while, and COL with untyped sets (under stratified semantics or inflationary semantics) have the power of the computable queries. The calculus has power beyond the computable queries; and is characterized using the typed complex object calculus with invention. The Bancilhon-Khoshafian calculus is also discussed. A technical tool, called “generic Turing machine”, is introduced and used in several of the proofs.

A formal framework for studying the expressive power and complexity of OODB queries is developed. Three approaches to modeling sets are articulated and compared. The class of regular OODB schemas supports the explicit representation of set-valued types. Using an object-based semantics for sets, the regular schemas correspond to most implemented OODB systems in the literature; a value-based semantics for sets is also introduced. Without restrictions, both of these approaches support the specification of all computable queries. Assuming that the new operator is prohibited, the query language of the regular OODB schemas under the object-based semantics is complete in PSPACE; and under the value-based semantics it has hyper-exponential complexity. The third approach to modeling sets is given by the algebraic OODB model, in which multi-valued attributes rather than set-valued types are supported. method implementations can use operators stemming from the relational algebra, and do not have side-effects. The query language of algebraic OODBs is more powerful than the relational algebra but has complexity bounded by PTIME. The expressive power and complexity of data access for other variations of OODBs are also considered. Finally, a new relational query language, called algebra + pointwise recursion, is introduced. This is equivalent to the algebraic OODB language, and can compute generalized transitive closure.

The set-height of a complex object type is defined to be its level of nesting of the set construct. In a query of the complex object calculus which maps a database D to an output type T, an intermediate type is a type which is used by some variable of the query, but which is not present in D or T. For each k, i ≥ 0 we define CALCk,i to be the family of calculus queries mapping from and to types with set-height ≤ k and using intermediate types with set-height ≤ i In particular, CALC0,0 is the relational calculus, and CALC0,1 is equivalent to the family of second-order (relational) queries

When databases are larger