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.
1297751
Storing semistructured data with STORED
Systems for managing and querying semistructured-data sources often store data in proprietary object repositories or in a tagged-text format. We describe a technique that can use relational database management systems to store and manage semistructured data. Our technique relies on a mapping between the semistructured data model and the relational data model, expressed in a query language called STORED. When a semistructured data instance is given, a STORED mapping can be generated automatically using data-mining techniques. We are interested in applying STORED to XML data, which is an instance of semistructured data. We show how a document-type-descriptor (DTD), when present, can be exploited to further improve performance.
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.
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 ...
3338932
Querying XML Data
XML threatens to expand beyond its document markup origins to become the basis for data interchange on the Internet. One highly anticipated application of XML is the interchange of electronic data (EDI). Unlike existing Web documents, electronic data is primarily intended for computer, not human, consumption. For example, businesses could publish data about their products and services, and potential customers could compare and process this information automatically; business partners could exchange internal operational data between their information systems on secure channels; search robots could integrate automatically information from related sources that publish their data in XML format, like stock quotes from financial sites, sports scores from news sites. New opportunities will arise for third parties to add value by integrating, transforming, cleaning, and aggregating XML data. Once it becomes pervasive, it’s not hard to imagine that many information sources will structure their external view as a repository of XML data, no matter what their internal storage mechanisms. Data exchange between applications will then be in XML format. What is then the role of a query language in this world? One could see it as a local adjunct to a browsing capability, providing a more expressive “find” command over one or more retrieved documents. Or it might serve as a souped-up version of XPointer, allowing richer forms of logical reference to portions of documents. Neither of these modes of use is very “databasey”. From the database viewpoint, the enticing role of an XML query language is as a tool for structural and content-based query that allows an application to extract precisely the information it needs from one or several XML data sources. One salient question is why not adapt SQL or OQL to query XML. The answer is that XML data is fundamentally different from relational and object-oriented data, and therefore, neither SQL nor OQL is appropriate for XML. The key distinction between data in XML and data in traditional models is that XML is not rigidly structured. In the relational and object-oriented models, every data instance has a schema, which is separate from and independent of the data. In XML, the schema exists with the data. Thus, XML data is self-describing and can naturally model irregularities that cannot be modeled by relational or object-oriented data. For example, data items may have missing elements or multiple occurrences of the same element; elements may have atomic values in some data items and structured values in others; and collections of elements can have heterogeneous structure. Even XML data that has an associated DTD is self-describing (the data can still be parsed, even if
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.
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.
14181773
Nominal rewriting
Nominal rewriting is based on the observation that if we add support for @a-equivalence to first-order syntax using the nominal-set approach, then systems with binding, including higher-order reduction schemes such as @l-calculus beta-reduction, can be smoothly represented. Nominal rewriting maintains a strict distinction between variables of the object-language (atoms) and of the meta-language (variables or unknowns). Atoms may be bound by a special abstraction operation, but variables cannot be bound, giving the framework a pronounced first-order character, since substitution of terms for variables is not capture-avoiding. We show how good properties of first-order rewriting survive the extension, by giving an efficient rewriting algorithm, a critical pair lemma, and a confluence theorem for orthogonal systems.
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.
892182
Operational equivalence for interaction nets
The notion of contextual (or operational) equivalence is fundamental in the theory of programming languages. By setting up a notion of bisimilarity, and showing that it coincides with contextual equivalence, one obtains a simple coinductive proof technique for showing that two programs are equivalent in all contexts. In this paper we apply these (now standard) techniques to interactions nets, a graphical programming language characterized by local reduction. This work generalizes previous studies of operational equivalence in typed interaction nets since it can be applied to untyped systems, thus all systems of interaction nets are captured.
3029296
Strong Normalization of Typeable Rewrite Systems
This paper studies termination properties of rewrite systems that are typeable using intersection types. It introduces a notion of partial type assignment on Curryfied Term Rewrite Systems, that consists of assigning intersection types to function symbols, and specifying the way in which types can be assigned to nodes and edges between nodes in the tree representation of terms. Using a more liberal approach to recursion, a general scheme for recursive definitions is presented, that generalizes primitive recursion, but has full Turing-machine computational power. It will be proved that, for all systems that satisfy this scheme, every typeable term is strongly normalizable.