9630674
Reasoning About Web-Site Structure
Building large Web sites is similar in many ways to building knowledge and database systems. In particular, by providing a declarative, logical view of a Web site’s data and structure, many of a site builder’s tasks, such as creating complex sites, modifying a site’s structure, and creating multiple versions of a site, are simplified significantly. New systems, such aS STRUDEL, support logical views of Web sites by allowing site builders to construct a site declaratively. In this paper, we address an important problem for site builders: verifying that a Web site’s structure conforms to certain constraints. Specifically, we consider the problem of verifying that a Web site created declaratively by STRUDEL satisfies certain integrity constraints, such as ’all pages are reachable from the root’ and ’every organization page points to its suborganizations’, etc. Our contributions are (1) formulating the verification problem as an entailment problem in a logical setting, and (2) presenting a sound and complete algorithm for verifying large classes of integrity constraints that occur in practice. Our algorithm uses a novel data structure, the site schema, which enables us to identify cases in which the general reasoning problem reduces to a decidable problem.
2076813
Adding Structure to Unstructured Data
We develop a new schema for unstructured data. Traditional schemas resemble the type systems of programming languages. For unstructured data, however, the underlying type may be much less constrained and hence an alternative way of expressing constraints on the data is needed. Here, we propose that both data and schema be represented as edge-labeled graphs. We develop notions of conformance between a graph database and a graph schema and show that there is a natural and efficiently computable ordering on graph schemas. We then examine certain subclasses of schemas and show that schemas are closed under query applications. Finally, we discuss how they may be used in query decomposition and optimization.
1969955
A Query Language for XML
Abstract An important application of XML is the interchange of electronic data (EDI) between multiple data sources on the Web. As XML data proliferates on the Web, applications will need to integrate and aggregate data from multiple source and clean and transform data to facilitate exchange. Data extraction, conversion, transformation, and integration are all well-understood database problems, and their solutions rely on a query language. We present a query language for XML, called XML-QL, which we argue is suitable for performing the above tasks. XML-QL is a declarative, `relational complete' query language and is simple enough that it can be optimized. XML-QL can extract data from existing XML documents and construct new XML documents.
1399759
Warehousing and incremental evaluation for Web Site management
Recently, several systems have been proposed for building Web sites from declarative spec-iications. The salient feature of these systems is that they model both the structure and the content of a Web site as a view over some existing raw data. In this \Web site as view" paradigm, a critical issue is when to compute the site. One approach is to materialize the site completely before the users browse it: the disadvantages of this approach are high maintenance costs and stale data. Moreover, this approach is not applicable if the Web site has forms, because then the queries deening the Web site depends on user input. The other extreme approach is to precompute only the root(s) of the Web site, and then compute dynamically (at \click time") the queries that retrieves the information required to display the next page. In this paper we address the problem of choosing the optimal connguration for run-time management of a declaratively speciied Web site, trading oo the beneets of precomputation and incremental evaluation. First, we identify several novel optimizations that need to be considered in addition to optimizations obtained by precomputing views. These optimizations include simplifying queries based on contexts that can be derived from the browsing patterns, and lookahead computation. Second, we describe an algorithm for cost based search of a space of conngurations which include the above optimizations. Finally, given a connguration we show how to reformulate our Web-site deenition to exploit the views and data being cached.
6149937
Publishing Relational Data in XML: the SilkRoute Approach
Xyleme is a dynamic warehouse for XML data of the Web supporting query evaluation, change control and data integration. We briefly present our motivations, the general architecture and some aspects of Xyleme. The project we describe here was completed at the end of 2000. A prototype has been implemented. This prototype is now being turned into a product by a start-up company also called Xyleme [14]. Xyleme: a complex tissue of wood cells, functions in conduction and storage ...
7426500
UnQL: a query language and algebra for semistructured data based on structural recursion
Abstract. This paper presents structural recursion as the basis of the syntax and semantics of query languages for semistructured data and XML. We describe a simple and powerful query language based on pattern matching and show that it can be expressed using structural recursion, which is introduced as a top-down, recursive function, similar to the way XSL is defined on XML trees. On cyclic data, structural recursion can be defined in two equivalent ways: as a recursive function which evaluates the data top-down and remembers all its calls to avoid infinite loops, or as a bulk evaluation which processes the entire data in parallel using only traditional relational algebra operators. The latter makes it possible for optimization techniques in relational queries to be applied to structural recursion. We show that the composition of two structural recursion queries can be expressed as a single such query, and this is used as the basis of an optimization method for mediator systems. Several other formal properties are established: structural recursion can be expressed in first-order logic extended with transitive closure; its data complexity is PTIME; and over relational data it is a conservative extension of the relational calculus. The underlying data model is based on value equality, formally defined with bisimulation. Structural recursion is shown to be invariant with respect to value equality.
12283254
Iterator Types
System L is a linear λ-calculus with numbers and an iterator, which, although imposing linearity restrictions on terms, has all the computational power of Godel's System τ. System L owes its power to two features: the use of a closed reduction strategy (which permits the construction of an iterator on an open function, but only iterates the function after it becomes closed), and the use of a liberal typing rule for iterators based on iterative types. In this paper, we study these new types, and show how they relate to intersection types. We also give a sound and complete type reconstruction algorithm for System L.
1019046
Implementing Nominal Unification
Nominal matching and unification underly the dynamics of nominal rewriting. Urban, Pitts and Gabbay gave a nominal unification algorithm which finds the most general solution to a nominal matching or unification problem, if one exists. Later the algorithm was extended by Fernandez and Gabbay to deal with name generation and locality. In this paper we describe first a direct implementation of the nominal unification algorithm, including the extensions, in Maude. This implementation is not efficient (it is exponential in time), but we will show that we can obtain a feasible implementation by using termgraphs.
17556593
Type assignment and termination of interaction nets
Interaction nets have proved to be a useful tool for the study of computational aspects of various formalisms (e.g. λ-calculus, term rewriting systems), but they are also a programming paradigm in themselves, and this is actually how they were introduced by Lafont. In this paper we consider semi-simple interaction nets as a programming language, and present a type assignment system using intersection types. First we show that interactions preserve types (i.e., the system enjoys subject reduction), and we compare this type assignment system with the intersection systems for λ-calculus and term rewriting systems. Then we define a recursion scheme that ensures termination of all interaction sequences. By relaxing the scheme and using the type assignment system, we derive another sufficient condition for termination of interaction nets. Finally, we show that although the type system based on general intersection types is not decidable, its restriction to rank 2 types is, and we give an algorithm that computes principal types for nets.
11746228
Interaction Nets and Term-Rewriting Systems
Abstract Term-rewriting systems provide a framework in which it is possible to specify and program in a traditional syntax (oriented equations). Interaction nets, on the other hand, provide a graphical syntax for the same purpose, but can be regarded as being closer to an implementation since the reduction process is local and asynchronous, and all the operations are made explicit, including discarding and copying of data. Our aim is to bridge the gap between the above formalisms by showing how to understand interaction nets in a term-rewriting framework. This allows us to transfer results from one paradigm to the other, deriving syntactical properties of interaction nets from the (well-studied) properties of term-rewriting systems; in particular concerning termination and modularity.
16649053
Coinductive techniques for operational equivalence of interaction nets
In this paper we study a notion of operational equivalence for interaction nets, following the recent success of applying methods based on bisimulation to functional and object oriented programming languages. We set up notions of contextual equivalence and bisimilarity and show that they coincide. A coinduction principle then gives a simple and robust way of showing when two interaction nets are contextually equivalent. We include several examples to demonstrate the usefulness of the approach, in particular for optimizing interaction nets.