A logic for rule-based query optimization in graph-based data models View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1993

AUTHORS

Neil Coburn , Grant E. Weddell

ABSTRACT

We present a wide-spectrum algebra and refinement calculus designed to allow one to reason about query optimization in graph-based data models.A query language is wide-spectrum if it can be used to express both user level queries as well as low-level evaluation strategies or access plans. This property enables rule-based query optimization to be viewed as the process of refining expressions in such a language: “non-procedural” sub-expressions are gradually replaced by more “procedural” sub-expressions until an unambiguous access plan results. We begin by presenting an algebra that is wide-spectrum in this sense. One subset of operations within the algebra can be used to define the formal semantics of a non-procedural query language for graph-based data models. Another subset can express common data access paradigms such as an index scan, the “cut” operator in Prolog or the nested-iteration join processing strategy.We then present a refinement calculus over the algebra which defines when one algebraic expression subsumes another. The calculus makes it possible to formally prove the correctness of rewrite rules used in rule-based query optimizers, and is sufficiently expressive to admit rules encoding many forms of semantic query optimization. More... »

PAGES

120-145

Book

TITLE

Deductive and Object-Oriented Databases

ISBN

978-3-540-57530-6
978-3-540-48212-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-57530-8_8

DOI

http://dx.doi.org/10.1007/3-540-57530-8_8

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1052689766


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Waterloo, UK", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, University of Waterloo, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Coburn", 
        "givenName": "Neil", 
        "id": "sg:person.015614722063.65", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015614722063.65"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Waterloo, UK", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, University of Waterloo, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Weddell", 
        "givenName": "Grant E.", 
        "id": "sg:person.01111756132.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01111756132.29"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1993", 
    "datePublishedReg": "1993-01-01", 
    "description": "We present a wide-spectrum algebra and refinement calculus designed to allow one to reason about query optimization in graph-based data models.A query language is wide-spectrum if it can be used to express both user level queries as well as low-level evaluation strategies or access plans. This property enables rule-based query optimization to be viewed as the process of refining expressions in such a language: \u201cnon-procedural\u201d sub-expressions are gradually replaced by more \u201cprocedural\u201d sub-expressions until an unambiguous access plan results. We begin by presenting an algebra that is wide-spectrum in this sense. One subset of operations within the algebra can be used to define the formal semantics of a non-procedural query language for graph-based data models. Another subset can express common data access paradigms such as an index scan, the \u201ccut\u201d operator in Prolog or the nested-iteration join processing strategy.We then present a refinement calculus over the algebra which defines when one algebraic expression subsumes another. The calculus makes it possible to formally prove the correctness of rewrite rules used in rule-based query optimizers, and is sufficiently expressive to admit rules encoding many forms of semantic query optimization.", 
    "editor": [
      {
        "familyName": "Ceri", 
        "givenName": "Stefano", 
        "type": "Person"
      }, 
      {
        "familyName": "Tanaka", 
        "givenName": "Katsumi", 
        "type": "Person"
      }, 
      {
        "familyName": "Tsur", 
        "givenName": "Shalom", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-57530-8_8", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-57530-6", 
        "978-3-540-48212-3"
      ], 
      "name": "Deductive and Object-Oriented Databases", 
      "type": "Book"
    }, 
    "keywords": [
      "graph-based data model", 
      "rule-based query optimization", 
      "query optimization", 
      "data model", 
      "query language", 
      "rule-based query optimizer", 
      "refinement calculus", 
      "non-procedural query languages", 
      "data access paradigm", 
      "semantic query optimization", 
      "level queries", 
      "query optimizer", 
      "subset of operations", 
      "formal semantics", 
      "index scan", 
      "rewrite rules", 
      "access paradigm", 
      "access plan", 
      "plan results", 
      "language", 
      "evaluation strategies", 
      "optimization", 
      "processing strategies", 
      "queries", 
      "semantics", 
      "Prolog", 
      "rules", 
      "correctness", 
      "algebraic expressions", 
      "optimizer", 
      "calculus", 
      "logic", 
      "paradigm", 
      "model", 
      "operators", 
      "algebra", 
      "operation", 
      "subset", 
      "strategies", 
      "plan", 
      "process", 
      "sense", 
      "results", 
      "reasons", 
      "cut", 
      "scans", 
      "form", 
      "properties", 
      "expression", 
      "wide-spectrum algebra", 
      "user level queries", 
      "low-level evaluation strategies", 
      "refining expressions", 
      "unambiguous access plan results", 
      "access plan results", 
      "common data access paradigms", 
      "nested-iteration join processing strategy", 
      "join processing strategy"
    ], 
    "name": "A logic for rule-based query optimization in graph-based data models", 
    "pagination": "120-145", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1052689766"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-57530-8_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-57530-8_8", 
      "https://app.dimensions.ai/details/publication/pub.1052689766"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_35.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-57530-8_8"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-57530-8_8'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-57530-8_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-57530-8_8'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-57530-8_8'


 

This table displays all metadata directly associated to this object as RDF triples.

