Trong ArangoDB, sẽ truy vấn, với bộ lọc, từ hàng xóm (s) được thực hiện trong O (n)?

Question

Tôi đã đọc Aql Graph Operation và Graphs và không tìm thấy ví dụ cụ thể và giải thích hiệu suất cho trường hợp sử dụng là SQL-Traverse.

Ví dụ:

Nếu tôi có một bộ sưu tập Người dùng, trong đó có một công ty liên quan đến bộ sưu tập Công ty

Collection Công ty có quan hệ vị trí vào bộ sưu tập Location;

Collection Location hoặc là một thành phố, quốc gia hoặc khu vực, và có mối quan hệ thành phố, nước, khu vực cho chính nó.

Bây giờ, tôi muốn truy vấn tất cả người dùng thuộc về các công ty ở Đức hoặc EU.

SELECT from Users where Users.company.location.city.country.name="Germany"; 
SELECT from Users where Users.company.location.city.parent.name="Germany"; 

hoặc

SELECT from Users where Users.company.location.city.country.region.name="europe"; 
SELECT from Users where Users.company.location.city.parent.parent.name="europe"; 

Giả sử rằng Location.name được lập chỉ mục, tôi có thể có hai câu hỏi trên thực hiện với O (n), với n là số tài liệu ở Vị trí (O (1) để truyền tải đồ thị, O (n) để quét chỉ mục)?

Tất nhiên, tôi chỉ có thể tiết kiệm regionName hoặc COUNTRYNAME trực tiếp tại công ty , như các thành phố và các nước trong Liên minh châu Âu, không giống như ở ... những nơi khác, sẽ không thể thay đổi, nhưng những gì nếu ... bạn biết những gì tôi có nghĩa là (đùa, nếu tôi có các trường hợp sử dụng khác đòi hỏi phải cập nhật liên tục)

Answer 1

Tôi sẽ giải thích điều này using the ArangoDB 2.8 Traversals.

Chúng Tạo những bộ sưu tập để phù hợp với shema của bạn sử dụng arangosh:

db._create("countries") 
db.countries.save({_key:"Germany", name: "Germany"}) 
db.countries.save({_key:"France", name: "France"}) 
db.countries.ensureHashIndex("name") 

db._create("cities") 
db.cities.save({_key: "Munich"}) 
db.cities.save({_key: "Toulouse") 

db._create("company") 
db.company.save({_key: "Siemens"}) 
db.company.save({_key: "Airbus"}) 

db._create("employees") 
db.employees.save({lname: "Kraxlhuber", cname: "Xaver", _key: "user1"}) 
db.employees.save({lname: "Heilmann", cname: "Vroni", _key: "user2"}) 
db.employees.save({lname: "Leroy", cname: "Marcel", _key: "user3"}) 

db._createEdgeCollection("CityInCountry") 
db._createEdgeCollection("CompanyIsInCity") 
db._createEdgeCollection("WorksAtCompany") 


db.CityInCountry.save("cities/Munich", "countries/Germany", {label: "beautiful South near the mountains"}) 
db.CityInCountry.save("cities/Toulouse", "countries/France", {label: "crowded city at the mediteranian Sea"}) 

db.CompanyIsInCity.save("company/Siemens", "cities/Munich", {label: "darfs ebbes gscheits sein? Oder..."}) 
db.CompanyIsInCity.save("company/Airbus", "cities/Toulouse", {label: "Big planes Ltd."}) 


db.WorksAtCompany.save("employees/user1", "company/Siemens", {employeeOfMonth: true}) 
db.WorksAtCompany.save("employees/user2", "company/Siemens", {veryDiligent: true}) 
db.WorksAtCompany.save("employees/user3", "company/Eurocopter", {veryDiligent: true}) 

Trong AQL chúng tôi sẽ viết truy vấn này cách khác xung quanh. Chúng tôi bắt đầu với thời gian liên tục FILTER trên thuộc tính được lập chỉ mục name và bắt đầu các lần truyền tải của chúng tôi từ đó trở đi. Do đó chúng ta lọc cho đất nước "Đức":

db._explain("FOR country IN countries FILTER country.name == 'Germany' RETURN country ") 
Query string: 
FOR country IN countries FILTER country.name == 'Germany' RETURN country 

Execution plan: 
Id NodeType  Est. Comment 
    1 SingletonNode  1 * ROOT 
    6 IndexNode   1  - FOR country IN countries /* hash index scan */ 
    5 ReturnNode   1  - RETURN country 

Indexes used: 
By Type Collection Unique Sparse Selectivity Fields  Ranges 
    6 hash countries false false  66.67 % [ `name` ] country.`name` == "Germany" 

Optimization rules applied: 
Id RuleName 
    1 use-indexes 
    2 remove-filter-covered-by-index 

Bây giờ chúng ta có nút khởi động cũng được lọc của chúng tôi, chúng tôi làm một traversal đồ thị theo hướng ngược lại.Kể từ khi chúng ta biết rằng Employees là đúng 3 bước đi từ đầu Vertex, và chúng tôi không quan tâm đến các con đường, chúng tôi chỉ trả lại lớp 3:

db._query("FOR country IN countries FILTER country.name == 'Germany' FOR v IN 3 INBOUND country CityInCountry, CompanyIsInCity, WorksAtCompany RETURN v") 

[ 
    { 
    "cname" : "Xaver", 
    "lname" : "Kraxlhuber", 
    "_id" : "employees/user1", 
    "_rev" : "1286703864570", 
    "_key" : "user1" 
    }, 
    { 
    "cname" : "Vroni", 
    "lname" : "Heilmann", 
    "_id" : "employees/user2", 
    "_rev" : "1286729095930", 
    "_key" : "user2" 
    } 
] 

Một số từ khoảng này yêu cầu hiệu suất:

• chúng tôi xác định vị trí Đức sử dụng một chỉ số băm là thời gian liên tục ->O (1)
• trên cơ sở đó chúng tôi muốn đi qua m nhiều con đường nơi m là t số lượng nhân viên ở số Đức; Mỗi người trong số họ có thể được đi qua trong thời gian không đổi. ->O (m) ở bước này.

• Return kết quả trong thời gian liên tục ->O (1)

  Tất cả kết hợp chúng ta cần O (m) nơi mà chúng tôi mong đợi m được ít hơn n (số lượng nhân viên) như được sử dụng trong SQL-Traversal của bạn.