135 TRIPLES      23 PREDICATES      84 URIs      77 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-57530-8_8 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N0db0d13f01784d859bdf2f9f25a421bc
4 schema:datePublished 1993
5 schema:datePublishedReg 1993-01-01
6 schema:description We present a wide-spectrum algebra and refinement calculus designed to allow one to reason about query optimization in graph-based data models.A query language is wide-spectrum if it can be used to express both user level queries as well as low-level evaluation strategies or access plans. This property enables rule-based query optimization to be viewed as the process of refining expressions in such a language: “non-procedural” sub-expressions are gradually replaced by more “procedural” sub-expressions until an unambiguous access plan results. We begin by presenting an algebra that is wide-spectrum in this sense. One subset of operations within the algebra can be used to define the formal semantics of a non-procedural query language for graph-based data models. Another subset can express common data access paradigms such as an index scan, the “cut” operator in Prolog or the nested-iteration join processing strategy.We then present a refinement calculus over the algebra which defines when one algebraic expression subsumes another. The calculus makes it possible to formally prove the correctness of rewrite rules used in rule-based query optimizers, and is sufficiently expressive to admit rules encoding many forms of semantic query optimization.
7 schema:editor N2b9f293e526e43119d0f535636dd898f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N43f6ae4dace94fa7a5969bab1d130a9e
12 schema:keywords Prolog
13 access paradigm
14 access plan
15 access plan results
16 algebra
17 algebraic expressions
18 calculus
19 common data access paradigms
20 correctness
21 cut
22 data access paradigm
23 data model
24 evaluation strategies
25 expression
26 form
27 formal semantics
28 graph-based data model
29 index scan
30 join processing strategy
31 language
32 level queries
33 logic
34 low-level evaluation strategies
35 model
36 nested-iteration join processing strategy
37 non-procedural query languages
38 operation
39 operators
40 optimization
41 optimizer
42 paradigm
43 plan
44 plan results
45 process
46 processing strategies
47 properties
48 queries
49 query language
50 query optimization
51 query optimizer
52 reasons
53 refinement calculus
54 refining expressions
55 results
56 rewrite rules
57 rule-based query optimization
58 rule-based query optimizer
59 rules
60 scans
61 semantic query optimization
62 semantics
63 sense
64 strategies
65 subset
66 subset of operations
67 unambiguous access plan results
68 user level queries
69 wide-spectrum algebra
70 schema:name A logic for rule-based query optimization in graph-based data models
71 schema:pagination 120-145
72 schema:productId N4a97f511b3ba457fac3989103451251c
73 Nfaf599603a354aed8d57e88d477e0e36
74 schema:publisher N54cea04901e24878a60b93c5c77d6f5e
75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052689766
76 https://doi.org/10.1007/3-540-57530-8_8
77 schema:sdDatePublished 2021-11-01T18:57
78 schema:sdLicense https://scigraph.springernature.com/explorer/license/
79 schema:sdPublisher Nbe7b7dd371d24fd68b08954d9b7825d4
80 schema:url https://doi.org/10.1007/3-540-57530-8_8
81 sgo:license sg:explorer/license/
82 sgo:sdDataset chapters
83 rdf:type schema:Chapter
84 N0db0d13f01784d859bdf2f9f25a421bc rdf:first sg:person.015614722063.65
85 rdf:rest N7289f45933304311b615725fb46be99d
86 N18fe158d47eb410c8e09a13ea0831eb8 schema:familyName Ceri
87 schema:givenName Stefano
88 rdf:type schema:Person
89 N2120760ffd6f4aeeb6a53c2ddf550ce5 schema:familyName Tsur
90 schema:givenName Shalom
91 rdf:type schema:Person
92 N2b9f293e526e43119d0f535636dd898f rdf:first N18fe158d47eb410c8e09a13ea0831eb8
93 rdf:rest Nbfbbdc41dd984430b84f9130dc11738c
94 N2c1b469e23f846279fbb007191897827 rdf:first N2120760ffd6f4aeeb6a53c2ddf550ce5
95 rdf:rest rdf:nil
96 N43f6ae4dace94fa7a5969bab1d130a9e schema:isbn 978-3-540-48212-3
97 978-3-540-57530-6
98 schema:name Deductive and Object-Oriented Databases
99 rdf:type schema:Book
100 N4a97f511b3ba457fac3989103451251c schema:name doi
101 schema:value 10.1007/3-540-57530-8_8
102 rdf:type schema:PropertyValue
103 N54cea04901e24878a60b93c5c77d6f5e schema:name Springer Nature
104 rdf:type schema:Organisation
105 N7289f45933304311b615725fb46be99d rdf:first sg:person.01111756132.29
106 rdf:rest rdf:nil
107 Nbe75a8bf56c04241b145bf3488cc31d0 schema:familyName Tanaka
108 schema:givenName Katsumi
109 rdf:type schema:Person
110 Nbe7b7dd371d24fd68b08954d9b7825d4 schema:name Springer Nature - SN SciGraph project
111 rdf:type schema:Organization
112 Nbfbbdc41dd984430b84f9130dc11738c rdf:first Nbe75a8bf56c04241b145bf3488cc31d0
113 rdf:rest N2c1b469e23f846279fbb007191897827
114 Nfaf599603a354aed8d57e88d477e0e36 schema:name dimensions_id
115 schema:value pub.1052689766
116 rdf:type schema:PropertyValue
117 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
118 schema:name Information and Computing Sciences
119 rdf:type schema:DefinedTerm
120 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
121 schema:name Information Systems
122 rdf:type schema:DefinedTerm
123 sg:person.01111756132.29 schema:affiliation grid-institutes:None
124 schema:familyName Weddell
125 schema:givenName Grant E.
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01111756132.29
127 rdf:type schema:Person
128 sg:person.015614722063.65 schema:affiliation grid-institutes:None
129 schema:familyName Coburn
130 schema:givenName Neil
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015614722063.65
132 rdf:type schema:Person
133 grid-institutes:None schema:alternateName Department of Computer Science, University of Waterloo, UK
134 schema:name Department of Computer Science, University of Waterloo, UK
135 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...